Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-12T04:20:22.709Z Has data issue: false hasContentIssue false
  • English
  • Français

Daisies and Other Turán Problems

Published online by Cambridge University Press:  18 August 2011

BÉLA BOLLOBÁS ,
IMRE LEADER  and
CLAUDIA MALVENUTO
BÉLA BOLLOBÁS
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: b.bollobas@dpmms.cam.ac.uk) Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: i.leader@dpmms.cam.ac.uk)
IMRE LEADER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: i.leader@dpmms.cam.ac.uk)
CLAUDIA MALVENUTO
Affiliation:
Dipartimento di Informatica, Sapienza – Università di Roma, Via Salaria 113, 00198 Roma, Italy (e-mail: claudia@di.uniroma1.it)
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Our aim in this note is to make some conjectures about extremal densities of daisy-free families, where a ‘daisy’ is a certain hypergraph. These questions turn out to be related to some Turán problems in the hypercube, but they are also natural in their own right. We start by giving the daisy conjectures, and some related problems, and shall then go on to describe the connection with vertex-Turán problems in the hypercube.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 5 , September 2011 , pp. 743 - 747
Copyright
Copyright © Cambridge University Press 2011

References

[1]Alon, N., Krech, A. and Szabó, T. (2007) Turán's theorem in the hypercube. SIAM J. Discrete Math. 21 66–72.CrossRefGoogle Scholar
[2]Bollobás, B. (1986) Combinatorics, Cambridge University Press.Google Scholar
[3]Bukh, B. (2011) Personal communication.Google Scholar
[4]Erdős, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 459–464.CrossRefGoogle Scholar
[5]Goldwasser, J. (2011) Personal communication.Google Scholar
[6]Johnson, J. R. and Talbot, J. (2010) Vertex Turán problems in the hypercube. J. Combin. Theory Ser. A 117 454–465.CrossRefGoogle Scholar
[7]Johnson, K. A. and Entringer, R. (1989) Largest induced subgraphs of the n-cube that contain no 4-cycles. J. Combin. Theory Ser. B 46 346–355.CrossRefGoogle Scholar
[8]Keevash, P. Hypergraph Turán problems. In Surveys in Combinatorics 2011, Cambridge University Press, pp. 83–139.Google Scholar
[9]Kostochka, E. A. (1976) Piercing the edges of the n-dimensional unit cube (in Russian). Diskret. Analiz Vyp. 28 Metody Diskretnogo Analiza v Teorii Grafov i Logiceskih Funkcii 55–64.Google Scholar
[10]Sidorenko, A. (1995) What we know and what we do not know about Turán numbers. Graphs Combin. 11 179–199.CrossRefGoogle Scholar