Daisy, a hypergraph and other Turán problems in the hypercube are studied. A daisy, or r-daisy, is a certain r-uniform hypergraph consisting of six sets. Given an (r - 2)-set P and a 4-set Q disjoint from P, the daisy on (P,Q) consists of the r-sets A with P ⊂ A ⊂ P ∪ Q. A beautiful conjecture of Johnson and Talbot is proposed, about meeting d-cubes in several points, that is also closely tied to daisy problems. They conjecture that if there is a positive fraction of the vertices of the n-cube then (for n sufficiently large) there must be some d-cube containing the least points of the family.
Daisies and Other Turan Problems / Malvenuto, Claudia; I., Leader; B., Bollobas. - In: COMBINATORICS PROBABILITY & COMPUTING. - ISSN 0963-5483. - STAMPA. - 20:5(2011), pp. 743-747. [10.1017/s0963548311000319]
Daisies and Other Turan Problems
MALVENUTO, Claudia;
2011
Abstract
Daisy, a hypergraph and other Turán problems in the hypercube are studied. A daisy, or r-daisy, is a certain r-uniform hypergraph consisting of six sets. Given an (r - 2)-set P and a 4-set Q disjoint from P, the daisy on (P,Q) consists of the r-sets A with P ⊂ A ⊂ P ∪ Q. A beautiful conjecture of Johnson and Talbot is proposed, about meeting d-cubes in several points, that is also closely tied to daisy problems. They conjecture that if there is a positive fraction of the vertices of the n-cube then (for n sufficiently large) there must be some d-cube containing the least points of the family.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.