on%20even-degree%20subgraphs_e.pdf (232.81 kB)
On Even-Degree Subgraphs of Linear Hypergraphs
journal contribution
posted on 2013-11-05, 00:00 authored by Domingos Jr Dellamonica, Penny E. Haxell, Tomasz Łuczak, Dhruv Muyabi, Brendan Nagle, Yury Person, Vojtech Rödl, Mathias Schacht, Jacques VerstraëteA 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 f(b)(n) denote the maximum number of edges in a linear n-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b >= 12, then
n log n/3b log log n <= f(b)(n) <= Bn(log n)(2)
for some absolute constant B, thus establishing f(b)(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
cn log n <= f2( n) <= Cn(3/2)(log n)(5).
We conjecture that f(2)(n) = n(1+o(1)) as n -> infinity.
History
Publisher Statement
This is a copy of an article published in the Combinatorics, Probability and Computing © 2012 Cambridge University Press. Available at http://journals.cambridge.org/abstract_S0963548311000575Publisher
Cambridge University PressLanguage
- en_US
issn
0963-5483Issue date
2012-03-01Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC