Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T06:57:37.952Z Has data issue: false hasContentIssue false
  • English
  • Français

On Even-Degree Subgraphs of Linear Hypergraphs

Published online by Cambridge University Press:  02 February 2012

D. DELLAMONICA Jr. ,
P. HAXELL ,
T. ŁUCZAK ,
D. MUBAYI ,
B. NAGLE ,
Y. PERSON ,
V. RÖDL ,
M. SCHACHT  and
J. VERSTRAËTE
D. DELLAMONICA Jr.
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: ddellam@mathcs.emory.edu, rodl@mathcs.emory.edu)
P. HAXELL
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada (e-mail: pehaxell@math.uwaterloo.ca)
T. ŁUCZAK
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: ddellam@mathcs.emory.edu, rodl@mathcs.emory.edu) Department of Discrete Mathematics, Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland (e-mail: tomasz@amu.edu.pl)
D. MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA (e-mail: mubayi@math.uic.edu)
B. NAGLE
Affiliation:
Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA (e-mail: bnagle@math.usf.edu)
Y. PERSON
Affiliation:
Institute of Mathematics, Freie Universität Berlin, 14195 Berlin, Germany (e-mail: person@math.fu-berlin.de)
V. RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: ddellam@mathcs.emory.edu, rodl@mathcs.emory.edu)
M. SCHACHT
Affiliation:
Fachbereich Mathematik, Universität Hamburg, Bundesstraße 55, D-20146 Hamburg, Germany (e-mail: schacht@math.uni-hamburg.de)
J. VERSTRAËTE
Affiliation:
Department of Mathematics, University of California, San Diego (UCSD), La Jolla, CA 92093-0112, USA (e-mail: jacques@ucsd.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.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then \[ \frac{n \log n}{3 b\log \log n} \leq f_b(n) \leq Bn(\log n)^2 \] for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that \[ c n\log n \leq f_2(n) \leq Cn^{3/2}(\log n)^5. \] We conjecture that f2(n) = n1 + o(1) as n → ∞.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 113 - 127
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N., Friedland, S. and Kalai, G. (1984) Regular subgraphs of almost regular graphs. J. Combin. Theory Ser. B 37 79–91.CrossRefGoogle Scholar
[2]Feige, U. (2008) Small linear dependencies for binary vectors of low weight. In Building Bridges: Between Mathematics and Computer Science, Vol. 19 of Bolyai Society Mathematical Studies, Springer, pp. 283–307.CrossRefGoogle Scholar
[3]Frankl, P. and Rödl, V. (1985) Near perfect coverings in graphs and hypergraphs. European J. Combin. 6 317–326.CrossRefGoogle Scholar
[4]Lazebnik, F. and Ustimenko, V. A. (1995) Explicit construction of graphs with an arbitrary large girth and of large size. Discrete Appl. Math. 60 275–284.CrossRefGoogle Scholar
[5]Lovász, L. Personal communication.Google Scholar
[6]Mubayi, D. and Verstraëte, J. (2009) Two-regular subgraphs of hypergraphs. J. Combin. Theory Ser. B 99 643–655.CrossRefGoogle Scholar
[7]Naor, A. and Verstraëte, J. (2008) Parity check matrices and product representations of squares. Combinatorica 28 163–185.CrossRefGoogle Scholar
[8]Pyber, L., Rödl, V. and Szemerédi, E. (1995) Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63 41–54.CrossRefGoogle Scholar