Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T07:39:57.248Z Has data issue: false hasContentIssue false
  • English
  • Français

The Turán Number of F3,3

Published online by Cambridge University Press:  29 November 2011

PETER KEEVASH and
DHRUV MUBAYI
PETER KEEVASH
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: p.keevash@qmul.ac.uk)
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: mubayi@math.uic.edu)
Rights & Permissions [Opens in a new window]

Abstract

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.

Let F3,3 be the 3-graph on 6 vertices, labelled abcxyz, and 10 edges, one of which is abc, and the other 9 of which are all triples that contain 1 vertex from abc and 2 vertices from xyz. We show that for all n ≥ 6, the maximum number of edges in an F3,3-free 3-graph on n vertices is $\binom{n}{3} - \binom{\lfloor n/2 \rfloor}{3} - \binom{\lceil n/2 \rceil}{3}$. This sharpens results of Zhou [9] and of the second author and Rödl [7].

Keywords

Primary 05C3505C65

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 3 , May 2012, pp. 451 - 456
Copyright
Copyright © Cambridge University Press 2011

References

[1]Bondy, A. and Tuza, Z. (1997) A weighted generalization of Turán's theorem. J. Graph Theory 25 267–275.3.0.CO;2-I>CrossRefGoogle Scholar
[2]de Caen, D. and Füredi, Z. (2000) The maximum size of 3-uniform hypergraphs not containing a Fano plane. J. Combin. Theory Ser. B 78 274–276.CrossRefGoogle Scholar
[3]Füredi, Z. and Kündgen, A. (2002) Turán problems for integer-weighted graphs. J. Graph Theory 40 195–225.CrossRefGoogle Scholar
[4]Goldwasser, J. On the Turán number of {123,124,345}. Manuscript.Google Scholar
[5]Keevash, P. (2011) Hypergraph Turán problems. Surveys in Combinatorics 2011, to appear.CrossRefGoogle Scholar
[6]Keevash, P. and Mubayi, D. (2004) Stability theorems for cancellative hypergraphs. J. Combin. Theory Ser. B 92 163–175.CrossRefGoogle Scholar
[7]Mubayi, D. and Rödl, V. (2002) On the Turán number of triple systems. J. Combin. Theory Ser. A 100 136–152.CrossRefGoogle Scholar
[8]Turán, P. (1961) Research problem. Közl MTA Mat. Kutató Int. 6 417–423.Google Scholar
[9]Zhou, B. (1991) A Turán-type problem on 3-graphs. Ars Combin. 31 177–181.Google Scholar