Abstract by
Zoltan Furedi
UIUC
Maximal $\tau$-critical linear hypergraphs.
A construction using finite affine geometries is given to show that the maximum number of edges in a t-critical linear hypergraph is (1-o(1))t2. This asymptotically answers a question of Roudnef, Aharoni and Ziv. Erdos, Hajnal, and Moon earlier solved the problem for the restriction to graphs. Over this smaller family, the proved that every t-critical graph has at most t(t+1)/2 edges, with equality holding only for the complete graph on t+1 vertices. Definitions: A hypergraph consists of a vertex set and a family of subsets of the vertex set called edges. In a linear hypergraph, every two edges have at most one common vertex (generalizing the notion of simple graph). A cover (or transversal) of a hypergraph is a set of vertices intersecting every edge. The minimum size of a cover of H is its covering number, denoted by t(H). A hypergraph is t-critical if omitting one edge always reduces its covering number.

Tuesday, November 30, 1999, 12:00 p.m.  - 241 Altgeld Hall
GRAPH THEORY AND COMBINATORICS

Go Back