Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650623 | Discrete Mathematics | 2006 | 11 Pages |
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.