Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: English
Types: Doctoral thesis
Subjects: QA
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.\ud \ud 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.\ud \ud 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.\ud \ud 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [60] Alexander A. Razborov. On the minimal density of triangles in graphs. Combin. Probab. Comput., 17:603{618, 7 2008.
    • [61] Alexander A. Razborov. On 3-hypergraphs with forbidden 4-vertex con gurations. SIAM J. Discrete Math., 24(3):946{963, 2010.
    • [62] Alexander A. Razborov. Flag Algebras: An Interim Report. In The Mathematics of Paul Erdo}s II, pages 207{232. Springer, 2013.
    • [63] Alexander A. Razborov. On the Caccetta-Haggkvist conjecture with forbidden subgraphs. J. Graph Theory, 74(2):236{248, 2013.
    • [64] Christian Reiher. The clique density theorem. Submitted; E-print available at arXiv:1212.2454.
    • [65] Vojtech Rodl. On universality of graphs with uniformly distributed edges. Discrete Math., 59(1{2):125{134, 1986.
    • [66] Vojtech Rodl and Mathias Schacht. Generalizations of the removal lemma. Combinatorica, 29(4):467{501, 2009.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article