Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T19:39:20.699Z Has data issue: false hasContentIssue false
  • English
  • Français

The Largest Minimum Codegree of a 3-Graph Without a Generalized 4-Cycle

Published online by Cambridge University Press:  19 October 2012

EDWARD MARCHANT
EDWARD MARCHANT*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: ejmarchant@gmail.com)
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.

A 3-graph is said to contain a generalized 4-cycle if it contains 4 edges A, B, C, D such that A ∩ B=C ∩ D =∅ and A ∪ B=C ∪ D. We show that a 3-graph in which every pair of vertices is contained in at least 4 edges must contain a generalized 4-cycle. When the number of vertices, n, is equivalent to 1 or 5 modulo 20, this result is optimum, in the sense that for such n there are 3-graphs where every pair of vertices is contained in 3 edges but which do not contain a generalized 4-cycle.

Keywords

Primary 05C65Secondary 05C35

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 1 , January 2013 , pp. 112 - 117
Copyright
Copyright © Cambridge University Press 2012

References

[1]Erdős, P. (1977) Problems and results in combinatorial analysis. In Proc. Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congress. Numer. 19 3–12.Google Scholar
[2]Erdős, P., Rényi, A. and Sós, V. T. (1966) On a problem of graph theory. Studia Sci. Math. Hungar 1 215–235.Google Scholar
[3]Füredi, Z. (1983) Graphs without quadrilaterals. J. Combin. Theory Ser. B 34 187–190.Google Scholar
[4]Füredi, Z. (1984) Hypergraphs in which all disjoint pairs have distinct unions. Combinatorica 4 161–168.Google Scholar
[5]Hanani, H. (1961) The existence and construction of balanced incomplete block designs. Ann. Math. Statist. 32 361–386.Google Scholar
[6]Hanani, H. (1965) A balanced incomplete block design. Ann. Math. Statist. 36 711–711.Google Scholar
[7]Mubayi, D. (2002) Some exact results and new asymptotics for hypergraph Turán numbers. Combin. Probab. Comput. 11 299–309.Google Scholar
[8]Pikhurko, O. and Verstraëte, J. (2009) The maximum size of hypergraphs without generalized 4-cycles. J. Combin. Theory Ser. A 116 637–649.Google Scholar