The Library
Analytic methods in combinatorics
Tools
Volec, Jan (2014) Analytic methods in combinatorics. PhD thesis, University of Warwick.
|
PDF
WRAP_THESIS_Volec_2014.pdf - Submitted Version - Requires a PDF viewer. Download (4Mb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2817335~S1
Abstract
In the thesis, we apply the methods from the recently emerged theory of limits of discrete structures to problems in extremal combinatorics. The main tool we use is the framework of flag algebras developed by Razborov.
We determine the minimum threshold d that guarantees a 3-uniform hypergraph to contain four vertices which span at least three edges, if every linear-size subhypergraph of the hypergraph has density more than d. We prove that the threshold value d is equal to 1=4. The extremal configuration corresponds to the set of cyclically oriented triangles in a random orientation of a complete graph. This answers a question raised by Erdos.
We also use the flag algebra framework to answer two questions from the extremal theory of permutations. We show that the minimum density of monotone subsequences of length five in any permutation is asymptotically equal to 1=256, and that the minimum density of monotone subsequences of length six is asymptotically equal to 1=3125. Furthermore, we characterize the set of (suffciently large) extremal configurations for these two problems. Both the values and the characterizations of extremal configurations were conjectured by Myers.
Flag algebras are also closely related to the theory of dense graph limits, where the main objects of study are convergent sequences of graphs. Such a sequence can be assigned an analytic object called a graphon. In this thesis, we focus on finitely forcible graphons. Those are graphons determined by finitely many subgraph densities. We construct a finitely forcible graphon such that the topological space of its typical vertices is not compact. In our construction, the space even fails to be locally compact. This disproves a conjecture of Lovasz and Szegedy.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Combinatorial probabilities | ||||
Official Date: | September 2014 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Extent: | vi, 101 leaves : illustrations (black and white) | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year