Abstract | ||
---|---|---|
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 â聠聮 ∞. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1017/S0963548311000575 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
interesting case,linear hypergraphs,maximum degree,leq bn,hypergraph h,leq f_2,leq cn,maximum number,3-uniform hypergraph,log n,even-degree subgraphs,leq f_b | Integer,Discrete mathematics,Binary logarithm,Combinatorics,Constraint graph,Hypergraph,Degree (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1-2 | 0963-5483 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
9 |
Name | Order | Citations | PageRank |
---|---|---|---|
Domingos Dellamonica | 1 | 4 | 0.77 |
P. E. Haxell | 2 | 212 | 26.40 |
T. Łuczak | 3 | 124 | 13.68 |
Dhruv Mubayi | 4 | 579 | 73.95 |
B. Nagle | 5 | 10 | 1.64 |
Yury Person | 6 | 118 | 19.19 |
V. Rödl | 7 | 750 | 131.81 |
Mathias Schacht | 8 | 361 | 37.90 |
J. Verstraëte | 9 | 0 | 0.34 |