Some results in extremal combinatorics
2011
In Chapter 1 we determine the minimal density of triangles in a tripartite graph with prescribed edge densities. This extends work of Bondy, Shen, Thomasse and Thomassen characterizing those edge densities guaranteeing the existence of a triangle in a tripartite graph. We also determine those edge densities guaranteeing a copy of a triangle or C5 in a tripartite graph.
In Chapter 2 we describe Razborov's flag algebra method and apply this to Erdos' jumping hypergraph problem to find the first non-trivial regions of jumps. We also use Razborov's method to prove five new sharp Turan densities,
by looking at six vertex 3-graphs which are edge minimal and not 2-colourable.
We extend Razborov's method to hypercubes. This allows us to significantly improve the upper bound given by Thomason and Wagner on the number of edges in a C4-free subgraph of the hypercube. We also show that the vertex
Turan density of a 3-cube with a single vertex removed is precisely 3/4.
In Chapter 3 we look at problems for intersecting families of sets on graphs.
We give a new bound for the size of G-intersecting families on a cycle, disproving a conjecture of Johnson and Talbot. We also extend this result to cross-intersecting families and to powers of cycles.
Finally in Chapter 4 we disprove a conjecture of Hurlbert and Kamat that
the largest trivial intersecting family of independent r-sets from the vertex set
of a tree is centred on a leaf.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
24
Citations
NaN
KQI