On Even-Degree Subgraphs of Linear Hypergraphs
Dellamonica, Domingos Jr
Haxell, Penny E.
PublisherCambridge University Press
MetadataShow full item record
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 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.