
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