کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650623 | 1632449 | 2006 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Odd cycles and ΘΘ-cycles in hypergraphs Odd cycles and ΘΘ-cycles in hypergraphs](/preview/png/4650623.png)
A ΘΘ-cycle of a hypergraph is a cycle including an edge that contains at least three base points of the cycle. We show that if a hypergraph H=(V,E)H=(V,E) has no ΘΘ-cycle, and |e|⩾3|e|⩾3, for every edge e∈Ee∈E, then ∑e∈E(|e|-1)⩽2|V|-2∑e∈E(|e|-1)⩽2|V|-2 with equality if and only if H is obtained from a hypertree by doubling its edges.This result reminiscent of Berge's and Lovász's similar inequalities implies that 3-uniform hypergraphs with n vertices and n edges have ΘΘ-cycles, and 3-uniform simple hypergraphs with n vertices and n-1n-1 edges have ΘΘ-cycles. Both results are sharp. Since the presence of a ΘΘ-cycle implies the presence of an odd cycle, both results are sharp for odd cycles as well. However, for linear 3-uniform hypergraphs the thresholds are different for ΘΘ-cycles and for odd cycles. Linear 3-uniform hypergraphs with n vertices and with minimum degree two have ΘΘ-cycles when |E|⩾5n/6-c1n and have odd cycles when |E|⩾7n/9-c2n and these are sharp results apart from the values of the constants.Most of our proofs use the concept of edge-critical (minimally 2-connected) graphs introduced by Dirac and by Plummer. In fact, the hypergraph results—in disguise—are extremal results for bipartite graphs that have no cycles with chords.
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2481–2491