Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T15:10:08.139Z 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: [email protected]) Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])
IMRE LEADER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])
CLAUDIA MALVENUTO
Affiliation:
Dipartimento di Informatica, Sapienza – Università di Roma, Via Salaria 113, 00198 Roma, Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Extract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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