Recent results on some not-so-recent hypergraph matching and covering problems. (English) Zbl 0820.05050

Kahn, J.

Frankl, P. (ed.) et al., Extremal problems for finite sets. Proceedings of the conference, held in Visegrád, Hungary between June 16-21, 1991. Budapest: János Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 3, 305-353 (1994).

The author discusses several partial results obtained on four inter- related combinatorial problems on hypergraphs and a common strategy employed in getting some of these asymptotic results. The problems are
(1) The Erdős-Faber-Lovász conjecture: Any nearly disjoint hypergraph \({\mathcal H}\) on \(n\) vertices has chromatic index at most \(n\).
(2) The Erdős-Lovász problem: For positive integers \(r\), estimate \(n(r) = \min \{| {\mathcal H} | : {\mathcal H}\) a \(r\)-uniform intersecting hypergraph with vertex covering number \(\tau ({\mathcal H}) = r\}\). Is it true that \(n(r)/r \to \infty\) as \(r \to \infty\)?
(3) The Meyer problem: For positive integers \(r\), estimate \(m(r) = \min \{| {\mathcal H}|: {\mathcal H}\) a maximal intersecting \(r\)-uniform hypergraph}.
(4) List colouring index \(\chi_ \ell'\) of graphs and hypergraphs:
Conjecture 1: For every multigraph \(G\), we have \(\chi_ \ell' (G) = \chi' (G)\) (the chromatic index).
Conjecture 2 (Dinitz): For \(1 \leq i\), \(j \leq n\), let \(S_{i,j}\) be a set of size \(n\). Then there is a partial Latin square \((a_{ij})_{1 \leq i,j \leq n}\) with \(a_{ij} \in S_{ij}\) for all \(i\) and \(j\).
The author presents several results on the above and discusses a common proof technique employed in these. We quote only two asymptotic results:
Theorem 1: Let \(k\) be fixed and \({\mathcal H}\) a \(k\)-uniform hypergraph satisfying \(| d(x) - D({\mathcal H}) | < o (D({\mathcal H}))\) for all vertices \(x\), and \(d(x,y) < o(D({\mathcal H}))\) for all distinct vertices \(x,y\). Then \(\nu ({\mathcal H}) \sim n/k \sim \rho ({\mathcal H})\), where \(\nu ({\mathcal H})\) and \(\rho ({\mathcal H})\) are the matching number and edge- covering number of \({\mathcal H}\), respectively.
Theorem 2: Under the hypothesis of Theorem 1, \(\chi' ({\mathcal H}) \sim D ({\mathcal H}) \sim \varphi ({\mathcal H})\), where \(\varphi ({\mathcal H})\) is the smallest size of a collection of covers whose union is \({\mathcal H}\).
The proof technique employs an algorithmic (recursive) procedure of generating the desired covers or matchings involving a finite number of stages of random selection of objects satisfying appropriate criteria and a final stage of greedy selection. In order to show that the actual behaviour of the process stays close to the expected behaviour, martingale theory is used.
For the entire collection see [Zbl 0809.00013].

Reviewer: K.R.Parthasarathy (Narayanapuram)

MSC:

05C65	Hypergraphs
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05D05	Extremal set theory
60C05	Combinatorial probability
05C35	Extremal problems in graph theory
05B15	Orthogonal arrays, Latin squares, Room squares

Keywords:

\(r\)-uniform intersecting hypergraph; hypergraphs; chromatic index; Latin square; matching number; edge-covering number; covers; matchings