You searched for subject:(Extremal combinatorics).
Showing records 1 – 30 of
54 total matches.
◁ [1] [2] ▶
University of Illinois – Urbana-Champaign
1.
Wagner, Zsolt Adam.
On some problems in extremal, probabilistic and enumerative combinatorics.
Degree: PhD, Mathematics, 2018, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/100954 
► This is a study of a small selection of problems from various areas of Combinatorics and Graph Theory, a fast developing field that provides a…
(more)
▼ This is a study of a small selection of problems from various areas of
Combinatorics and Graph Theory, a fast developing field that provides a diverse spectrum of powerful tools with numerous applications to computer science, optimization theory and economics. In this thesis, we focus on
extremal, probabilistic and enumerative problems in this field.
A central theorem in
combinatorics is Sperner's Theorem, which determines the maximum size of a family \F\subseteq \P(n) that does not contain a 2-chain F
1\subsetneq F
2. Erd\H{o}s later extended this result and determined the largest family not containing a k-chain F
1\subsetneq … \subsetneq F
k. Erd\H{o}s and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding
extremal result. In Chapter 2 we answer their question for all families of size at most (1-\eps)2
n, provided n is sufficiently larger compared to k and \eps.
The result of Chapter 2 is an example of a supersaturation, or Erd\H{o}s – Rademacher type result, which seeks to answer how many forbidden objects must appear in a set whose size is larger than the corresponding result. These supersaturation results are a key ingredient to a very recently discovered proof method, called the Container method. Chapters 3 and 4 show various examples of this method in action. In Chapter 3 we, among others, give tight bounds on the logarithm of the number of t-error correcting codes and illustrate how the Container method can be used to prove random analoges of classical
extremal results. In Chapter 4 we solve a conjecture of Burosch – Demetrovics – Katona – Kleitman – Sapozhenko about estimating the number of families in {0,1}
n which do not contain two sets and their union.
In Chapter 5 we improve an old result of Erd\H{o}s and Spencer. Folkman's theorem asserts that for each k ∈ \N, there exists a natural number n = F(k) such that whenever the elements of [n] are two-colored, there exists a set A \subset [n] of size k with the property that all the sums of the form ∑
x ∈ B x, where B is a nonempty subset of A, are contained in [n] and have the same color. In 1989, Erd\H{o}s and Spencer showed that F(k) ≥ 2
ck2/ log k, where c >0 is an absolute constant; here, we improve this bound significantly by showing that F(k) ≥ 2
2^{k-1/k} for all k∈ \N.
Fox – Grinshpun – Pach showed that every 3-coloring of the complete graph on n vertices without a rainbow triangle contains a clique of size Ω ≤ ft(n
1/3log
2 n)) which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. In Chapter 6 we show, amongst others, that every such coloring contains a 2-colored subgraph with chromatic number at least n
2/3, and this is best possible. As a direct corollary of our result we obtain a generalisation of the celebrated…
Advisors/Committee Members: Balogh, Jozsef (advisor), Kostochka, Alexandr V (Committee Chair), Tserunyan, Anush (committee member), Lavrov, Mikhail (committee member).
Subjects/Keywords: extremal combinatorics; probabilistic combinatorics; enumerative combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Wagner, Z. A. (2018). On some problems in extremal, probabilistic and enumerative combinatorics. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/100954
Chicago Manual of Style (16th Edition):
Wagner, Zsolt Adam. “On some problems in extremal, probabilistic and enumerative combinatorics.” 2018. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 09, 2021.
http://hdl.handle.net/2142/100954.
MLA Handbook (7th Edition):
Wagner, Zsolt Adam. “On some problems in extremal, probabilistic and enumerative combinatorics.” 2018. Web. 09 Mar 2021.
Vancouver:
Wagner ZA. On some problems in extremal, probabilistic and enumerative combinatorics. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2018. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/2142/100954.
Council of Science Editors:
Wagner ZA. On some problems in extremal, probabilistic and enumerative combinatorics. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2018. Available from: http://hdl.handle.net/2142/100954
University of Guelph
2.
Styner, Dustin.
A Collection of Results of Simonyi's Conjecture.
Degree: MS, Department of Mathematics and Statistics, 2012, University of Guelph
URL: https://atrium.lib.uoguelph.ca/xmlui/handle/10214/4926
► ℬ| ≤ 2n. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete…
(more)
▼ ℬ| ≤ 2
n. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete proof that the conjecture holds for all values of n up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when n>8. We also present a result describing the nature of the set of numbers over which the conjecture in fact holds. Lastly, we present a new problem in graph theory, and discuss a few cases of this problem.
Advisors/Committee Members: Pereira, Rajesh (advisor), McNicholas, Paul (advisor).
Subjects/Keywords: Combinatorics; Set Theory; Extremal Combinatorics; Graph Theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Styner, D. (2012). A Collection of Results of Simonyi's Conjecture. (Masters Thesis). University of Guelph. Retrieved from https://atrium.lib.uoguelph.ca/xmlui/handle/10214/4926
Chicago Manual of Style (16th Edition):
Styner, Dustin. “A Collection of Results of Simonyi's Conjecture.” 2012. Masters Thesis, University of Guelph. Accessed March 09, 2021.
https://atrium.lib.uoguelph.ca/xmlui/handle/10214/4926.
MLA Handbook (7th Edition):
Styner, Dustin. “A Collection of Results of Simonyi's Conjecture.” 2012. Web. 09 Mar 2021.
Vancouver:
Styner D. A Collection of Results of Simonyi's Conjecture. [Internet] [Masters thesis]. University of Guelph; 2012. [cited 2021 Mar 09].
Available from: https://atrium.lib.uoguelph.ca/xmlui/handle/10214/4926.
Council of Science Editors:
Styner D. A Collection of Results of Simonyi's Conjecture. [Masters Thesis]. University of Guelph; 2012. Available from: https://atrium.lib.uoguelph.ca/xmlui/handle/10214/4926
University of Cambridge
3.
Przykucki, Michał Jan.
Extremal and probabilistic bootstrap percolation.
Degree: PhD, 2013, University of Cambridge
URL: https://www.repository.cam.ac.uk/handle/1810/245349https://www.repository.cam.ac.uk/bitstream/1810/245349/2/license.txt
;
https://www.repository.cam.ac.uk/bitstream/1810/245349/5/thesis.pdf.txt
;
https://www.repository.cam.ac.uk/bitstream/1810/245349/6/thesis.pdf.jpg
► In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation…
(more)
▼ In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected.
In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n × n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n2/18+O(n).
In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n2/3 \rfloor.
In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, pc(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b ≥ r then the value of b itself does not yield any non-trivial lower bound on pc(T,r). In other words, for any ε > 0 there exists a tree T with branching number \br(T) = b and critical probability pc(T,r) < ε.
However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton – Watson trees. We show that for every r ≥ 2 there exists a constant cr>0 such that if T is a Galton – Watson tree with branching number \br(T) = b ≥ r then
[
pc(T,r) > \frac{cr}{b} e-\frac{b{r-1}}.
]
We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton – Watson trees with critical probability bounded from above by Cr e-\frac{b{r-1}} for some constant Cr>0.
Subjects/Keywords: Bootstrap percolation; Probabilistic combinatorics; Extremal combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Przykucki, M. J. (2013). Extremal and probabilistic bootstrap percolation. (Doctoral Dissertation). University of Cambridge. Retrieved from https://www.repository.cam.ac.uk/handle/1810/245349https://www.repository.cam.ac.uk/bitstream/1810/245349/2/license.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/5/thesis.pdf.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/6/thesis.pdf.jpg
Chicago Manual of Style (16th Edition):
Przykucki, Michał Jan. “Extremal and probabilistic bootstrap percolation.” 2013. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://www.repository.cam.ac.uk/handle/1810/245349https://www.repository.cam.ac.uk/bitstream/1810/245349/2/license.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/5/thesis.pdf.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/6/thesis.pdf.jpg.
MLA Handbook (7th Edition):
Przykucki, Michał Jan. “Extremal and probabilistic bootstrap percolation.” 2013. Web. 09 Mar 2021.
Vancouver:
Przykucki MJ. Extremal and probabilistic bootstrap percolation. [Internet] [Doctoral dissertation]. University of Cambridge; 2013. [cited 2021 Mar 09].
Available from: https://www.repository.cam.ac.uk/handle/1810/245349https://www.repository.cam.ac.uk/bitstream/1810/245349/2/license.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/5/thesis.pdf.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/6/thesis.pdf.jpg.
Council of Science Editors:
Przykucki MJ. Extremal and probabilistic bootstrap percolation. [Doctoral Dissertation]. University of Cambridge; 2013. Available from: https://www.repository.cam.ac.uk/handle/1810/245349https://www.repository.cam.ac.uk/bitstream/1810/245349/2/license.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/5/thesis.pdf.txt ; https://www.repository.cam.ac.uk/bitstream/1810/245349/6/thesis.pdf.jpg
University of Cambridge
4.
Milicevic, Luka.
Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.
Degree: PhD, 2018, University of Cambridge
URL: https://www.repository.cam.ac.uk/handle/1810/273375
► In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space (X,d), a…
(more)
▼ In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space (X,d), a family of n continuous maps f1,f2,\dots,fn\colon X → X is a \emph{contractive family} if there exists λ<1 such that for any x,y∈ X we have d(fi(x),fi(y)) ≤ λ d(x,y) for some i. In the first part of the thesis, we (i) construct a compact metric space (X,d) with a contractive family {f,g}, such that no word in f,g has a fixed point, and (ii) show that if {f,g,h} is a contractive family such that f,g,h commute and λ<10-23, then they have a common fixed point. The proofs of these two statements are combinatorial in nature. For bf{(i)}, we introduce a new concept of a \emph{diameter space}, leading us naturally to a combinatorial problem about constructing certain sets of words. The result bf{(ii)} has a Ramsey-theoretic flavour, and is based on studying the local and global structure of a related metric space on ℕ3. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of Kn, we can find sets X,Y,Z and colours x,y,z (not necessarily distinct) such that X\cup Y\cup Z=V(Kn), and each of Kn[X, x],Kn[Y, y] and Kn[Z, z] has diameter bounded by 160 (where KN[X,x] denotes the edges in X that have colour x). This theorem is motivated by the work on commuting contractive families, where the analogous statement for 3 colours played a crucial role, and by the Lovász-Ryser conjecture. The proof is in the spirit of structural graph theory. The key point is the fact that the diameters are bounded. This strengthens a result of Gyárfás, who proved the same but with no diameter bounds (i.e. just with the sets being connected). Recall that a set of points in ℝd is in \emph{general position} if no d+1 lie on a common hyperplane. Similarly, we say that a set of points in ℝd is in it{almost general position} if no d+2 lie on a common hyperplane. In the third part, we answer a question of Füredi, by showing that, for each d, there are sets of n points in almost general position in ℝd, whose subsets in general position have size at most o(n). The proof is based on algebraically studying to what extent polynomial maps preserve cohyperplanarity, and an application of the density version of the Hales – Jewett theorem. In the fourth part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in ℤN (the integers modulo N). For all ε>0 and k∈ℕ, we construct a subset A\subsetℤN for some N, such that |A2+kA| ≤ ε N, while A-A=ℤN. (Here A-A={a1-a2:a1,a2∈ A} and A2+kA={a1a2+a'1+a'2+\dots+a'k:a1,a2,a'1,a'2,\dots,a'k∈ A}.) We also prove some extensions of this result. Among other ingredients, the proof also includes an application of a…
Subjects/Keywords: combinatorics; graph theory; extremal combinatorics; metric geometry; combinatorial geometry; additive combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Milicevic, L. (2018). Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. (Doctoral Dissertation). University of Cambridge. Retrieved from https://www.repository.cam.ac.uk/handle/1810/273375
Chicago Manual of Style (16th Edition):
Milicevic, Luka. “Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.” 2018. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://www.repository.cam.ac.uk/handle/1810/273375.
MLA Handbook (7th Edition):
Milicevic, Luka. “Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.” 2018. Web. 09 Mar 2021.
Vancouver:
Milicevic L. Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. [Internet] [Doctoral dissertation]. University of Cambridge; 2018. [cited 2021 Mar 09].
Available from: https://www.repository.cam.ac.uk/handle/1810/273375.
Council of Science Editors:
Milicevic L. Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. [Doctoral Dissertation]. University of Cambridge; 2018. Available from: https://www.repository.cam.ac.uk/handle/1810/273375
Queen Mary, University of London
5.
Falgas-Ravry, Victor.
Thresholds in probabilistic and extremal combinatorics.
Degree: PhD, 2012, Queen Mary, University of London
URL: http://qmro.qmul.ac.uk/xmlui/handle/123456789/8827
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.566640
► This thesis lies in the field of probabilistic and extremal combinatorics: we study discrete structures, with a focus on thresholds, when the behaviour of a…
(more)
▼ This thesis lies in the field of probabilistic and extremal combinatorics: we study discrete structures, with a focus on thresholds, when the behaviour of a structure changes from one mode into another. From a probabilistic perspective, we consider models for a random structure depending on some parameter. The questions we study are then: When (i.e. for what values of the parameter) does the probability of a given property go from being almost 0 to being almost 1? How do the models behave as this transition occurs? From an extremal perspective, we study classes of structures depending on some parameter. We are then interested in the following questions: When (for what value of the parameter) does a particular property become unavoidable? What do the extremal structures look like? The topics covered in this thesis are random geometric graphs, dependent percolation, extremal hypergraph theory and combinatorics in the hypercube.
Subjects/Keywords: 519.2; Mathematics; Combinatorics; Discrete structures; Probabilistic combinatorics; Extremal combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Falgas-Ravry, V. (2012). Thresholds in probabilistic and extremal combinatorics. (Doctoral Dissertation). Queen Mary, University of London. Retrieved from http://qmro.qmul.ac.uk/xmlui/handle/123456789/8827 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.566640
Chicago Manual of Style (16th Edition):
Falgas-Ravry, Victor. “Thresholds in probabilistic and extremal combinatorics.” 2012. Doctoral Dissertation, Queen Mary, University of London. Accessed March 09, 2021.
http://qmro.qmul.ac.uk/xmlui/handle/123456789/8827 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.566640.
MLA Handbook (7th Edition):
Falgas-Ravry, Victor. “Thresholds in probabilistic and extremal combinatorics.” 2012. Web. 09 Mar 2021.
Vancouver:
Falgas-Ravry V. Thresholds in probabilistic and extremal combinatorics. [Internet] [Doctoral dissertation]. Queen Mary, University of London; 2012. [cited 2021 Mar 09].
Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/8827 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.566640.
Council of Science Editors:
Falgas-Ravry V. Thresholds in probabilistic and extremal combinatorics. [Doctoral Dissertation]. Queen Mary, University of London; 2012. Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/8827 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.566640
University of Waterloo
6.
Walsh, Zachary.
Quadratically Dense Matroids.
Degree: 2020, University of Waterloo
URL: http://hdl.handle.net/10012/16051
► This thesis is concerned with finding the maximum density of rank-n matroids in a minor-closed class. The extremal function of a non-empty minor-closed class \mathcal…
(more)
▼ This thesis is concerned with finding the maximum density of rank-n matroids in a minor-closed class.
The extremal function of a non-empty minor-closed class \mathcal M of matroids which excludes a rank-2 uniform matroid is defined by
h\mathcal M(n)=\max(|M|\colon M∈ \mathcal M { is simple, and } r(M) ≤ n).
The Growth Rate Theorem of Geelen, Kabell, Kung, and Whittle shows that this function is either linear, quadratic, or exponential in n.
In this thesis we prove a general result about classes with quadratic extremal function, and then use it to determine the extremal function for several interesting classes of representable matroids, for sufficiently large integers n.
In particular, for each integer t ≥ 4 we find the extremal function for all but finitely many n for the class of ℂ-representable matroids with no U2,t-minor, and we find the extremal function for the class of matroids representable over finite fields 𝔽1 and 𝔽2 where |𝔽1|-1 divides |𝔽2|-1 and |𝔽1| and |𝔽2| are relatively prime.
Subjects/Keywords: matroids; combinatorics; density; quadratic; extremal; fields
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Walsh, Z. (2020). Quadratically Dense Matroids. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/16051
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Walsh, Zachary. “Quadratically Dense Matroids.” 2020. Thesis, University of Waterloo. Accessed March 09, 2021.
http://hdl.handle.net/10012/16051.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Walsh, Zachary. “Quadratically Dense Matroids.” 2020. Web. 09 Mar 2021.
Vancouver:
Walsh Z. Quadratically Dense Matroids. [Internet] [Thesis]. University of Waterloo; 2020. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10012/16051.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Walsh Z. Quadratically Dense Matroids. [Thesis]. University of Waterloo; 2020. Available from: http://hdl.handle.net/10012/16051
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Waterloo
7.
Lindzey, Nathan.
Matchings and Representation Theory.
Degree: 2018, University of Waterloo
URL: http://hdl.handle.net/10012/14267
► In this thesis we investigate the algebraic properties of matchings via representation theory. We identify three scenarios in different areas of combinatorial mathematics where the…
(more)
▼ In this thesis we investigate the algebraic properties of matchings via representation theory. We identify three scenarios in different areas of combinatorial mathematics where the algebraic structure of matchings gives keen insight into the combinatorial problem at hand. In particular, we prove tight conditional lower bounds on the computational complexity of counting Hamiltonian cycles, resolve an asymptotic version of a conjecture of Godsil and Meagher in Erdos-Ko-Rado combinatorics, and shed light on the algebraic structure of symmetric semidefinite relaxations of the perfect matching problem
Subjects/Keywords: Representation Theory; Extremal Combinatorics; Symmetric Functions
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lindzey, N. (2018). Matchings and Representation Theory. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14267
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Lindzey, Nathan. “Matchings and Representation Theory.” 2018. Thesis, University of Waterloo. Accessed March 09, 2021.
http://hdl.handle.net/10012/14267.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Lindzey, Nathan. “Matchings and Representation Theory.” 2018. Web. 09 Mar 2021.
Vancouver:
Lindzey N. Matchings and Representation Theory. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10012/14267.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Lindzey N. Matchings and Representation Theory. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/14267
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Iowa State University
8.
Blumenthal, Adam.
Domination problems in directed graphs and inducibility of nets.
Degree: 2020, Iowa State University
URL: https://lib.dr.iastate.edu/etd/17952
► In this thesis we discuss two topics: domination parameters and inducibility. In the first chapter, we introduce basic concepts, definitions, and a brief history for…
(more)
▼ In this thesis we discuss two topics: domination parameters and inducibility. In the first chapter, we introduce basic concepts, definitions, and a brief history for both types of problems. We will first inspect domination parameters in graphs, particularly independent domination in regular graphs and we answer a question of Goddard and Henning. Additionally, we provide some constructions for graphs regular graphs of small degree to provide lower bounds on the independent domination ratio of these classes of graphs. In Chapter 3 we expand our exploration of independent domination into the realm of directed graphs. We will prove several results including providing a fastest known algorithm for determining existence of an independent dominating set in directed graphs with minimum in degree at least one and period not eqeual to one. We also construct a set of counterexamples to the analogue of Vizing's Conjecture for this setting. In the fourth chapter, we pivot from independent domination to split domination in directed graphs, where we introduce the split domination sequence. We will determine that almost all possible split domination sequences are realizable by some graphs, and state several open questions that would be of interest to continue on this field. In the fifth chapter we will provide a brief introduction to Flag Algebras, then determine the unique maximizer of induced net graphs in graphs of certain orders.
Subjects/Keywords: Directed Graphs; Domination; Extremal Combinatorics; Graphs; Inducibility
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Blumenthal, A. (2020). Domination problems in directed graphs and inducibility of nets. (Thesis). Iowa State University. Retrieved from https://lib.dr.iastate.edu/etd/17952
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Blumenthal, Adam. “Domination problems in directed graphs and inducibility of nets.” 2020. Thesis, Iowa State University. Accessed March 09, 2021.
https://lib.dr.iastate.edu/etd/17952.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Blumenthal, Adam. “Domination problems in directed graphs and inducibility of nets.” 2020. Web. 09 Mar 2021.
Vancouver:
Blumenthal A. Domination problems in directed graphs and inducibility of nets. [Internet] [Thesis]. Iowa State University; 2020. [cited 2021 Mar 09].
Available from: https://lib.dr.iastate.edu/etd/17952.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Blumenthal A. Domination problems in directed graphs and inducibility of nets. [Thesis]. Iowa State University; 2020. Available from: https://lib.dr.iastate.edu/etd/17952
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Illinois – Urbana-Champaign
9.
Liu, Hong.
Extremal graph theory: supersaturation and enumeration.
Degree: PhD, Mathematics, 2015, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/89148
► In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza…
(more)
▼ In this thesis, we study supersaturation and enumeration problems in
extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K
4, a complete graph on 4 vertices, in a K
4-free graph.
In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh.
In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C
i + o(1))2
n/4, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos.
In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.
Advisors/Committee Members: Balogh, Jozsef (advisor), Kostochka, Alexandr (Committee Chair), Reznick, Bruce (committee member), Molla, Theo (committee member).
Subjects/Keywords: Supersaturation; Enumeration; Typical Structure; Extremal Combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Liu, H. (2015). Extremal graph theory: supersaturation and enumeration. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/89148
Chicago Manual of Style (16th Edition):
Liu, Hong. “Extremal graph theory: supersaturation and enumeration.” 2015. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 09, 2021.
http://hdl.handle.net/2142/89148.
MLA Handbook (7th Edition):
Liu, Hong. “Extremal graph theory: supersaturation and enumeration.” 2015. Web. 09 Mar 2021.
Vancouver:
Liu H. Extremal graph theory: supersaturation and enumeration. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2015. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/2142/89148.
Council of Science Editors:
Liu H. Extremal graph theory: supersaturation and enumeration. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2015. Available from: http://hdl.handle.net/2142/89148
University of South Florida
10.
Theado, John.
An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs.
Degree: 2019, University of South Florida
URL: https://scholarcommons.usf.edu/etd/7969
► Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and…
(more)
▼ Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and theoretical computer science.
The Regularity Lemma hinges on the following concepts. Let G = (V, E) be a graph and let ∅ /= X, Y ⊂ V be a pair of disjoint vertex subsets. We define the density of the pair (X, Y ) by dG(X, Y ) = |E[X, Y ]|/(|X||Y |) where E[X, Y ] denotes the set of edges {x, y} ∈ E with x ∈ X and y ∈ Y . We say the pair (X, Y ) is ε-regular if all subsets XI ⊆ X and Y I ⊆ Y satisfying |XI| > ε|X| and |Y I| > ε|Y | also satisfy |dG(XI, Y I) − dG(X, Y )| < ε.
The Regularity Lemma states that, for all ε > 0, all large n-vertex graphs G = (V, E) admit a partition V = V1 ∪ · · · ∪ Vt, where t = t(ε) depends on ε but not on n, so that all but εt2 pairs (Vi, Vj), 1 ≤ i < j ≤ t, are ε-regular. While Szemere´di’s original proof demonstrates the existence of such a partition, it gave no method for (efficiently) constructing such partitions. Alon, Duke, Lefmann, Ro¨dl, and Yuster [1, 2] showed that such partitions can be constructed in time O(M (n)), where M (n) is the time needed to multiply two n × n {0, 1}-matrices over the integers. Kohayakawa, Ro¨dl, and Thoma [17, 18] improved this time to O(n2).
The Regularity Lemma can be extended to k-uniform hypergraphs, as can algorithmic for- mulations thereof. The most straightforward of these extends the concepts above to k-uniform hypergraphs H = (V, E) in a nearly verbatim way. Let ∅ /= X1, . . . , Xk ⊂ V be pairwise disjoint subsets, and let E[X1, . . . , Xk] denote the set of k-tuples {x1, . . . , xk} ∈ E satisfying x1 ∈ X1, . . . , xk ∈ Xk. We define the density of (X1, . . . , Xk) as
dH(X1, . . . , Xk) = |E[X1, . . . , Xk]| / |X1| · · · |Xk|.
We say that (X1, . . . , Xk) is ε-regular if all subsets XiI ⊆ Xi, 1 ≤ i ≤ k, satisfying |XiI| > ε|Xi| also satisfy
|dH (X1I , . . . , XkI ) − dH (X1, . . . , Xk)| < ε.
With these concepts, Szemeredi’s original proof can be applied to give that, for all integers k ≥ 2 and for all ε > 0, all n-vertex k-uniform hypergraphs H = (V, E) admit a partition V = V1 ∪· · ∪ Vt, where t = t(k, ε) is independent of n, so that all but εtk many k-tuples (Vi1 , . . . , Vik) are ε-regular, where 1 ≤ i1 < · · · < ik ≤ t. Czygrinow and Ro¨dl [4] gave an algorithm for such a regularity lemma, which in the context above, runs in time O(n2k−1 log5 n).
In this dissertation, we consider regularity lemmas for 3-uniform hypergraphs. In this setting, our first main result improves the algorithm of Czygrinow and Ro¨dl to run in time O(n3), which is optimal in its order of magnitude. Our second main result shows that this algorithm gives a stronger notion of regularity than what is described above, where this stronger notion is described in the course of this dissertation. Finally, we discuss some ongoing applications of our constructive regularity lemmas to some classical algorithmic hypergraph problems.
Subjects/Keywords: Density; Extremal Combinatorics; Links; Partition; Quasirandomness; Mathematics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Theado, J. (2019). An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs. (Thesis). University of South Florida. Retrieved from https://scholarcommons.usf.edu/etd/7969
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Theado, John. “An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs.” 2019. Thesis, University of South Florida. Accessed March 09, 2021.
https://scholarcommons.usf.edu/etd/7969.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Theado, John. “An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs.” 2019. Web. 09 Mar 2021.
Vancouver:
Theado J. An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs. [Internet] [Thesis]. University of South Florida; 2019. [cited 2021 Mar 09].
Available from: https://scholarcommons.usf.edu/etd/7969.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Theado J. An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs. [Thesis]. University of South Florida; 2019. Available from: https://scholarcommons.usf.edu/etd/7969
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Cambridge
11.
David, Stefan.
Extremal combinatorics and universal algorithms.
Degree: PhD, 2018, University of Cambridge
URL: https://doi.org/10.17863/CAM.25601
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.753383
► In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we…
(more)
▼ In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.
Subjects/Keywords: 511; Combinatorics; Extremal Combinatorics; Algorithms; Automata theory; Bootstrap percolation; Combinatorics of partially ordered sets
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
David, S. (2018). Extremal combinatorics and universal algorithms. (Doctoral Dissertation). University of Cambridge. Retrieved from https://doi.org/10.17863/CAM.25601 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.753383
Chicago Manual of Style (16th Edition):
David, Stefan. “Extremal combinatorics and universal algorithms.” 2018. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://doi.org/10.17863/CAM.25601 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.753383.
MLA Handbook (7th Edition):
David, Stefan. “Extremal combinatorics and universal algorithms.” 2018. Web. 09 Mar 2021.
Vancouver:
David S. Extremal combinatorics and universal algorithms. [Internet] [Doctoral dissertation]. University of Cambridge; 2018. [cited 2021 Mar 09].
Available from: https://doi.org/10.17863/CAM.25601 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.753383.
Council of Science Editors:
David S. Extremal combinatorics and universal algorithms. [Doctoral Dissertation]. University of Cambridge; 2018. Available from: https://doi.org/10.17863/CAM.25601 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.753383
Colorado State University
12.
Lindzey, Nathan.
Towards a general theory of Erdős-Ko-Rado combinatorics.
Degree: MS(M.S.), Mathematics, 2014, Colorado State University
URL: http://hdl.handle.net/10217/83990
► In 1961, Erdős, Ko, and Rado proved that for a universe of size n ≥ 2k a family of k-subsets whose members pairwise intersect cannot…
(more)
▼ In 1961, Erdős, Ko, and Rado proved that for a universe of size n ≥ 2k a family of k-subsets whose members pairwise intersect cannot be larger than n-1/k-1. This fundamental result of
extremal combinatorics is now known as the EKR theorem for intersecting set families. Since then, there has been a proliferation of similar EKR theorems in
extremal combinatorics that characterize families of more sophisticated objects that are largest with respect to a given intersection property. This line of research has given rise to many interesting combinatorial and algebraic techniques, the latter being the focus of this thesis. Algebraic methods for EKR results are attractive since they could potentially give rise to a unified theory of EKR
combinatorics, but the state-of-the-art has been shown only to apply to sets, vector spaces, and permutation families. These categories lie on opposite ends of the stability spectrum since the stabilizers of sets and vector spaces are large as possible whereas the stabilizer of a permutation is small as possible. In this thesis, we investigate a category that lies somewhere in between, namely, the perfect matchings of the complete graph. In particular, we show that an algebraic method of Godsil's can be lifted to the more general algebraic framework of Gelfand pairs, giving the first algebraic proof of the EKR theorem for intersecting families of perfect matchings as a consequence. There is strong evidence to suggest that this framework can be used to approach the open problem of characterizing the maximum t-intersecting families of perfect matchings, whose combinatorial proof remains illusive. We conclude with obstacles and open directions for extending this framework to encompass a broader spectrum of categories.
Advisors/Committee Members: Penttila, Tim (advisor), Hulpke, Alexander (committee member), Boucher, Christina (committee member).
Subjects/Keywords: algebraic combinatorics; extremal combinatorics; Erdős-Ko-Rado theorems; association schemes; algebraic graph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lindzey, N. (2014). Towards a general theory of Erdős-Ko-Rado combinatorics. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/83990
Chicago Manual of Style (16th Edition):
Lindzey, Nathan. “Towards a general theory of Erdős-Ko-Rado combinatorics.” 2014. Masters Thesis, Colorado State University. Accessed March 09, 2021.
http://hdl.handle.net/10217/83990.
MLA Handbook (7th Edition):
Lindzey, Nathan. “Towards a general theory of Erdős-Ko-Rado combinatorics.” 2014. Web. 09 Mar 2021.
Vancouver:
Lindzey N. Towards a general theory of Erdős-Ko-Rado combinatorics. [Internet] [Masters thesis]. Colorado State University; 2014. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10217/83990.
Council of Science Editors:
Lindzey N. Towards a general theory of Erdős-Ko-Rado combinatorics. [Masters Thesis]. Colorado State University; 2014. Available from: http://hdl.handle.net/10217/83990
University of Rochester
13.
Ethier, Dillon (1988 - ).
Sum-product estimates and finite point configurations
over p-adic fields.
Degree: PhD, 2017, University of Rochester
URL: http://hdl.handle.net/1802/31894
► We examine Erdös-Falconer type problems in the setting of <i>p</i>-adic numbers, and establish bounds on the size of a set <i>E</i> in Qpd that will…
(more)
▼ We examine Erdös-Falconer type problems in the
setting of <i>p</i>-adic numbers, and establish bounds
on
the size of a set <i>E</i> in
Qpd that will
guarantee E·E+E·E+ ... +E·E has positive Haar measure. Under a mild
regularity assumption, we establish a lower bound on the dimension
of a set that determines a set of simplices of positive measure,
which reduces to an analogue of the distance problem when
1-simplices are considered. Using the Mattila integral, we
establish a different bound that improves upon the first bound when
the dimension of the simplices is close to the ambient
dimension.
Subjects/Keywords: Combinatorics; Extremal problems; Harmonic analysis; Local fields; Nonarchimedean; p-adic
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Ethier, D. (. -. ). (2017). Sum-product estimates and finite point configurations
over p-adic fields. (Doctoral Dissertation). University of Rochester. Retrieved from http://hdl.handle.net/1802/31894
Chicago Manual of Style (16th Edition):
Ethier, Dillon (1988 - ). “Sum-product estimates and finite point configurations
over p-adic fields.” 2017. Doctoral Dissertation, University of Rochester. Accessed March 09, 2021.
http://hdl.handle.net/1802/31894.
MLA Handbook (7th Edition):
Ethier, Dillon (1988 - ). “Sum-product estimates and finite point configurations
over p-adic fields.” 2017. Web. 09 Mar 2021.
Vancouver:
Ethier D(-). Sum-product estimates and finite point configurations
over p-adic fields. [Internet] [Doctoral dissertation]. University of Rochester; 2017. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/1802/31894.
Council of Science Editors:
Ethier D(-). Sum-product estimates and finite point configurations
over p-adic fields. [Doctoral Dissertation]. University of Rochester; 2017. Available from: http://hdl.handle.net/1802/31894
University of Illinois – Chicago
14.
Terry, Caroline.
Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws.
Degree: 2016, University of Illinois – Chicago
URL: http://hdl.handle.net/10027/21323
► This thesis investigates connections between model theory and extremal combinatorics. The first part of the thesis consists of an analysis of discrete metric spaces and…
(more)
▼ This thesis investigates connections between model theory and
extremal combinatorics. The first part of the thesis consists of an analysis of discrete metric spaces and multigraphs, from the point of view of
extremal combinatorics. We first consider finite metric spaces with integer distances between 1 and r, where r is a fixed integer at least 2. We prove approximate enumeration and structure theorems for these metric spaces. When r is even, we prove precise structure and enumeration theorems, and obtain new zero-one laws as consequences. An (n,s,q)-graph is a multigraph on n vertices where every set of s vertices spans at most q edges. We study the problem of determining the maximum product of edge multiplicities in (n,s,q)-graphs. We prove sharp results for certain values of s and q, as well as corresponding stability theorems in some cases. These results are joint work with D. Mubayi.
The second part of the thesis uses model theory to unify under a general framework, certain definitions and theorems appearing in the first part of the thesis and throughout the literature in
extremal combinatorics. In particular, we consider classes of structures in finite relational languages which are closed under model theoretic substructure and isomorphism. In this setting, we give general definitions of
extremal structures, asymptotic density, and stability theorems. We prove a general enumeration theorem in terms of asymptotic density, and under the assumption of the existence of a stability theorem, we prove a general approximate structure theorem. We then show these results generalize the arguments appearing in many papers on structure and enumeration of combinatorial objects.
The last part of the thesis consists of joint work with M. Malliaris in which we consider a theorem in graph theory from the perspective of model theory. In particular, we reprove a theorem of Chudnovsky, Kim, Oum, and Seymour by reorganizing their proof in such a way that allows us to apply the stable Ramsey theorem in place of the usual Ramsey theorem. We also give an infinitary proof which implies the original finite result.
Advisors/Committee Members: Marker, David (advisor), Mubayi, Dhruv (committee member), Baldwin, John (committee member), Malliaris, Maryanthe (committee member), Starchenko, Sergei (committee member).
Subjects/Keywords: model theory; extremal combinatorics; Ramsey theory; zero-one laws; enumeration
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Terry, C. (2016). Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws. (Thesis). University of Illinois – Chicago. Retrieved from http://hdl.handle.net/10027/21323
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Terry, Caroline. “Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws.” 2016. Thesis, University of Illinois – Chicago. Accessed March 09, 2021.
http://hdl.handle.net/10027/21323.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Terry, Caroline. “Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws.” 2016. Web. 09 Mar 2021.
Vancouver:
Terry C. Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws. [Internet] [Thesis]. University of Illinois – Chicago; 2016. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10027/21323.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Terry C. Model Theory and Extremal Combinatorics: Structure, Enumeration, and 0-1 Laws. [Thesis]. University of Illinois – Chicago; 2016. Available from: http://hdl.handle.net/10027/21323
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Illinois – Chicago
15.
Wang, Lujia.
Problems in Extremal and Probabilistic Combinatorics.
Degree: 2018, University of Illinois – Chicago
URL: http://hdl.handle.net/10027/22982
► We study the following four problems in extremal and probabilistic combinatorics: 1. A sunflower is a collection of distinct sets such that the intersection of…
(more)
▼ We study the following four problems in
extremal and probabilistic
combinatorics:
1. A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection C of all of them, and |C| is smaller than each of the sets. We consider the problems of determining the maximum sum and product of k families of subsets of [n] that contain no sunflower of size k with one set from each family. For the sum, we prove that the maximum is
(k-1)2
n+1+∑
s=0k-2\binom{n}{s}
for all n ≥ k ≥ 3, and for the k=3 case of the product, we prove that the maximum is ≤ ft(\frac{1}{8}+o(1)))2
3n.
We conjecture that for all fixed k ≥ 3, the maximum product is (1/8+o(1))2
kn.
2. For k ≥ 4, a loose k-cycle C
k is a hypergraph with distinct edges e
1, e
2, …, e
k such that consecutive edges (modulo k) intersect in exactly one vertex and all other pairs of edges are disjoint. Our main result is that for every even integer k ≥ 4, there exists c>0 such that the number of triple systems with vertex set [n] containing no C
k is at most 2
cn2. An easy construction shows that the exponent is sharp in order of magnitude.
Our proof method is different than that used for most recent results of a similar flavor about enumerating discrete structures, since it does not use hypergraph containers. One novel ingredient is the use of some (new) quantitative estimates for an asymmetric version of the bipartite canonical Ramsey theorem.
3. For p ∈ [0,1] and an integer n, let Q(n,p) be the random set system, obtained by picking each subset of [n] independently with probability p. We prove that for many configurations \F that arise naturally in
extremal set theory there is a threshold probability p
0 such that if p \ll p
0 then asymptotically almost surely Q(n,p) contains no member of \F while if p \gg p
0 then asymptotically almost surely Q(n,p) contains many members of \F. Our general results imply that p
0=(t+1)
-n/t is the threshold for the appearance of a matching of size t and is also a threshold for the appearance a chain of size of size t. This generalizes results of R\'enyi from 1961 who answered a question of Erd\H os by solving these two problems for t=2. R\'enyi observed that his approach did not work for larger t for either a matching or chain.
We overcome this problem by using the second moment method on a more restricted class of configurations than the entire family \F. Our general result also determines the threshold for the appearance of a sunflower of size t and several other configurations.
4. A family \A\subset 2
[n] is intersecting if A\cap B\neq \emptyset for all A, B∈ \A. We prove that if p=2
-Θ(√{nlog n)}, the maximum intersecting family in the random set system Q(n, p) is (1+o(1))p 2
n-1. This is a continuation of the work by Balogh, Bohman and Mubayi who proved the random version of the Erd\H{o}s – Ko – Rado theorem in…
Advisors/Committee Members: Mubayi, Dhruv (advisor), Turan, Gyorgy (committee member), Reyzin, Lev (committee member), DasGupta, Bhaskar (committee member), Kaul, Hemanshu (committee member), Mubayi, Dhruv (chair).
Subjects/Keywords: Combinatorics; Extremal set theory; Probabilistic methods; Random set systems
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Wang, L. (2018). Problems in Extremal and Probabilistic Combinatorics. (Thesis). University of Illinois – Chicago. Retrieved from http://hdl.handle.net/10027/22982
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Wang, Lujia. “Problems in Extremal and Probabilistic Combinatorics.” 2018. Thesis, University of Illinois – Chicago. Accessed March 09, 2021.
http://hdl.handle.net/10027/22982.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Wang, Lujia. “Problems in Extremal and Probabilistic Combinatorics.” 2018. Web. 09 Mar 2021.
Vancouver:
Wang L. Problems in Extremal and Probabilistic Combinatorics. [Internet] [Thesis]. University of Illinois – Chicago; 2018. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10027/22982.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Wang L. Problems in Extremal and Probabilistic Combinatorics. [Thesis]. University of Illinois – Chicago; 2018. Available from: http://hdl.handle.net/10027/22982
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Illinois – Chicago
16.
Cameron, Alexander M.
Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs.
Degree: 2018, University of Illinois – Chicago
URL: http://hdl.handle.net/10027/23148
► Let a 2 to 1 directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such…
(more)
▼ Let a 2 to 1 directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph F let the nth
extremal number of F be the maximum number of edges that any directed hypergraph on n vertices can have without containing a copy of F. In 2007, Langlois, Mubayi, Sloan, and Turan determined the exact
extremal number for a particular directed hypergraph and found the
extremal number up to asymptotic equivalence for a second directed hypergraph. Each of these forbidden graphs had exactly two edges. In the first part of this thesis, we determine the exact
extremal numbers for every 2 to 1 directed hypergraph that has exactly two edges.
For fixed integers p and q, let f(n,p,q) denote the minimum number of colors needed to color all of the edges of the complete graph on n vertices such that no clique of p vertices spans fewer than q distinct colors. Any edge-coloring with this property is known as a (p,q)-coloring. In the second part of this thesis, we construct a (5,5)-coloring and a (5,6)-coloring with few colors, improving on the best known upper bounds for f(n,5,5) and f(n,5,6).
Advisors/Committee Members: Turán, György (advisor), Mubayi, Dhruv (advisor), Friedland, Shmuel (committee member), Reyzin, Lev (committee member), Sloan, Robert (committee member), Turán, György (chair).
Subjects/Keywords: combinatorics; graph theory; hypergraphs; extremal problems; directed hypergraphs; Ramsey's theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Cameron, A. M. (2018). Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs. (Thesis). University of Illinois – Chicago. Retrieved from http://hdl.handle.net/10027/23148
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Cameron, Alexander M. “Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs.” 2018. Thesis, University of Illinois – Chicago. Accessed March 09, 2021.
http://hdl.handle.net/10027/23148.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Cameron, Alexander M. “Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs.” 2018. Web. 09 Mar 2021.
Vancouver:
Cameron AM. Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs. [Internet] [Thesis]. University of Illinois – Chicago; 2018. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10027/23148.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Cameron AM. Extremal Problems on Directed Hypergraphs and the Erdös-Gyárfás Ramsey Problem Variant for Graphs. [Thesis]. University of Illinois – Chicago; 2018. Available from: http://hdl.handle.net/10027/23148
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of South Carolina
17.
Johnston, Jeremy Travis.
Turán Problems on Non-uniform Hypergraphs.
Degree: PhD, Mathematics, 2014, University of South Carolina
URL: https://scholarcommons.sc.edu/etd/2580
► A non-uniform hypergraph H = (V, E) consists of a vertex set V and an edge set E ⊆ 2 V; the edges in…
(more)
▼ A non-uniform hypergraph H = (V, E) consists of a vertex set V and an edge set E ⊆ 2 V; the edges in E are not required to all have the same cardinality. The set of all cardinalities of edges in H is denoted by R(H), the set of edge types. For a fixed hypergraph H, the Turán density π(H) is defined to be the maximum Lubell value of a graph G (in the limit) which is H-free and such that R(G) ⊆ R(H). The Lubell function, is the expected number of edges in G hit by a random full chain. This concept, which generalizes the Turán density of k-uniform hypergraphs, is motivated by recent work on
extremal poset problems.
Several properties of Turán density, such as supersaturation, blow-up, and suspension, are generalized from uniform hypergraphs to non-uniform hypergraphs. We characterize all the Turán densities of {1, 2}-graphs. In the final chapters, we discuss the notion of jumps in non-uniform hypergraphs. We refine the notion of jumps to strong jumps and weak jumps. We also show that every value in [0, 2) is a jump for {1, 2}-graphs and we determine exactly which values are the strong jumps. Using this refinement, we are able to determine, among other things, which values in the interval [0, 2) could be the density of a hereditary graph property of {1, 2}-graphs. Examples of densities of hereditary properties are Turán densities of families of graphs, Lagrangians of graphs, and others. The method and results may be extended to hereditary properties of other R-graphs, however one needs a more complete knowledge of the strong jump values in the interval [0, |R|).
Advisors/Committee Members: Linyuan Lu.
Subjects/Keywords: Mathematics; Physical Sciences and Mathematics; extremal combinatorics; hypergraph jumps; Turán density
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Johnston, J. T. (2014). Turán Problems on Non-uniform Hypergraphs. (Doctoral Dissertation). University of South Carolina. Retrieved from https://scholarcommons.sc.edu/etd/2580
Chicago Manual of Style (16th Edition):
Johnston, Jeremy Travis. “Turán Problems on Non-uniform Hypergraphs.” 2014. Doctoral Dissertation, University of South Carolina. Accessed March 09, 2021.
https://scholarcommons.sc.edu/etd/2580.
MLA Handbook (7th Edition):
Johnston, Jeremy Travis. “Turán Problems on Non-uniform Hypergraphs.” 2014. Web. 09 Mar 2021.
Vancouver:
Johnston JT. Turán Problems on Non-uniform Hypergraphs. [Internet] [Doctoral dissertation]. University of South Carolina; 2014. [cited 2021 Mar 09].
Available from: https://scholarcommons.sc.edu/etd/2580.
Council of Science Editors:
Johnston JT. Turán Problems on Non-uniform Hypergraphs. [Doctoral Dissertation]. University of South Carolina; 2014. Available from: https://scholarcommons.sc.edu/etd/2580
University of Cambridge
18.
Gruslys, Vytautas.
Tilings and other combinatorial results.
Degree: PhD, 2018, University of Cambridge
URL: https://doi.org/10.17863/CAM.18291
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.745014
► In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings…
(more)
▼ In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of ℤn. In this setting a tile T is just a finite subset of ℤn. We say that T tiles ℤn if the latter set admits a partition into isometric copies of T. Chalcraft observed that there exist T that do not tile ℤn but tile ℤd for some d > n. He conjectured that such d exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset P of size a power of 2, if P has a greatest and a least element, then there is a positive integer k such that [2]k can be partitioned into copies of P. The third tiling problem is about vertex-partitions of the hypercube graph Qn. Offner asked: if G is a subgraph of Qn such |G| is a power of 2, must V(Qd), for some d, admit a partition into isomorphic copies of G? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set P is a maximal collinear subset of P. P\'or and Wood considered colourings of finite P without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that |P| is large. They conjectured that for all k,l ≥ 2 there exists an n ≥ 2 such that if |P| ≥ n and P does not contain a line of cardinality larger than l, then every colouring of P with k colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case k=l=3. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with n vertices and m edges? For sufficiently large n we prove a conjecture of Füredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an r-uniform graph H is to assign for each of its edges one of the r! possible orderings of its elements. Then, for any p-set of vertices A and any p-set of indices I \subset [r], we define the I-degree of A to be the number of edges containing vertices A in precisely the positions labelled by I. Caro and Hansberg were interested in determining whether a given r-uniform hypergraph admits an orientation where every set of p vertices has some I-degree equal to 0. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for r large, but false in general.
Subjects/Keywords: 511; Combinatorics; Tilings; Combinatorial Geometry; Extremal Graph Theory; Ramsey Theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Gruslys, V. (2018). Tilings and other combinatorial results. (Doctoral Dissertation). University of Cambridge. Retrieved from https://doi.org/10.17863/CAM.18291 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.745014
Chicago Manual of Style (16th Edition):
Gruslys, Vytautas. “Tilings and other combinatorial results.” 2018. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://doi.org/10.17863/CAM.18291 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.745014.
MLA Handbook (7th Edition):
Gruslys, Vytautas. “Tilings and other combinatorial results.” 2018. Web. 09 Mar 2021.
Vancouver:
Gruslys V. Tilings and other combinatorial results. [Internet] [Doctoral dissertation]. University of Cambridge; 2018. [cited 2021 Mar 09].
Available from: https://doi.org/10.17863/CAM.18291 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.745014.
Council of Science Editors:
Gruslys V. Tilings and other combinatorial results. [Doctoral Dissertation]. University of Cambridge; 2018. Available from: https://doi.org/10.17863/CAM.18291 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.745014
19.
Przykucki, Michał Jan.
Extremal and probabilistic bootstrap percolation.
Degree: PhD, 2013, University of Cambridge
URL: https://doi.org/10.17863/CAM.16232
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.607571
► In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation…
(more)
▼ In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected. In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n × n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n2/18+O(n). In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n2/3 \rfloor. In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, pc(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b ≥ r then the value of b itself does not yield any non-trivial lower bound on pc(T,r). In other words, for any ε > 0 there exists a tree T with branching number \br(T) = b and critical probability pc(T,r) < ε. However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton – Watson trees. We show that for every r ≥ 2 there exists a constant cr>0 such that if T is a Galton – Watson tree with branching number \br(T) = b ≥ r then [ pc(T,r) > \frac{cr}{b} e-\frac{b{r-1}}. ] We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton – Watson trees with critical probability bounded from above by Cr e-\frac{b{r-1}} for some constant Cr>0.
Subjects/Keywords: 519.5; Bootstrap percolation; Probabilistic combinatorics; Extremal combinatorics
…to extremal problems, the size of the smallest percolating sets in
[n]d was… …extremal result in bootstrap percolation,
as a partial answer to a question of Bollobás, was… …Chapters 1, 2 and 3 of this dissertation we contribute to this developing
family of extremal… …trees.
In this chapter we answer an extremal question posed by Bollobás, that of
bounding the…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Przykucki, M. J. (2013). Extremal and probabilistic bootstrap percolation. (Doctoral Dissertation). University of Cambridge. Retrieved from https://doi.org/10.17863/CAM.16232 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.607571
Chicago Manual of Style (16th Edition):
Przykucki, Michał Jan. “Extremal and probabilistic bootstrap percolation.” 2013. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://doi.org/10.17863/CAM.16232 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.607571.
MLA Handbook (7th Edition):
Przykucki, Michał Jan. “Extremal and probabilistic bootstrap percolation.” 2013. Web. 09 Mar 2021.
Vancouver:
Przykucki MJ. Extremal and probabilistic bootstrap percolation. [Internet] [Doctoral dissertation]. University of Cambridge; 2013. [cited 2021 Mar 09].
Available from: https://doi.org/10.17863/CAM.16232 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.607571.
Council of Science Editors:
Przykucki MJ. Extremal and probabilistic bootstrap percolation. [Doctoral Dissertation]. University of Cambridge; 2013. Available from: https://doi.org/10.17863/CAM.16232 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.607571
20.
Day, Alan Nicholas.
A collection of problems in extremal combinatorics.
Degree: PhD, 2018, Queen Mary, University of London
URL: http://qmro.qmul.ac.uk/xmlui/handle/123456789/36669
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.766135
► Extremal combinatorics is concerned with how large or small a combinatorial structure can be if we insist it satis es certain properties. In this thesis…
(more)
▼ Extremal combinatorics is concerned with how large or small a combinatorial structure can be if we insist it satis es certain properties. In this thesis we investigate four different problems in extremal combinatorics, each with its own unique flavour. We begin by examining a graph saturation problem. We say a graph G is H-saturated if G contains no copy of H as a subgraph, but the addition of any new edge to G creates a copy of H. We look at how few edges a Kp- saturated graph can have when we place certain conditions on its minimum degree. We look at a problem in Ramsey Theory. The k-colour Ramsey number Rk(H) of a graph H is de ned as the least integer n such that every k- colouring of Kn contains a monochromatic copy of H. For an integer r > 3 let Cr denote the cycle on r vertices. By studying a problem related to colourings without short odd cycles, we prove new lower bounds for Rk(Cr) when r is odd. Bootstrap percolation is a process in graphs that can be used to model how infection spreads through a community. We say a set of vertices in a graph percolates if, when this set of vertices start off as infected, the whole graph ends up infected. We study minimal percolating sets, that is, percolating sets with no proper percolating subsets. In particular, we investigate if there is any relation between the smallest and the largest minimal percolating sets in bounded degree graph sequences. A tournament is a complete graph where every edge has been given an orientation. We look at the maximum number of directed k-cycles a tournament can have and investigate when there exist tournaments with many more k-cycles than expected in a random tournament.
Subjects/Keywords: 511; Mathematical Sciences; Combinatorics; Extremal combinatorics
…the
probability that A occurs.
9
1.2
Thesis Introduction
Extremal combinatorics is the… …satisfies certain conditions. One
class of objects that is central to extremal combinatorics is… …Another classical example of a problem in extremal combinatorics is the
following. Given a graph… …extremal combinatorics, each of which has its own distinct flavour.
10
1.2.1
Saturated Graphs… …example of an extremal problem on graphs is, what is the maximum number of edges a triangle-free…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Day, A. N. (2018). A collection of problems in extremal combinatorics. (Doctoral Dissertation). Queen Mary, University of London. Retrieved from http://qmro.qmul.ac.uk/xmlui/handle/123456789/36669 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.766135
Chicago Manual of Style (16th Edition):
Day, Alan Nicholas. “A collection of problems in extremal combinatorics.” 2018. Doctoral Dissertation, Queen Mary, University of London. Accessed March 09, 2021.
http://qmro.qmul.ac.uk/xmlui/handle/123456789/36669 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.766135.
MLA Handbook (7th Edition):
Day, Alan Nicholas. “A collection of problems in extremal combinatorics.” 2018. Web. 09 Mar 2021.
Vancouver:
Day AN. A collection of problems in extremal combinatorics. [Internet] [Doctoral dissertation]. Queen Mary, University of London; 2018. [cited 2021 Mar 09].
Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/36669 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.766135.
Council of Science Editors:
Day AN. A collection of problems in extremal combinatorics. [Doctoral Dissertation]. Queen Mary, University of London; 2018. Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/36669 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.766135
UCLA
21.
Das, Shagnik.
Extensions of Classic Theorems in Extremal Combinatorics.
Degree: Mathematics, 2014, UCLA
URL: http://www.escholarship.org/uc/item/5t2532gk
► Extremal combinatorics deals with the following fundamental question: how large can a structure be without containing forbidden configurations? The structures studied are extremely flexible, allowing…
(more)
▼ Extremal combinatorics deals with the following fundamental question: how large can a structure be without containing forbidden configurations? The structures studied are extremely flexible, allowing for a wide range of applications to diverse fields such as theoretical computer science, operations research, discrete geometry and number theory. Moreover, tools from probability theory, algebra and analysis have proven incredibly useful, spurring the development of new techniques in combinatorics. This synergy between different fields has led to incredible growth in recent decades, inspiring numerous directions for research.In this dissertation, we present new extensions of classic theorems in extremal combinatorics, employing probabilistic and analytic arguments to solve problems connected to number theory and coding theory. In Chapter 2, we greatly improve the bounds for the rainbow Turan problem for even cycles, a problem merging the graph theoretic disciplines of Turan theory and graph colouring. In Chapter 3, we use the analytic method of flag algebras to study a variant of Turan's theorem proposed by Erdos. We then shift to extremal set theory, and in Chapter 4 study the supersaturation problem for the Erdos-Ko-Rado Theorem. In Chapter 5 we discuss a probabilistic measure of supersaturation for intersecting families, introduced recently by Katona, Katona and Katona. These problems represent the various fields within extremal combinatorics that the author has worked in.
Subjects/Keywords: Mathematics; Theoretical mathematics; Combinatorics; Discrete mathematics; Extremal set theory; Graph theory; Supersaturation
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Das, S. (2014). Extensions of Classic Theorems in Extremal Combinatorics. (Thesis). UCLA. Retrieved from http://www.escholarship.org/uc/item/5t2532gk
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Das, Shagnik. “Extensions of Classic Theorems in Extremal Combinatorics.” 2014. Thesis, UCLA. Accessed March 09, 2021.
http://www.escholarship.org/uc/item/5t2532gk.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Das, Shagnik. “Extensions of Classic Theorems in Extremal Combinatorics.” 2014. Web. 09 Mar 2021.
Vancouver:
Das S. Extensions of Classic Theorems in Extremal Combinatorics. [Internet] [Thesis]. UCLA; 2014. [cited 2021 Mar 09].
Available from: http://www.escholarship.org/uc/item/5t2532gk.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Das S. Extensions of Classic Theorems in Extremal Combinatorics. [Thesis]. UCLA; 2014. Available from: http://www.escholarship.org/uc/item/5t2532gk
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of South Carolina
22.
Wang, Zhiyu.
Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.
Degree: PhD, Mathematics, 2020, University of South Carolina
URL: https://scholarcommons.sc.edu/etd/5771
► This thesis studies some problems in extremal and probabilistic combinatorics, Ricci curvature of graphs, spectral hypergraph theory and the interplay between these areas. The…
(more)
▼ This thesis studies some problems in
extremal and probabilistic
combinatorics, Ricci curvature of graphs, spectral hypergraph theory and the interplay between these areas. The first main focus of this thesis is to investigate several Ramsey-type problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and spectral techniques:
The size-Ramsey number Rˆ(G, r) is defined as the minimum number of edges in a hypergraph H such that every r-edge-coloring of H contains a monochromatic copy of G in H. We improved a result of Dudek, La Fleur, Mubayi and Rödl [ J. Graph Theory 2017 ] on the size-Ramsey number of tight paths and extended it to more colors.
An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Confirming a conjecture of Jahanbekam and West [J. Graph Theory 2016], we determine the anti-Ramsey number of t edge-disjoint rainbow spanning trees for all values of n and t.
We study the
extremal problems on Berge hypergraphs. Given a graph G = (V, E), a hypergraph H is called a Berge-G, denoted by BG, if there exists an injection i ∶ V (G) → V (H) and a bijection f ∶ E(G) → E(H) such that for every e = uv ∈ E(G), (i(u), i(v)) ⊆ f(e). We investigate the hypergraph Ramsey number of Berge cliques, the cover-Ramsey number of Berge hypergraphs, the cover-Turán desity of Berge hypergraphs as well as Hamiltonian Berge cycles in 3-uniform hypergraphs.
The second part of the thesis uses the ‘geometry’ of graphs to derive concentration inequalities in probabilities spaces. We prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the Erdős-Rényi random graph models G(n, p) and G(n,M), the random d-out(in)-regular directed graphs, and the space of random permutations. The main idea is using Ollivier’s work on the Ricci curvature of Markov chairs on metric spaces. We give a cleaner form of such concentration inequality in graphs. Namely, we show that for any Lipschitz function f on any graph (equipped with an ergodic random walk and thus an invariant distribution ν) with Ricci curvature at least κ > 0, we have
ν (∣f − Eνf∣ ≥ t) ≤ 2 exp (-t
2κ/7).
The third part of this thesis studies a problem in spectral hypergraph theory, which is the interplay between graph theory and linear algebra. In particular, we study the maximum spectral radius of outerplanar 3-uniform hypergraphs. Given a hypergraph H, the shadow of H is a graph G with V (G) = V (H) and E(G) = {uv ∶ uv ∈ h for some h ∈ E(H)}. A 3-uniform hypergraph H is called outerplanar if its shadow is outerplanar and all faces except the outer face are triangles, and the edge set of H is the set of triangle faces of its shadow. We show that the outerplanar 3-uniform…
Advisors/Committee Members: Linyuan Lu.
Subjects/Keywords: Mathematics; extremal combinatorics; graph theory; probabilistic methods; Ricci curvature; spectral hypergraph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Wang, Z. (2020). Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra. (Doctoral Dissertation). University of South Carolina. Retrieved from https://scholarcommons.sc.edu/etd/5771
Chicago Manual of Style (16th Edition):
Wang, Zhiyu. “Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.” 2020. Doctoral Dissertation, University of South Carolina. Accessed March 09, 2021.
https://scholarcommons.sc.edu/etd/5771.
MLA Handbook (7th Edition):
Wang, Zhiyu. “Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.” 2020. Web. 09 Mar 2021.
Vancouver:
Wang Z. Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra. [Internet] [Doctoral dissertation]. University of South Carolina; 2020. [cited 2021 Mar 09].
Available from: https://scholarcommons.sc.edu/etd/5771.
Council of Science Editors:
Wang Z. Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra. [Doctoral Dissertation]. University of South Carolina; 2020. Available from: https://scholarcommons.sc.edu/etd/5771
University of Vermont
23.
Martin, Jo Ryder.
Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs.
Degree: MS, Mathematics, 2020, University of Vermont
URL: https://scholarworks.uvm.edu/graddis/1233
► Hat guessing games—logic puzzles where a group of players must try to guess the color of their own hat—have been a fun party game…
(more)
▼ Hat guessing games—logic puzzles where a group of players must try to guess the color of their own hat—have been a fun party game for decades but have become of academic interest to mathematicians and computer scientists in the past 20 years. In 2006, Søren Riis, a computer scientist, introduced a new variant of the hat guessing game as well as an associated graph invariant, the guessing number, that has applications to network coding and circuit complexity. In this thesis, to better understand the nature of the guessing number of undirected graphs we apply the concept of saturation to guessing numbers and investigate the
extremal and saturation numbers of guessing numbers. We define and determine the
extremal number in terms of edges for the guessing number by using the previously established bound of the guessing number by the chromatic number of the complement. We also use the concept of graph entropy, also developed by Søren Riis, to find a constant bound on the saturation number of the guessing number.
Advisors/Committee Members: Puck Rombach.
Subjects/Keywords: Combinatorics; Extremal Graph Theory; Graph Saturation; Graph Theory; Guessing Number; Network Coding; Computer Sciences; Mathematics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Martin, J. R. (2020). Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs. (Thesis). University of Vermont. Retrieved from https://scholarworks.uvm.edu/graddis/1233
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Martin, Jo Ryder. “Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs.” 2020. Thesis, University of Vermont. Accessed March 09, 2021.
https://scholarworks.uvm.edu/graddis/1233.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Martin, Jo Ryder. “Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs.” 2020. Web. 09 Mar 2021.
Vancouver:
Martin JR. Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs. [Internet] [Thesis]. University of Vermont; 2020. [cited 2021 Mar 09].
Available from: https://scholarworks.uvm.edu/graddis/1233.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Martin JR. Extremal/Saturation Numbers for Guessing Numbers of Undirected Graphs. [Thesis]. University of Vermont; 2020. Available from: https://scholarworks.uvm.edu/graddis/1233
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Wesleyan University
24.
Davino, Rocco.
On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture.
Degree: Mathematics, 2019, Wesleyan University
URL: https://wesscholar.wesleyan.edu/etd_mas_theses/234
► The Erdős-Hajnal Conjecture is a famous open problem in extremal graph combinatorics relating the omission of a subgraph to the existence of a clique…
(more)
▼ The Erdős-Hajnal Conjecture is a famous open problem in
extremal graph
combinatorics relating the omission of a subgraph to the existence of a clique or an anti-clique of a given size in a graph. If true, this conjecture improves the well-known Ramsey Theorem. Chernikov and Starchenko proved a special case of this conjecture for certain families of graphs connected to the notion of stability in model theory. The goal of this paper is to provide the full details of their proofs and the necessary background to understand these details so that a first-year student in model theory can understand them. The main theorem in this paper is model-theoretic; its ingredients are some basic tools in local stability theory, such as local 2-rank, and the pseudo-finite dimension. This material is developed in the first few chapters, and then the proof of the main theorem is given in depth. We conclude by explaining how the graph-theoretic statement of the special case of Erdős-Hajnal follows from the aforementioned model theory.
Advisors/Committee Members: Cameron D. Hill.
Subjects/Keywords: logic; model theory; stability; pseudofinite; extremal graph combinatorics; Erdős; Hajnal; Erdős-Hajnal conjecture
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Davino, R. (2019). On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture. (Masters Thesis). Wesleyan University. Retrieved from https://wesscholar.wesleyan.edu/etd_mas_theses/234
Chicago Manual of Style (16th Edition):
Davino, Rocco. “On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture.” 2019. Masters Thesis, Wesleyan University. Accessed March 09, 2021.
https://wesscholar.wesleyan.edu/etd_mas_theses/234.
MLA Handbook (7th Edition):
Davino, Rocco. “On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture.” 2019. Web. 09 Mar 2021.
Vancouver:
Davino R. On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture. [Internet] [Masters thesis]. Wesleyan University; 2019. [cited 2021 Mar 09].
Available from: https://wesscholar.wesleyan.edu/etd_mas_theses/234.
Council of Science Editors:
Davino R. On a Model-Theoretic Approach to a Special Case of the Erdős-Hajnal Conjecture. [Masters Thesis]. Wesleyan University; 2019. Available from: https://wesscholar.wesleyan.edu/etd_mas_theses/234
University of South Florida
25.
Dizona, Jill.
On Algorithmic Fractional Packings of Hypergraphs.
Degree: 2012, University of South Florida
URL: https://scholarcommons.usf.edu/etd/4029
► Let F0 be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F0-packing of H is a family…
(more)
▼ Let F0 be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F0-packing of H is a family F of edge-disjoint copies of F0 which are subhypergraphs in H. Let nF0(H) denote the maximum size |F| of an F0-packing F of H. It is well-known that computing nF0(H) is NP-hard for nearly any choice of F0.
In this thesis, we consider the special case when F0 is a linear hypergraph, that is, when no two edges of F0 overlap in more than one vertex. We establish for z > 0 and n &ge n0(z) sufficiently large, an algorithm which, in time polynomial in n, constructs an F0-packing F of H of size |F| ≥ nF0(H) - znk.
A central direction in our proof uses so-called fractional F0-packings of H which are known to approximate nF0(H). The driving force of our argument, however, is the use and development of several tools within the theory of hypergraph regularity.
Subjects/Keywords: extremal combinatorics; fractional packings; linear hypergraphs; regularity; American Studies; Arts and Humanities; Mathematics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dizona, J. (2012). On Algorithmic Fractional Packings of Hypergraphs. (Thesis). University of South Florida. Retrieved from https://scholarcommons.usf.edu/etd/4029
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Dizona, Jill. “On Algorithmic Fractional Packings of Hypergraphs.” 2012. Thesis, University of South Florida. Accessed March 09, 2021.
https://scholarcommons.usf.edu/etd/4029.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Dizona, Jill. “On Algorithmic Fractional Packings of Hypergraphs.” 2012. Web. 09 Mar 2021.
Vancouver:
Dizona J. On Algorithmic Fractional Packings of Hypergraphs. [Internet] [Thesis]. University of South Florida; 2012. [cited 2021 Mar 09].
Available from: https://scholarcommons.usf.edu/etd/4029.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Dizona J. On Algorithmic Fractional Packings of Hypergraphs. [Thesis]. University of South Florida; 2012. Available from: https://scholarcommons.usf.edu/etd/4029
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
26.
Lee, Choongbum.
Problems in Extremal and Probabilistic Combinatorics.
Degree: Mathematics, 2012, UCLA
URL: http://www.escholarship.org/uc/item/7jc7f4ft
► Extremal combinatorics can be described as a subfield of combinatorics that studies the maximum or minimum size of discrete structures (such as graphs, set systems,…
(more)
▼ Extremal combinatorics can be described as a subfield of combinatorics that studies the maximum or minimum size of discrete structures (such as graphs, set systems, or convex bodies) with certain properties. For example, a classical question of this kind is, ``what is the maximum number of edges that a triangle-free graph can have?''. One particular beauty of extremal combinatorics lies in its connection to other fields of mathematics. That is, many questions in this area has applications in analysis, number theory, probability, and theoretical computer science. On the other hand, numerous problems which seem to be purely combinatorial can only be proved by relying on tools from algebra, analysis, topology, probability, and other areas. The most successfully developed tool among them is the so called probabilistic method. Probabilistic combinatorics on one hand refers to the study of this universal framework which can be potentially applied to any combinatorial problem and on the other hand refers to the study of random objects such as the Erdos-Renyi random graph. This field can also be described as the art of establishing certainty by adapting the language of uncertainty. These two fields, extremal and probabilistic combinatorics, share a central role in modern combinatorics and are fastly expanding; they do so by interacting with each other, and with other fields of mathematics. In this dissertation, we study several problems in these fields. These problems are chosen among the authors work in order to represent the various aspects of this field. In Chapter 2, we study a extremal problem on set systems and settle a 40 year old conjecture of Erdos and Shelah. Then in Chapters 3 and 4, we study two extremal problems using the probabilistic method, where the statement of the problem seemingly has nothing to do with probability. The first problem is a partitioning problem of graphs, and second is a problem of measuring self similarity of a graph. In Chapters 5 and 6, we study problems that lie in the intersection of extremal and probabilistic combinatorics; we take a classical theorem proved by Dirac, and further study it from various view points. These problems will illustrate the second aspect of probabilistic combinatorics.
Subjects/Keywords: Mathematics; combinatorics; discrete mathematics; extremal combinatorics; probabilistic combinatorics
…CHAPTER 1
Introduction
Extremal combinatorics can be described as a subfield of combinatorics… …overview of this field.
One particular beauty of extremal combinatorics lies in its connection to… …study several problems in the fields of extremal and probabilistic combinatorics. The first… …intersection of extremal and probabilistic combinatorics.
A classical theorem of Dirac [38]… …probabilistic and
extremal combinatorics, using variance calculations or martingale concentration…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lee, C. (2012). Problems in Extremal and Probabilistic Combinatorics. (Thesis). UCLA. Retrieved from http://www.escholarship.org/uc/item/7jc7f4ft
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Lee, Choongbum. “Problems in Extremal and Probabilistic Combinatorics.” 2012. Thesis, UCLA. Accessed March 09, 2021.
http://www.escholarship.org/uc/item/7jc7f4ft.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Lee, Choongbum. “Problems in Extremal and Probabilistic Combinatorics.” 2012. Web. 09 Mar 2021.
Vancouver:
Lee C. Problems in Extremal and Probabilistic Combinatorics. [Internet] [Thesis]. UCLA; 2012. [cited 2021 Mar 09].
Available from: http://www.escholarship.org/uc/item/7jc7f4ft.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Lee C. Problems in Extremal and Probabilistic Combinatorics. [Thesis]. UCLA; 2012. Available from: http://www.escholarship.org/uc/item/7jc7f4ft
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Cambridge
27.
Milicevic, Luka.
Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.
Degree: PhD, 2018, University of Cambridge
URL: https://doi.org/10.17863/CAM.20403
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.744557
Subjects/Keywords: 516; combinatorics; graph theory; extremal combinatorics; metric geometry; combinatorial geometry; additive combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Milicevic, L. (2018). Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. (Doctoral Dissertation). University of Cambridge. Retrieved from https://doi.org/10.17863/CAM.20403 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.744557
Chicago Manual of Style (16th Edition):
Milicevic, Luka. “Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.” 2018. Doctoral Dissertation, University of Cambridge. Accessed March 09, 2021.
https://doi.org/10.17863/CAM.20403 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.744557.
MLA Handbook (7th Edition):
Milicevic, Luka. “Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics.” 2018. Web. 09 Mar 2021.
Vancouver:
Milicevic L. Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. [Internet] [Doctoral dissertation]. University of Cambridge; 2018. [cited 2021 Mar 09].
Available from: https://doi.org/10.17863/CAM.20403 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.744557.
Council of Science Editors:
Milicevic L. Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics. [Doctoral Dissertation]. University of Cambridge; 2018. Available from: https://doi.org/10.17863/CAM.20403 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.744557
28.
Huang, Hao.
Various Problems in Extremal Combinatorics.
Degree: Mathematics, 2012, UCLA
URL: http://www.escholarship.org/uc/item/282049q8
► Extremal combinatorics is a central theme of discrete mathematics. It deals with the problems of finding the maximum or minimum possible cardinality of a collection…
(more)
▼ Extremal combinatorics is a central theme of discrete mathematics. It deals with the problems of finding the maximum or minimum possible cardinality of a collection of finite objects satisfying certain restrictions. These problems are often related to other areas including number theory, analysis, geometry, computer science and information theory. This branch of mathematics has developed spectacularly in the past several decades and many interesting open problems arose from it. In this dissertation, we discuss various problems in extremal combinatorics, as well as some related problems from other areas.This dissertation is organized in the way that each chapter studies a topic from extremal combinatorics, and includes its own introduction and concluding remarks. In Chapter 1 we study the relation between the chromatic number of a graph and its biclique partition, give a counterexample to the Alon-Saks-Seymour conjecture, and discuss related problems in theoretical computer science. Chapter 2 focuses on a conjecture on minimizing the number of nonnegative k-sums. Our approach naturally leads to an old conjecture by Erdos on hypergraph matchings. In Chapter 3, we improve the range that this conjecture is known to be true. Chapter 4 studies the connection of the Erdos conjecture with determining the minimum d-degree condition which guarantees the existence of perfect matching in hypergraphs. In Chapter 5, we study some extremal problems for Eulerian digraphs and obtain several results about existence of short cycles, long cycles, and subgraph with large minimum degree. The last chapter includes a proof that certain graph cut properties are quasi-random.
Subjects/Keywords: Mathematics; coloring; combinatorics; extremal; hypergraph; matching; probability
…Extremal problems in Eulerian digraphs . . . . . . . . . . . . . . . . . . . .
68
5.1… …89
6.2.1
Extremal Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . .
90… …x28;with P. Loh and B. Sudakov), Combinatorics, Probability and Computing, 21… …the extremal example in the Erd˝
os-Ko-Rado theorem [30] which states that for n… …and the Erd˝
os-Ko-Rado theorem. When n ≥ 4k, the conjectured extremal example
is x1 = n − 1…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Huang, H. (2012). Various Problems in Extremal Combinatorics. (Thesis). UCLA. Retrieved from http://www.escholarship.org/uc/item/282049q8
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Huang, Hao. “Various Problems in Extremal Combinatorics.” 2012. Thesis, UCLA. Accessed March 09, 2021.
http://www.escholarship.org/uc/item/282049q8.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Huang, Hao. “Various Problems in Extremal Combinatorics.” 2012. Web. 09 Mar 2021.
Vancouver:
Huang H. Various Problems in Extremal Combinatorics. [Internet] [Thesis]. UCLA; 2012. [cited 2021 Mar 09].
Available from: http://www.escholarship.org/uc/item/282049q8.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Huang H. Various Problems in Extremal Combinatorics. [Thesis]. UCLA; 2012. Available from: http://www.escholarship.org/uc/item/282049q8
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
29.
Coregliano, Leonardo Nagami.
Flag algebras and tournaments.
Degree: Mestrado, Ciência da Computação, 2015, University of São Paulo
URL: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/
;
► Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of…
(more)
▼ Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences.
Alexander A. Razborov (2007) desenvolveu a teoria de álgebras de flags para calcular a densidade assintótica mínima de triângulos em um grafo em função de sua densidade de arestas. A teoria das álgebras de flags, contudo, pode ser usada para estudar densidades assintóticas de diversos objetos combinatórios. Nesta dissertação, apresentamos dois resultados originais obtidos na teoria de torneios através de técnicas de demonstração de álgebras de flags. O primeiro resultado compreende a minimização da densidade assintótica de torneios transitivos em uma sequência de torneios, a qual provamos ocorrer se e somente se a sequência é quase aleatória. Como subprodutos, obtemos também novas caracterizações de quase aleatoriedade e diversos outros elementos da álgebra de flags cuja densidade é minimizada se e somente se a sequência é quase aleatória. O segundo resultado compreende uma classe de propriedades equivalentes sobre uma sequência de torneios que chamamos de propriedades quase carrossel e que, de uma forma similar às propriedades quase aleatórias, forçam que a sequência convirja para um homomorfismo limite específico. Várias propriedades quase carrossel, quando comparadas às propriedades quase aleatórias, sugerem que sequências quase aleatórias e sequências quase carrossel estão o mais distantes possível umas das outras na classe de sequências quase balanceadas.
Advisors/Committee Members: Kohayakawa, Yoshiharu.
Subjects/Keywords: Álgebras de flags; Asymptotic combinatorics; Combinatória assintótica; Extremal problems; Flag algebra; Problemas extremais; Quase aleatório; Quasi-random; Torneios; Tournaments
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Coregliano, L. N. (2015). Flag algebras and tournaments. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/ ;
Chicago Manual of Style (16th Edition):
Coregliano, Leonardo Nagami. “Flag algebras and tournaments.” 2015. Masters Thesis, University of São Paulo. Accessed March 09, 2021.
http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/ ;.
MLA Handbook (7th Edition):
Coregliano, Leonardo Nagami. “Flag algebras and tournaments.” 2015. Web. 09 Mar 2021.
Vancouver:
Coregliano LN. Flag algebras and tournaments. [Internet] [Masters thesis]. University of São Paulo; 2015. [cited 2021 Mar 09].
Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/ ;.
Council of Science Editors:
Coregliano LN. Flag algebras and tournaments. [Masters Thesis]. University of São Paulo; 2015. Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12082015-093248/ ;
Vilnius University
30.
Dzindzalieta, Dainius.
Tiksliosios Bernulio tikimybių
nelygybės.
Degree: PhD, Mathematics, 2014, Vilnius University
URL: http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2014~D_20140512_103759-89684
;
► Disertacijos darbo tikslas – įrodyti universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi, kad jos yra tolygios pagal tam tikras…
(more)
▼ Disertacijos darbo tikslas – įrodyti
universalias tiksliąsias nelygybes atsitiktinių dydžių funkcijų
nukrypimo nuo vidurkio tikimybėms. Universalios nelygybės pažymi,
kad jos yra tolygios pagal tam tikras bendras skirstinių klases ir
pagal atsitiktinių dydžių kiekį, kartais ir pagal kitus parametrus.
Nelygybės vadinamos tiksliosiomis, jeigu pavyksta sukonstruoti
atsitiktinių dydžių seką, kuriai nelygybės virsta lygybėmis. Tokios
nelygybės labai naudingos, pavyzdžiui, draudimo matematikoje,
konstruojant efektyvius algoritmus. Disertaciją sudaro šeši
skyriai. Pirmasis skyrius yra įvadas, kuriame neformaliai
pristatomas disertacijoje tiriamas objektas, pateikiamas bendras
darbo aprašymas ir motyvacija. Detalesnė kitų autorių rezultatų
apžvalga pateikiama atskirai kiekviename skyriuje. Antrasis skyrius
skirtas atvejui, kai atsitiktiniai dydžiai yra aprėžti ir
simetriniai. Trečiajame skyriuje įrodomos nelygybės atsitiktiniams
dydžiams, tenkinantiems dispersijos aprėžtumo sąlygą. Ketvirtajame
skyriuje nagrinėjamos sąlyginai aprėžtų atsitiktinių dydžių sumos.
Penktajame skyriuje tiriamos atsitiktinių dydžių sekos, sudarančios
martingalą arba supermartingalą, ir joms gaunamos universaliosios
tikimybinės nelygybės ir sukonstruojama nehomogeninė Markovo
grandinė, kuri yra martingalas, ir kuriai minėtos nelygybės virsta
lygybėmis. Šeštajame skyriuje rezultatai yra apibendrinami
atsitiktinių dydžių sekos Lipšico
funkcijoms.
The purpose of the dissertation is to prove
universal tight bounds for deviation from the mean probability
inequalities for functions of random variables. Universal bounds
shows that they are uniform with respect to some class of
distributions and quantity of variables and other parameters. The
bounds are called tight, if we can construct a sequence of random
variables, such that the upper bounds are achieved. Such
inequalities are useful for example in insurance mathematics, for
constructing effective algorithms. We extend the results for
Lipschitz functions on general probability metric
spaces.
Advisors/Committee Members: KUBILIUS, KĘSTUTIS (Doctoral dissertation committee chair), DUČINSKAS, KĘSTUTIS (Doctoral dissertation committee member), PAULAUSKAS, VYGANTAS (Doctoral dissertation committee member), SURGAILIS, DONATAS (Doctoral dissertation committee member), ŠIAUČIŪNAS, DARIUS (Doctoral dissertation committee member), BIKELIS, ALGIMANTAS JONAS (Doctoral dissertation opponent), RADAVIČIUS, MARIJUS (Doctoral dissertation opponent).
Subjects/Keywords: Nepriklausomi atsitiktiniai
dydžiai; Uodegų
tikimybės; Lipšico
funkcijos; Martingalai; Ekstremali
kombinatorika; Random
variables; Tail
probabilities; Martingales; Lipschitz
functions; Extremal
combinatorics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dzindzalieta, D. (2014). Tiksliosios Bernulio tikimybių
nelygybės. (Doctoral Dissertation). Vilnius University. Retrieved from http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2014~D_20140512_103759-89684 ;
Chicago Manual of Style (16th Edition):
Dzindzalieta, Dainius. “Tiksliosios Bernulio tikimybių
nelygybės.” 2014. Doctoral Dissertation, Vilnius University. Accessed March 09, 2021.
http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2014~D_20140512_103759-89684 ;.
MLA Handbook (7th Edition):
Dzindzalieta, Dainius. “Tiksliosios Bernulio tikimybių
nelygybės.” 2014. Web. 09 Mar 2021.
Vancouver:
Dzindzalieta D. Tiksliosios Bernulio tikimybių
nelygybės. [Internet] [Doctoral dissertation]. Vilnius University; 2014. [cited 2021 Mar 09].
Available from: http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2014~D_20140512_103759-89684 ;.
Council of Science Editors:
Dzindzalieta D. Tiksliosios Bernulio tikimybių
nelygybės. [Doctoral Dissertation]. Vilnius University; 2014. Available from: http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2014~D_20140512_103759-89684 ;
◁ [1] [2] ▶
. 
Open Access Theses and Dissertations
