Sanitt, Adam; (2017) Turán problems in graphs and hypergraphs. Doctoral thesis , UCL (University College London).

Preview

Text final-thesis.pdf Download (1MB) | Preview

Abstract

Mantel's theorem says that among all triangle-free graphs of a given order the balanced complete bipartite graph is the unique graph of maximum size. In Chapter 2, we prove an analogue of this result for 3-graphs (3-uniform hy¬pergraphs) together with an associated stability result. Let K− 4 , F5 and F6 be 3-graphs with vertex sets {1, 2,3, 4}, {1, 2,3,4, 5} and {1, 2,3,4, 5, 6} re¬spectively and edge sets E(K−4 ) = {123, 124, 134}, E(F5) = {123, 124, 345}, E(F6) = {123, 124,345, 156} and F = {K4, F6}. For n =6 5 the unique F-free 3-graph of order n and maximum size is the balanced complete tri¬partite 3-graph S3(n). This extends an old result of Bollobas that S3(n) is the unique 3-graph of maximum size with no copy of K− 4 or F5. In 1941, Turán generalised Mantel's theorem to cliques of arbitrary size and then asked whether similar results could be obtained for cliques on hyper-graphs. This has become one of the central unsolved problems in the field of extremal combinatorics. In Chapter 3, we prove that the Turán density of K(3) 5 together with six other induced subgraphs is 3/4. This is analogous to a similar result obtained for K(3) 4 by Razborov. In Chapter 4, we consider various generalisations of the Turán density. For example, we prove that, if the density in C of ¯P3 is x and C is K3-free, then |E(C)| /(n ) ≤ 1/4+(1/4)J1 − (8/3)x. This is motivated by the observation 2 that the extremal graph for K3 is ¯P3-free, so that the upper bound is a natural extension of a stability result for K3. The question how many edges can be deleted from a blow-up of H before it is H-free subject to the constraint that the same proportion of edges are deleted from each connected pair of vertex sets has become known as the Turán density problem. In Chapter 5, using entropy compression supplemented with some analytic methods, we derive an upper bound of 1 − 1/('y(Δ(H) − /3)), where Δ(H) is the maximum degree of H, 3 ≤ 'y < 4 and /3 ≤ 1. The new bound asymptotically approaches the existing best upper bound despite being derived in a completely different way. The techniques used in these results, illustrating their breadth and connec¬tions between them, are set out in Chapter 1.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item