Talbot, John Mark; (2001) Lagrangians of hypergraphs and other combinatorial results. Doctoral thesis (Ph.D), UCL (University College London).

Text Lagrangians_of_hypergraphs_and.pdf Download (2MB)

Abstract

We consider two types of extremal problems for hypergraphs. In chapters two, three and four these are problems related to Lagrangians of hypergraphs. In the final chapter we examine a problem on intersecting families of sets. After giving an introduction to extremal problems for hypergraphs and Lagrangians in chapter one, we consider a question due to Frankl and Furedi. They asked how large the Lagrangian of an r-graph with m edges can be. We prove the first interesting case of their conjecture on this problem, namely that the 3-graph with (k3) edges and largest Lagrangian is k(3). We also prove a result for general r-graphs: for k sufficiently large, the r-graph supported on k + 1 vertices with (kr) edges and largest Lagrangian is k(r). In the third chapter we consider Erdos jumping constant conjecture and give a new result on values which are not jumps for hypergraphs. We also discuss an unresolved case of this conjecture which is of particular interest. Our main result in chapter four is a bound for a Turan-type problem related to Erdos jumping constant conjecture. We also review Turans original problem and the use of Lagrangians in this context. In the final chapter we consider a problem due to Holroyd and Johnson on intersecting families of separated sets. Our main result here is a new version of the Erdos-Ko-Rado theorem for weighted separated sets.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as CSVJSONXML

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item