On even-degree subgraphs of linear hypergraphs

Link:

Autor/in:

Erscheinungsjahr:

2012

Medientyp:

Text

Schlagworte:

Beschreibung:

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.
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/3 b log log n≤ f b(n)≤ 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 cn log n ≤ f 2(n) ≤ Cn 3/2(log n) 5. We conjecture that f 2(n) = n 1 + o(1) as n → ∞. © 2012 Cambridge University Press.

Lizenz:

Quellsystem:

Forschungsinformationssystem der UHH

Interne Metadaten

Quelldatensatz: oai:www.edit.fis.uni-hamburg.de:publications/29975bc3-4dc3-4628-bda4-aec529c99ba1