Hypergraph Turán Problems for Daisies

  • Dylan A King

Student thesis: Master's ThesisMaster of Science by Research (MScR)


Starting with Willem Mantel in 1907 and continuing with the work of Turan and Erd os in the mid-twentieth century, the extremal properties of graphs (or hypergraphs) avoiding a fixed subgraph (or subhypergraph) have been extensively studied, up to the present day. This is the field of so-called ‘Turan problems’; it has had much impact on other areas of Mathematics, such as number theory and geometry, as well as on combinatorics and theoretical computer science.
The classical ‘Turan problem’ for a fixed r-uniform hypergraph F is the following: for
each positive integer n, what is the maximum number ex(n, F ) of edges we may take in a r-
uniform hypergraph H on n vertices that contains no copy of F? The limit of ex(n, F )/(n choose r)
as n tends to infinity is called the Turan density of F, and is usually denoted by π(F).
In this thesis we study a natural and important class of Tur ́an problems for hypergraphs, posed by Bollobas, Leader and Malvenuto, and independently by Johnson and Talbot and (again independently) by Bukh. For integers r ≥ 3 and t ≥ 2, we define an r-uniform t-daisy Drt and consider the Turan problem for F = Drt. The exact value of π(Drt) is not known for any t ≥ 2,r ≥ 3. It was conjectured by Bollobas, Leader and Malvenuto in [3] (and independently by Bukh; an equivalent conjecture was made independently by Johnson and Talbot) that the Turan densities of t-daisies satisfy lim π(Drt ) = 0 for all t ≥ 2; this is still open for r→∞ and all values of t. We give lower bounds for the Turan densities of r-uniform t-daisies, im-
proving the best known lower bound from exponential to polynomial in r.
Date of Award27 Sept 2022
Original languageEnglish
Awarding Institution
  • University of Bristol
SupervisorDavid C Ellis (Supervisor)

Cite this