On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings

Abstract

This article summarizes progress on several old hypergraph problems of Paul Erdős and a few questions to which they led. Quite unexpectedly, there turned out to be substantial connections between the problems under discussion, surely some indication (if any were needed) that Erdős’ questions were the “right” ones. Here’s a quick synopsis.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

This article summarizes progress on several old hypergraph problems of Paul Erdős and a few questions to which they led. Quite unexpectedly, there turned out to be substantial connections between the problems under discussion, surely some indication (if any were needed) that Erdős’ questions were the “right” ones. Here’s a quick synopsis.

The story basically begins about 10 years ago, with Vojta Rödl’s beautiful proof [80] of the “Erdős-Hanani” Conjecture (Sect. 4). His proof was based on a powerful “semirandom” or “guided-random” approach. (I wish there were a better name for this.) A similar method had earlier been used in a less precise context by Ajtai, Komlós and Szemerédi [1] and Komlós, Pintz and Szemerédi [70]. Substantial extensions of Rödl’s work were subsequently achieved by Frankl and Rödl [38], Pippenger (see [87] or [42]), and Pippenger and Spencer [77] (see Sects. 4 and 6).

Most of the work described in this paper had its beginnings in attempts to apply these ideas to prove a nonlinear lower bound on the function n(r) of Erdős and Lovász discussed in Sect. 3. In the event, n(r) turned out to be linear, though discovering this would certainly not have been possible if the results of those initial attempts (see Sect. 5) had not suggested where—or at least where not—to look for examples.

In the meantime, an understanding of the above-mentioned results, particularly [77], had led to a proof of the “asymptotic correctness” of the well-known Erdős-Faber-Lovász Conjecture (Sect. 2), which proof led eventually to a much stronger result (Theorem 12) on the asymptotic behavior of the list-chromatic index for hypergraphs; and further efforts to prove n(r) ∕ r → ∞ had suggested the conjecture which eventually became the main result of Sect. 5. (Theorem 9), and led in its turn to the investigations mentioned in Sects. 7 and 8.

In this paper we mainly try to give an overview of these developments and connections, with discussion of proofs limited to hints at most. More detailed accounts of some of the material—especially more serious discussions of the semirandom method—may be found in [42] and [60]. (I should also say that various bits and pieces of this article are borrowed from [60–62].)

1.1 Terminology

Throughout we use $\mathcal{H}$ to denote a hypergraph on vertex set V ​​. For further hypergraph background see, e.g., [42] or [9].

The degree (in $\mathcal{H}$) of x ∈ V is the number of edges of $\mathcal{H}$ containing x, and is denoted $d_{\mathcal{H}}(x)$ or simply d(x). Similarly, d(x, y) denotes the number of edges containing both of the vertices x, y and d(X) the number of edges containing all vertices of $X \subseteq V$. We write $D(\mathcal{H})$ for the largest degree in $\mathcal{H}$. A hypergraph is D-regular if each of its vertices has degree D.

A hypergraph is intersecting, resp. simple (or nearly-disjoint, but we won’t use this), if any two of its edges have at least, resp. at most, one vertex in common.

For $X,Y \in \mathcal{H}\cup V$, the distance from X to Y, denoted $\Delta (X,Y )$, is the least m for which there exists a sequence $X = X_{0},\ldots,X_{m} = Y$ from $\mathcal{H}\cup V$ such that for each i, X _i − 1 is an element of X _i or vice versa.

A matching of $\mathcal{H}$ is a collection of pairwise disjoint edges, and the size of a largest such collection, denoted $\nu (\mathcal{H})$, is the matching number of $\mathcal{H}$. We write $\mathcal{M}(\mathcal{H})$ for the set of matchings of $\mathcal{H}$.

A vertex cover (clearer would be “cover of edges by vertices”) of $\mathcal{H}$ is a set of vertices meeting every edge of $\mathcal{H}$, while an edge cover is a collection of edges whose union is V. Either of these may be shortened to “cover” if there seems no danger of confusion. The vertex and edge cover numbers of $\mathcal{H}$ are the minimum sizes of its vertex and edge covers, and are denoted $\tau (\mathcal{H})$ and $\rho (\mathcal{H})$.

Each of ν, τ, ρ has a fractional counterpart, obtained by regarding the object in question as the solution of an integer program and taking the linear relaxation thereof. Thus a fractional (edge) cover—the only one of the three needed here—is a function $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$ satisfying

$$\displaystyle{ \sum _{A\ni x}t(A) \geq 1\quad \forall x \in V, }$$

(1)

and the fractional (edge) cover number is

$${\displaystyle{\rho }^{{\ast}}(\mathcal{H}) =\min \{\sum t(A) : t\ \mbox{ a fractional edge cover of }\mathcal{H}\}.}$$

We also say that $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$ is a fractional tiling if equality holds in (1).

The chromatic index (or edge coloring number) of $\mathcal{H}$, denoted $\chi ^{\prime}(\mathcal{H})$, is the least t for which there is a “coloring” $\sigma : \mathcal{H}\rightarrow [t]$ which is proper in the usual sense that σ(A)≠σ(B) whenever A, B are distinct, nondisjoint edges. Equivalently, $\chi ^{\prime}(\mathcal{H})$ is the least size of a collection of matchings whose union is $\mathcal{H}$. We also write $\phi (\mathcal{H})$ for the greatest size of a collection of pairwise disjoint covers contained in $\mathcal{H}$.

These too have fractional versions, of which we only need the fractional chromatic index of $\mathcal{H}$, denoted (unfortunately) ${\chi }^{{\prime}{\ast}}(\mathcal{H})$, and defined as the minimum value of

$$\displaystyle{\sum _{M\in \mathcal{M}}f(M)}$$

over $f : \mathcal{M}\rightarrow {\mathbf{R}}^{+}$ satisfying

$$\displaystyle{\sum _{A\in M\in \mathcal{M}}f(M) \geq 1\qquad \forall A \in \mathcal{H}.}$$

Finally we need to say a little about asymptotic notation. For nonnegative f, g we use f ∼ g and f ≲ g for “f ∕ g → 1” and “limsupf ∕ g ≤ 1”, with limits taken as some relevant parameter tends to infinity. We also write $f = _{\varepsilon }g$ for ${(1+\varepsilon )}^{-1} < f/g < 1+\varepsilon$. As usual we use f = O(g), f = o(g) and f = ω(g) for (respectively) sup(f ∕ g) < ∞, f ∕ g → 0 and f ∕ g → ∞.

We adopt the “uniformity convention” of [77], viz: any limiting statement involving one or more free variables ranging over vertices, edges or hypergraphs is understood to hold uniformly with respect to all possible choices of these variables, as some specified numerical parameter tends to infinity. (See Theorem 7 for a first instance of this.)

2 The Erdős-Faber-Lovász Conjecture

To avoid trivialities, hypergraphs in this section are assumed to have no singleton edges.

The celebrated Erdős-Faber-Lovász Conjecture may be stated as follows (see [53]):

Conjecture 1.

Any simple hypergraph $\mathcal{H}$ on n vertices has chromatic index at most n.

Erdős has for many years listed this as one of his “three favorite combinatorial problems” (the other two being the $\Delta$-system problem of Erdős and Rado, and the problem of Erdős and Lovász described in Sect. 3), and currently offers $500 for its resolution (see, e.g., [29]).

Notice first of all that the Conjecture is sharp in the case $\mathcal{H}$ is either

• (a) A projective plane or degenerate projective plane (the latter being the hypergraph with vertex set {0, 1, …, n − 1} and edge set $\{\{0,1\},\ldots,\{0,n - 1\},\{1,\ldots,n - 1\}\}$), or

• (b) A complete graph on n vertices, n odd.

(Sufficiently minor modifications of (b) also give equality.)

On the other hand:

• (c) For intersecting $\mathcal{H}$, Conjecture 1 is just the de Bruijn-Erdős Theorem [20], which says that if | A ∩ B |  = 1 for all distinct $A,B \in \mathcal{H}$, then $\vert \mathcal{H}\vert \leq n$ (with equality only for $\mathcal{H}$ as in (a)).

• (d) For graphs, Conjecture 1 is contained in Vizing’s Theorem [90] stating that the chromatic index of a simple graph of maximum degree D is at most D + 1. (Of course this special case—Vizing’s Theorem for complete graphs—is easily proved directly. On the other hand, as observed, e.g., by Meyniel (unpublished), Berge [10] and Füredi [41], it seems likely that the bound in Conjecture 1 can be replaced by max _x ∈ V  |  ∪ _A ∋ x A | , which for graphs reduces to Vizing’s Theorem in full.)

Graphs and intersecting hypergraphs are in some sense the extreme cases of Conjecture 1. One of the problem’s most appealing aspects is that it has proved so intractable despite being manageable at these extremes, and apparently less accurate between them.

2.1 Bounds

The history of results on Conjecture 1 is rather brief, surely more an indication of the difficulty of the problem than of any lack of attempts to resolve it. The first significant progress was made by P. Seymour, who showed

Theorem 1 ([84]). 

If $\mathcal{H}$ is simple on n vertices, then $\nu (\mathcal{H}) \geq \vert \mathcal{H}\vert /n$, with equality only in the cases (a) and (b).

Note this is immediate from Conjecture 1. An intermediate statement was conjectured in [84] and proved in [68]:

Theorem 2.

If $\mathcal{H}$ is simple on n vertices, then χ ^′∗ ≤ n.

Equivalently (by LP-duality),

$$\displaystyle\begin{array}{rcl} & & \forall f : \mathcal{H}\rightarrow {\mathbf{R}}^{+}\exists M \in \mathcal{M}(\mathcal{H})\mbox{ such that } \\ & & \qquad \qquad \qquad \qquad \qquad \sum \{f(A) : A \in M\} \geq {n}^{-1}\sum \{f(A) : A \in \mathcal{H}\}. {}\end{array}$$

(2)

(So taking f ≡ 1 we recover Theorem 1.) The proof of Theorem 2 turned out to be much simpler than that of Theorem 1 because it was possible to exploit properties of a worst f in (2).

It seems to have been noticed by several people that a greedy coloring of edges of $\mathcal{H}$ in any nonincreasing size order requires at most 2n − 3 colors. In the absence of edges of size 2 this bound shrinks to about 3n ∕ 2, and Chang and Lawler [21] showed how to modify the greedy procedure to achieve the same bound (precisely, $\chi ^{\prime}(\mathcal{H}) \leq \lceil 1.5n - 2\rceil$) in general. That Conjecture 1 is at least asymptotically correct was subsequently proved in [58]:

Theorem 3.

If $\mathcal{H}$ is simple on n vertices, then $\chi ^{\prime}(\mathcal{H}) < n + o(n)$.

The proof of this is based on the “semirandom” method discussed below (see especially Sect. 6), and actually gives $\chi ^{\prime}(\mathcal{H}) < (1 + o(1))\max _{x\in V }\vert \cup _{A\ni x}A\vert$ (c.f. (d) above).

2.2 Digression: Borsuk and Larman

There’s at least a formal similarity between Conjecture 1 and the following problem of Larman [73]. (A hypergraph is t-intersecting if any two of its edges share at least t vertices.)

Conjecture 2.

If $\mathcal{H}$ is a t-intersecting hypergraph on n vertices, then $\mathcal{H} = \mathcal{H}_{1} \cup \cdots \cup \mathcal{H}_{n}$ with each $\mathcal{H}_{i}$ (t + 1)-intersecting.

This is motivated by, and for uniform $\mathcal{H}$ is a special case of “Borsuk’s Conjecture” that every bounded set in ${\mathbf{R}}^{d}$ is the union of d + 1 sets of smaller diameter ([19]; see [17, 24, 46] for further discussion).

Conjecture 2 and Borsuk’s Conjecture were recently disproved in [65]. (We again come back to Erdős. The disproof is a simple application of a Theorem of Frankl and Wilson [39] which has its roots in the de Bruijn-Erdős Theorem and Fisher’s inequality [36]. Erdős was also one of the first to suggest that Borsuk’s Conjecture might be false [30].)

The case t = 1 of Conjecture 2 remains open (and interesting). Here Füredi and Seymour (see [31, 68]) proposed the stronger conjecture that one may use $\mathcal{H}_{i}$’s of the form $\{A \in \mathcal{H} : A \supseteq \{ x,y\}\}$ for appropriate vertex pairs {x, y}. This too turns out to be false [64], though a simple disproof would still be welcome. (Curiously, the random construction of [64] takes just a few lines to describe, but as of now about 20 pages to justify.)

3 A Problem of Erdős and Lovász

In a seminal paper [33], Erdős and Lovász pose the problem of estimating, for positive integer r,

$$\displaystyle{n(r) :=\min \{ \vert \mathcal{H}\vert : \mathcal{H}\mbox{ $r$-uniform, intersecting, with }\tau (\mathcal{H}) = r\}.}$$

That is, with how few intersecting r-edges can one force τ = r? While the conditions here may at first glance seem a little arbitrary, notice that we must require “intersecting,” or some substitute, to make the question nontrivial, and that once we assume “r-uniform, intersecting,” we are just asking that τ be as large as possible subject to these conditions. Thus the Erdős-Lovász problem is a quite natural way of making concrete the vague question, how can one economically force large cover number in a hypergraph with large edges?

Erdős and Lovász showed (writing $\mathcal{P}_{r}$ for any projective plane of order r − 1)

$$\displaystyle{ n(r) \geq 8r/3 - 3\mbox{ for all }r, }$$

(3)

and

$$\displaystyle{ n(r) \leq 4{r}^{3/2}\log r\mbox{ if there exists a }\mathcal{P}_{ r}, }$$

(4)

the second inequality being an immediate consequence of

Theorem 4 ([33]). 

If $\mathcal{H}$ is a set of m ≥ 4r ^3∕2log r random lines from $\mathcal{P}_{r}$ , then $Pr(\tau (\mathcal{H}) = r) \rightarrow 1(r \rightarrow \infty )$.

They also conjectured that the correct rate of growth here should be rlogr. This was shown in [59]:

Theorem 5.

If $\mathcal{H}$ is a set of m ≥ 22rlog r random lines from $\mathcal{P}_{r}$ , then $Pr(\tau (\mathcal{H}) = r) \rightarrow 1(r \rightarrow \infty )$.

Of course this also gives the corresponding improvement in (4). The correct value of m here is probably about 3rlogr; see [59] or [60] for a precise statement.

The problem from Erdős’ “list of three” was to decide whether

$$\displaystyle{ n(r) = O(r). }$$

(5)

This was done in [61]. The answer—that (5) is true—was probably not what most people expected. (Certainly it wasn’t what the author expected.)

We don’t have space to go into the construction here, but want to mention that one ingredient is the work of Chowla, Erdős and Straus [23] on the existence of large sets of mutually orthogonal Latin squares. See also the discussion following Theorem 9 for a small additional hint at what’s involved.

The constant in (5) is so far not very good. Quite surprisingly the best lower bound is still (3), though I feel quite certain this could be improved somewhat via the ideas of [57, 66] discussed in Sect. 5.

3.1 Meyer’s Problem

In connection with n(r), let us just briefly mention a related problem of similar vintage due to J.-C. Meyer [76]. Meyer defined

$$\displaystyle{m(r) =\min \{ \vert \mathcal{H}\vert : \mathcal{H}\mbox{ a maximal intersecting},r -\mbox{ uniform hypergraph}\}}$$

and conjectured that $m(r) \geq {r}^{2} - r + 1$ (projective planes being the obvious examples). This was disproved by Füredi [40], who showed

$$\displaystyle{ m(r) \leq 3{r}^{2}/4\mbox{ if there exists a }\mathcal{P}_{ r/2+1}. }$$

(6)

On the other hand, despite a fair amount of subsequent effort, it remains quite unclear how m(r) ought to grow. As of now the best results are (from [11, 18] and [25] respectively)

$$\displaystyle{ m(r) \leq {r}^{5}\ \forall r, }$$

(7)

$$\displaystyle{ m(r) < {r}^{2}/2 + O(r)\mbox{ if there exists a }\mathcal{P}_{ r}, }$$

(8)

and

$$\displaystyle{ m(r) \geq 3r\ \mathrm{for}\ r \geq 4. }$$

(9)

(The lower bound is a slight improvement on $m(r) \geq 8r/3 - 3$, which follows from (3), since trivially m(r) ≥ n(r). See also [60] for a proposed construction for m(r) = o(r ²) when there exists a $\mathcal{P}_{r}$.)

While the examples for n(r) described above don’t seem to give anything for m(r), they seem to me strongly to suggest the truth of

Conjecture 3.

m(r) = O(r).

4 The Erdős-Hanani Conjecture and Asymptotics of Packing and Covering Problems

Both Theorem 3 and, in a sense, the proof of (5) had their roots in yet another Erdős problem, the so-called “Erdős-Hanani Conjecture” of 1963, and in Rödl’s beautiful and seminal proof thereof. Here and in the next two sections we outline work which grew out of Rödl’s Theorem. As mentioned earlier, much of this material, and in particular the powerful “semirandom” approach underlying it all, was discussed at some length in [42, 60], so we will be pretty brief here, especially as regards the proofs.

4.1 The Erdős-Hanani Conjecture

For positive integer t, say a family $\mathcal{F}$ of subsets of a set V is a t-packing (resp. t-cover) if each t-subset of V is contained in at most (resp. at least) one member of $\mathcal{F}$. For 2 ≤ t < k < v =  | V | , let P(v, k, t) (resp. C(v, k, t)) denote the size of a largest t-packing (resp. smallest t-cover) of k-sets in V.

Erdős and Hanani [32] proved that the obvious bounds

$$\displaystyle{ P(v,k,t) \leq \left ({ v \atop t} \right ){\left ({ k \atop t} \right )}^{-1} \leq C(v,k,t) }$$

(10)

are asymptotically tight for t = 2 and any fixed k, and conjectured the same result for every t and k. This is Rödl’s Theorem:

Theorem 6 ([80]). 

For every fixed t and k,

$$\displaystyle{P(v,k,t) \sim \left ({ v \atop t} \right ){\left ({ k \atop t} \right )}^{-1} \sim C(v,k,t).}$$

(This is an asymptotic version of a well-known conjecture in the theory of block designs which states that the bounds (10) are exact for large enough v satisfying the obvious necessary conditions

$$\displaystyle{\left ({ k - i \atop t - i} \right )\,\bigg\vert \,\left ({ v - i \atop t - i} \right )\mbox{ for }0 \leq i \leq t - 1.}$$

For t = 2 this was proved by R. M. Wilson in the early 1970s [93], but for t ≥ 3 a proof still appears remote.)

In other language, Theorem 6 gives the asymptotics of the matching and edge cover numbers of the hypergraph $\mathcal{H} =\big\{ \left ({ K \atop t} \right ) : K \in \left ({ V \atop k} \right )\big\}$ on the vertex set $\left ({ V \atop t} \right )$. In fact, as shown by P. Frankl and Rödl [38], Rödl’s Theorem is just one instance of a remarkably general packing and covering phenomenon for hypergraphs with bounded edge sizes. An even stronger and cleaner version of their Theorem was proved by N. Pippenger (unpublished; for the original proof see [87] or [42]):

Theorem 7.

Let k be fixed and $\mathcal{H}$ a k-uniform D-regular hypergraph on n vertices satisfying

$$\displaystyle{ d(x,y) < o(D)\mbox{ for all distinct vertices }x,y. }$$

(11)

Then

$$\displaystyle{\nu (\mathcal{H}) \sim n/k \sim \rho (\mathcal{H}).}$$

(The Frankl-Rödl Theorem differs from Theorem 7 in requiring an explicit bound (roughly D ∕ (log | V | )³) on pairwise degrees. Incidentally, Theorem 7 is our first use of the “uniformity convention” (see Terminology): limits are taken as D → ∞, with convergence uniform in x, y and $\mathcal{H}$.)

4.2 The “semirandom” Approach

Joel Spencer remarks in [87] that the Erdős-Hanani Conjecture always seemed a natural candidate for a probabilistic proof. And the proof was probabilistic…

A natural way to try to prove Theorem 7, say for matchings, would be as follows. Let $\mathcal{H}_{0} = \mathcal{H}$, $M_{0} = \varnothing$, and for i = 1, … do

• (i) Choose A _i uniformly at random from $\mathcal{H}_{i-1}$,

• (ii) Set $M_{i} = M_{i-1} \cup \{ A_{i}\}$ and $\mathcal{H}_{i} =\{ A \in \mathcal{H}_{i-1} : A \cap A_{i} = \varnothing \}$.

When $\mathcal{H}_{i} = \varnothing$ we stop and take M _i to be our matching.

Most likely this procedure does work (e.g., in the sense that the random matching it produces has expected size asymptotic to n ∕ k), but I don’t think anyone knows how to show this at the moment. Rödl’s fundamental insight (translated to the proof of Theorem 7) was that we can do the analysis if at each stage we choose a small but fixed (positive) proportion of the desired matching M, rather than just one edge.

To say this a little more precisely, we switch from matchings to covers for a while. Thus we want to show $\rho (\mathcal{H}) < (1+\delta )n/k$ for δ > 0 fixed, $\mathcal{H}$ as in Theorem 7, and sufficiently large D.

Fix $\varepsilon > 0$ small relative to δ. Let $\mathcal{H}_{0} = \mathcal{H}$, V ₀ = V, and iterate the following procedure for i running from 1 to about ${\varepsilon }^{-1}\log (1/\delta )$. Let $\mathcal{K}_{i}$ be a random subset of $\mathcal{H}_{i-1}$ chosen according to

$$\displaystyle{Pr(A \in \mathcal{K}_{i}) =\varepsilon /D_{i-1}}$$

(for D _i see below), these events mutually independent. Set

$$\displaystyle{V _{i} = V _{i-1} \setminus \bigcup \{ A : A \in \mathcal{K}_{i}\},\qquad \mathcal{H}_{i} =\{ A \in \mathcal{H}_{i-1} : A \subseteq V _{i}\}.}$$

After the specified number of iterations we add to $\cup \mathcal{K}_{i}$ one edge containing x for each x ∈ V not covered by $\cup \mathcal{K}_{i}$, and claim this (usually) gives the desired cover. Of course what needs to be shown is that $\vert \cup \mathcal{K}_{i}\vert$ is typically about n ∕ k, while $\vert V \setminus \cup \{A : A \in \cup \mathcal{K}_{i}\}\vert$ is small relative to n.

The key to the success of this approach is that we can understand how various relevant quantities—$\vert \mathcal{K}_{i}\vert,\vert V _{i}\vert,\vert \mathcal{H}_{i}\vert$, and especially degrees in $\mathcal{H}_{i}$—ought to evolve, and, moreover, show that they do typically evolve approximately as they ought. In particular, each “residual” hypergraph $\mathcal{H}_{i}$ will be close to regular, meaning most of its vertices will have degree close to some (predictable) D _i .

To see why this might be true, suppose we fix x ∈ V _i − 1 and condition on {x ∈ V _i } (that is on $\{x \in A \in \mathcal{H}_{i-1} \Rightarrow A\notin \mathcal{K}_{i}\}$). Then writing X _A for the indicator of $\{A \in \mathcal{H}_{i}\}$, $d_{\mathcal{H}_{i}}(x) =\sum \{ X_{A} : x \in A \in \mathcal{H}_{i-1}\}$ is usually the sum of about D _i − 1 Bernoulli random variables whose expectations are, because of the approximate regularity of $\mathcal{H}_{i-1}$ and (11), about ${(1 -\varepsilon /D_{i-1})}^{(k-1)D_{i-1}}$. Moreover, again because of (11), there is considerable independence among these random variables, enough to enable us to say (via Chebyshev’s inequality) that $d_{\mathcal{H}_{i}}(x)$ is likely to be close to its expectation.

Actual implementation of this rough description requires considerable care. In particular, it does take some thought to convince oneself that the various estimates don’t deteriorate unacceptably over the specified number of iterations; but we won’t go into this here.

For the number of iterations, note that the “natural” value of Pr(x ∈ V _i  | x ∈ V _i − 1) is about ${(1 -\varepsilon /D_{i-1})}^{D_{i-1}} \approx {e}^{-\varepsilon }$, so that ${\varepsilon }^{-1}\log (1/\delta )$ iterations should reduce the number of vertices to about δ | V | .

Remarks.

 

• 1. A technical but important point is that, if n is large relative to D we cannot guarantee that all degrees in $\mathcal{H}_{i}$ are close to D _i . It was precisely in the handling of this point that Pippenger improved on [38].

• 2. For the matching portion of Theorem 7 we may dispense with the final augmentation of $\cup \mathcal{K}_{i}$ and simply take our matching M to consist of all isolated edges of $\cup \mathcal{K}_{i}$. The number of edges which this removes from $\mathcal{K}_{i}$ should be about $\varepsilon \vert \mathcal{K}_{i}\vert$, an acceptable loss. Actually the two parts of Theorem 7 are easily seen to be equivalent, but for the proof of Theorem 10 below one wants a procedure for generating a nicely behaved random matching; see Theorem 11. The procedure just described—essentially that of [77]—is an improved version of Pippenger’s original proof designed to accomplish this.

5 Fractional Versus Integer

As stated earlier, the starting point for most of the work discussed here was the realization that something like Theorem 7 could be used to try to prove n(r) ∕ r → ∞. In this section we give a little indication of this connection and sketch the work (other than [61]) that evolved most directly from this attempt.

5.1 Connection with n(r)

For $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$, let $t(\mathcal{H}) =\sum \{ t(A) : A \in \mathcal{H}\}$, define $\bar{t} : {2}^{V } \rightarrow {\mathbf{R}}^{+}$ by

$$\displaystyle{\bar{t}(A) =\sum \{ t(B) : B \supseteq A\},}$$

and set

$$\displaystyle{\alpha _{i}(t) =\max \{\bar{ t}(W) : W \subseteq V,\vert W\vert = i\}.}$$

For example, if $\mathcal{H}$ is r-regular, then for the fractional tiling t ≡ 1 ∕ r we have $\alpha _{2}(t) = {r}^{-1}\max \{d(x,y)\}$ and (11) (with r replacing D) is equivalent to

$$\displaystyle{ \alpha _{2}(t) \rightarrow 0, }$$

(12)

so that Theorem 7 is contained in

Theorem 8 ([57]). 

Let k be fixed, $\mathcal{H}$ a k-bounded hypergraph, and t : ℋ→ R ⁺ a fractional cover. Then

$$\displaystyle{\rho (\mathcal{H}) \lesssim t(\mathcal{H})\quad (\alpha _{2}(t) \rightarrow 0).}$$

(A similar result holds for matchings, but we confine ourselves here to covers.)

To see the connection with the Erdős-Lovász problem, we dualize: n(r) is the least number of vertices in an r-regular hypergraph satisfying

$$\displaystyle{ d(x,y) > 0\mbox{ for all distinct vertices }x,y }$$

(13)

and having edge cover number r. Thus the following consequence of Theorem 8 is relevant.

Corollary 1.

Suppose $\mathcal{H}$ is r-regular with at most cr vertices, c fixed, d(x,y) > 0 for all x,y ∈ V and

$$\displaystyle{\max \{d(x,y) : x,y \in V,x\neq y\} = o(r).}$$

Then $\rho (\mathcal{H}) < (c/(c + 1) + o(1))r$.

Or undualized:

Corollary 2.

Suppose $\mathcal{H}$ is r-uniform, intersecting, of size at most cr, c fixed, and satisfies

$$\displaystyle{ \max \{\vert A \cap B\vert : A,B \in \mathcal{H},A\neq B\} = o(r). }$$

(14)

Then $\tau (\mathcal{H}) < (c/(c + 1) + o(1))r$.

After a preliminary step which eliminates large edges, the connection between Theorem 8 and Corollary 1 is provided by the observation that if $\mathcal{H}$ is r-regular with n ≤ cr vertices and satisfies (13), then the function $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$ given by

$$\displaystyle{ t(A) = \vert A\vert /(n + r - 1) }$$

(15)

is a fractional cover of total weight

$$\displaystyle{ \sum _{A\in \mathcal{H}}t(A) = nr/(n + r - 1) \approx nr/(n + r) \leq cr/(c + 1). }$$

(16)

Notice also that larger pairwise degrees—corresponding to larger intersection sizes in the original formulation—will tend to give even smaller fractional cover number, suggesting that the best hope for proving (5) should indeed be via something akin to the projective plane based constructions of Theorems 4 and 5. But the above results say that one cannot prove (5) with $\mathcal{H}$’s in which all edge intersections are small.

This seemed for quite a while to support the opinion that n(r) ∕ r → ∞. But the correct lesson, very roughly, was that one should allow a few strategically placed small sets X with large d(X). This, it turns out, can be done in such a way that the value of the fractional cover doesn’t shrink too much, but we lose Theorem 8 entirely.

The proof of Theorem 8 is similar to that of Theorem 7. At each stage we have some fractional tiling t _i − 1 of the remaining hypergraph $\mathcal{H}_{i-1}$ which guides the choice of $\mathcal{K}_{i}$: we take each $A \in \mathcal{H}_{i-1}$ to be in $\mathcal{K}_{i}$ with probability $\varepsilon t_{i-1}(A)$.

It’s then necessary to update t _i − 1 in addition to V _i − 1 and $\mathcal{H}_{i-1}$. A nice bonus of the more general framework is that, because we are not restricted to uniform hypergraphs, the difficulty mentioned in Remark 1 at the end of Sect. 4 here essentially takes care of itself. Our random procedure will produce a hypergraph $\mathcal{G}\subseteq \mathcal{H}_{i-1}$ and approximate fractional tiling s. We can then (with high probability) replace $\mathcal{G}$ by some $\mathcal{H}_{i} \leq \mathcal{G}$ (meaning each edge of $\mathcal{H}_{i}$ is contained in an edge of $\mathcal{G}$) and s by a fractional tiling t _i of $\mathcal{H}_{i}$ such that $t_{i}(\mathcal{H}_{i}) \approx s(\mathcal{G})$. In particular, we begin each iteration with a fractional tiling, the fractional analogue of a regular $\mathcal{H}_{i-1}$.

5.2 Local Behavior

The work in [66] again grew out of attempts to push the approach of Theorem 8 to prove n(r) ∕ r → ∞. The general idea was that it should be possible to relax (12) to a requirement that “locally”—that is, on small sets of vertices—one can find ordinary (integer) covers which mimic the fractional cover t. A way to make this precise is as follows.

For $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$ and any X ⊆ V, define $t\vert _{X} : {2}^{X} \rightarrow {\mathbf{R}}^{+}$ by

$$\displaystyle{t\vert _{X}(A) =\sum \{ t(B) : B \cap X = A\}.}$$

Write MP(X) for the matching polytope of X:

$$\displaystyle{MP(X) =\mathrm{ conv}\{1_{M} : M\mbox{ a matching of }{2}^{X}\}.}$$

Denote by b(t) the largest b such that for any X ⊆ V with | X | ≤ b we have t |  _X  ∈ MP(X). In place of (12) we then require that b(t) → ∞. (Note this is weaker than (12).)

Suppose for example that $V (\mathcal{H})$ is partitioned into triples, and that we allow $\bar{t}(\{x,y\})$ to be large when x, y are in the same triple and take each edge of $\mathcal{H}$ to meet each triple in either 0 or 2 vertices. Then b(t) = 2 and it’s more or less typical (e.g., take $\mathcal{H}$ regular and uniform) for $\rho (\mathcal{H})$ to be about ${(4/3)\rho }^{{\ast}}(\mathcal{H})$, reflecting the fact that we have $\rho (\Gamma ) = {(4/3)\rho }^{{\ast}}(\Gamma )$ for the underlying graph $\Gamma$ of pairs for which $\bar{t}$ is allowed to be large.

But—this was the starting point—the fractional covers (15) arising in connection with n(r) cannot look like this, and in fact b(t) does tend to be large in situations of interest for n(r). (To see what’s meant here, assume most pairwise degrees in $\mathcal{H}$ are 1—if they’re not then we gain substantially in (16)—and use the fact that t in (15) is given by $t(A) = {(n + r - 1)}^{-1}\sum _{x\in V }1_{\{A\ni x\}}$ to show that for X not too large, t |  _X is (usually, approximately) in MP(X).)

At any rate, it turns out that “b(t) → ∞” is the correct relaxation of (12), provided we at least insist that α ₃ be small:

Theorem 9 ([66]). 

Let k be fixed, $\mathcal{H}$ a k-bounded hypergraph, and $t : \mathcal{H}\rightarrow {\mathbf{R}}^{+}$ a fractional tiling. Then

$$\displaystyle{\rho (\mathcal{H}) \lesssim t(\mathcal{H})\quad (\alpha _{3}(t) \rightarrow 0,b(t) \rightarrow \infty ).}$$

This implies for example that in Theorem 8 we could replace α ₂(t) by

$$\displaystyle{\max \{\bar{t}(\{x,y\}) : x,y \in X\mbox{ or }\ x,y \in Y \}}$$

where X ∪Y is a partition of V. That is, allowing $\bar{t}$ to be large on the edges of a bipartite graph doesn’t create obstructions to good cover behavior, reflecting the fact that fractional and integer edge cover numbers coincide for bipartite graphs.

(Though this has yet to be checked, Theorem 9 probably implies that Corollary 2 holds even if we relax (14) to the analogous condition on 3-wise intersections.)

If we allow α ₃(t) to be large, then the situation changes completely. For instance, the dual, $\mathcal{H}$, of a random cubic graph (as in [8, 12, 13]) is a 3-uniform, 2-regular hypergraph which typically has no short cycles, yet has ρ substantially greater than | V | ∕ 3. Thus the fractional tiling t ≡ 1 ∕ 2 has large b(t), yet $\rho (\mathcal{H})$ is much larger than $t(\mathcal{H})$.

I think it’s fair to say that it’s this phenomenon that lies at the heart of the construction of [61]: there the “small sets X with large d(X)” mentioned following (16) comprise a hypergraph with properties akin to those described in the preceding paragraph.

Theorem 9 was conjectured in [60]. The proof turned out to be both harder and much more interesting than originally anticipated, involving, centrally, some understanding of the behavior of so-called “normal” distributions on the set of matchings of a graph. This connection is sketched a little in Sect. 7. The questions raised in [66] also led, if somewhat tangentially, to the work on random matchings outlined in Sect. 8.

6 Chromatic and List-Chromatic Indices

It was suggested by Füredi [88] that the hypotheses of Theorem 7 might guarantee the existence not just of one good matching or cover, but of a decomposition of the entire hypergraph into matchings or covers which are good on average. This was proved by Pippenger and Spencer.

Theorem 10 ([77]). 

Under the hypotheses of Theorem 7,

$$\displaystyle{\chi ^{\prime}(\mathcal{H}) \sim D(\mathcal{H}) \sim \phi (\mathcal{H}).}$$

(As noted in [77], the second assertion of Theorem 10 follows from the first; here we restrict our attention to χ′.)

Theorem 10 is based on an elegant variant of Theorem 7, which we state for future reference.

Theorem 11.

For every $\varepsilon > 0$ and k there are δ > 0 and t so that if $\mathcal{H}$ is a k-uniform, D-regular hypergraph on V with

$$\displaystyle{d(x,y) <\delta D\qquad \forall x,y \in V,}$$

then there is a probability distribution p on the set $\mathcal{M}$ of matchings of $\mathcal{H}$ satisfying

• (a) $\sum \{p(M) : A \in M \in \mathcal{M}\} = _{\varepsilon }1/D\qquad \forall A \in \mathcal{H}$,

• (b) For M chosen according to p, and $A \in \mathcal{H}$ , the event {A ∈ M} is independent of the events $\{\{B \in M\} : \Delta (A,B) > t\}$.

In fact what’s shown in [77] is that the distribution obtained from the random procedure sketched in Sect. 4 has these properties. (The present $\varepsilon$ and δ are not those used earlier). Of course for the expected size, say μ, of a random matching drawn from a distribution satisfying (a), we have $\mu = _{\varepsilon }n/k$. This (letting $\varepsilon \rightarrow 0$) yields Theorem 7, and says that matchings of the desired size are plentiful in some sense.

The proof of Theorem 10 is in the same vein as that of Theorem 7. Rather than cover vertices by edges, we must cover edges by matchings. Again we proceed in stages, choosing at each stage enough random matchings to cover a small but constant fraction of the surviving edges. Here, in contrast to the earlier situation, it is far from obvious what ought to be meant by “random matchings”; but matchings drawn from distributions as in Theorem 11 work very nicely (except that we should relax D-regularity in the theorem to something like “d(x) =  _δ D  ∀x ∈ V ”).

The point of (b)—I think this the nicest new idea here—is that it supports use of the Lovász local lemma ([33] or e.g. [4]) to say that our small sets of matchings have positive probability of being well-behaved at every vertex. (Here and again in Theorems 12 and 13, application of the local lemma requires much stronger concentration assertions than are given by Chebyshev’s inequality. These are achieved via martingales: the so-called “Azuma-Hoeffding” inequality ([7, 54], or e.g. [14, 75]) in the present instance, and extensions thereof for the later results.)

6.1 List Colorings

The final (for now; see Conjecture 7) development in the direction we’ve been discussing was an extension of Theorem 10 to list-colorings which was conjectured in [58] and proved in [62].

Recall that the list-chromatic index, $\chi _{l}^{\prime}(\mathcal{H})$, of $\mathcal{H}$ is the least t such that if S(A) is a set (“list”) of size t for each $A \in \mathcal{H}$, then there exists a proper coloring σ of $\mathcal{H}$ with σ(A) ∈ S(A) for each $A \in \mathcal{H}$. Of course χ _l ′ is always at least χ′, so Theorem 10 is contained in

Theorem 12 ([62]). 

Let k be fixed and $\mathcal{H}$ a k-bounded hypergraph of maximum degree D satisfying (11) . Then

$$\displaystyle{\chi _{l}^{\prime}(\mathcal{H}) \sim D\qquad (D \rightarrow \infty ).}$$

List-colorings have recently been getting a lot of attention. Here we just want to give enough background on list-chromatic indices of graphs to put the graphic case of Theorem 12 in context. But see [3] for a survey of recent results, and, e.g., [47, 48, 62] for more on what’s touched on here. Let us also mention that we are, as usual, in Erdős territory: the study of list colorings was initiated by Vizing in [92] and, independently, Erdős, Rubin and Taylor in [34].

The following central problem, now called the “list-chromatic” or “list coloring” conjecture, seems to have been proposed several times, probably first by Vizing in 1975 (see, e.g., [22, 47, 48] for more on this story).

Conjecture 4.

For every multigraph G, χ _l ′(G) = χ′(G).

The case G = K _n, n was proposed by J. Dinitz in about 1978 (see [28]) in the context of Latin squares. This version is particularly appealing, and seems to have provided much of the initial stimulus for western interest in such questions.

Conjecture 5 (Dinitz Conjecture). 

Suppose that for 1 ≤ i,j ≤ n, S _i,j is a set of size n. Then there is a partial Latin square $(s_{i,j})_{1\leq i,j\leq n}$ with s _i,j ∈ S _i,j for all i,j.

(A partial Latin square of order n is an n ×n array of symbols with the property that no symbol appears more than once in any row or column.)

Let us just quickly mention that there are natural extensions of these problems to vector spaces and matroids. For example, the following was proposed in [62] as a common generalization of the Dinitz Conjecture and a conjecture of G.-C. Rota [55] (see [55, 62] for more in this direction).

Conjecture 6.

Let V be an n-dimensional vector space and suppose that for 1 ≤ i,j ≤ n, S _i,j is a basis of V. Then there exist s _i,j ∈ S _i,j for 1 ≤ i,j ≤ n such that each of the sets {s _i,j : j = 1,…,n}, {s _i,j : i = 1,…,n} is a basis of V.

For simple G, Conjecture 4 together with Vizing’s Theorem would imply that D(G) ≤ χ _l ′(G) ≤ D(G) + 1, while Theorem 12 says that D(G) is at least the right asymptotic value. This improved several earlier bounds (e.g., [15, 16, 22]), the best of which was

$$\displaystyle{\chi _{l}^{\prime}(G) < 7D(G)/4 + o(D(G))}$$

due to Bollobás and Hind [16].

We haven’t had space in this very brief summary to discuss a beautiful algebraic approach to list colorings which was introduced by Alon and Tarsi in [5] and has had several important consequences ([27, 37] or [3]). Recently J. Janssen [56] used this approach to give a simple and elegant proof that $\chi _{l}^{\prime}(K_{n,n+1}) = n + 1$ (which in particular says that the Dinitz Conjecture is not off by more than 1), and then Häggkvist and Janssen [48], taking [56] as a starting point, showed, inter alia,

$$\displaystyle{ \chi _{l}^{\prime}(G) < D + O({D}^{2/3}\log D) }$$

(17)

for simple bipartite G of maximum degree D. At this writing they can also show χ _l ′(K _n ) ≤ n + 1, and expect that their method will extend to give (17) for nonbipartite graphs.

6.2 Semirandom Again

Theorem 12 was conjectured in [58], where a much more limited extension of Theorem 10 was used to prove Theorem 3. (Derivation of Theorem 3 from Theorem 12 is left as a nice exercise for the reader; or see [60].) While it was nice to see the asymptotic correctness of Conjecture 1, it’s my (perhaps not majority) opinion that the most important thing to come out of [58] was the right conjecture along these lines, namely what became Theorem 12.

The special case of Theorem 12 proved in [58] requires a good understanding of [77] but not too much in the way of new ideas. Theorem 12, on the other hand, for some time seemed beyond reach, an opinion influenced in part by the apparent difficulty of even the graphic case, and in part by the fact that the Pippenger-Spencer proof clearly would not extend.

The basic idea of the eventual proof is actually quite natural, though a little strange in that it initially seems doomed to failure. Here’s a thumbnail sketch in the “standard” case that all the S(A)’s are the same. (The general case is not essentially different, but involves some fiddling to keep the relevant parameters on track.)

We color the hypergraph in stages. At each stage we tentatively assign each as yet uncolored edge A a random color from its current list of legal colors. In some (most) cases, the color tentatively assigned to A will also be assigned to one or more edges meeting A. Such edges A are simply returned to the pool of uncolored edges. The remaining edges (those not involved in such “collisions”) are permanently colored with their tentative colors and removed from the hypergraph. We then modify the lists of legal colors (mainly meaning that we delete from S(A) all colors already assigned to edges which meet A) and repeat the process.

Martingale Concentration results together with the Lovász local lemma are used to show that this procedure can be repeated many times, leaving after each stage a hypergraph and modified lists, of legal colors which are reasonably well-behaved. (Finding the correct definition of “well-behaved” is crucial.) Eventually our control here does deteriorate, but by the time this happens the degrees in the remaining hypergraph are small relative to the (minimum) number of colors still admissible at an edge, and the remaining edges can be colored greedily.

The strange feature alluded to above is that the lists of legal colors initially shrink much faster than the degrees. (Roughly, when the degrees have shrunk to βD, with β not too small, the lists will have size about β ^k D if edges are of size k.) This at first seems unpromising, since we are accustomed to thinking of degree as a trivial lower bound on chromatic index. What saves us here—this is perhaps the central idea of the proof—is that the lists S ⁱ(A) (of legal colors for A at the end of stage i) tend to evolve fairly independently, except where obviously dependent. So for example, for a color γ which through stage i has not been permanently assigned to any edge meeting A ∩ B (that is, we condition on this being so), the probability that γ belongs to S ⁱ(B) is not much affected by its membership or nonmembership in S ⁱ(A).

Implementation of this idea is reasonably delicate; still, I think the proof demonstrates considerable flexibility for the “guided-random” approach (beyond what was already apparent from the results discussed above), and expect to see further applications in the near future.

For example, about a year ago, J. H. Kim [69] used a similar method to make significant progress on Vizing’s old problem [91] of upper bounds for the chromatic number of a triangle-free graph G of maximum degree D, proving

Theorem 13.

If G is a graph of maximum degree D and girth at least 5, then $\chi _{l}(G) < (1 + o(1))D/\log D$.

(with the list-chromatic numberχ _l defined in the obvious way). Here even for large girth the best previous upper bound was about D ∕ 2 due to Kostochka [71], though it seems reasonable to expect, particularly in view of [1, 2, 86], that the the bound of Theorem 13 remains valid for triangle-free G.

(Recently, R. Häggkvist told me that A. Johansson and S. McGuiness, had just (independently) proved Kim’s result—following the method of Theorem 12 as described in [60]—and believed that for girth 4 they could show $\chi (G) = O(D/\log D)$ and χ _l (G) = o(D).)

6.3 A Conjecture

Before closing this section, we mention one more (important) problem which recalls the “fractional vs. integer” theme of Sect. 5.

Conjecture 7.

For fixed k and k-bounded hypergraph $\mathcal{H}$,

$$\displaystyle{\chi _{l}^{\prime}(\mathcal{H}) \sim \chi ^{\prime}(\mathcal{H}) {\sim \chi }^{{\prime}{\ast}}(\mathcal{H}).}$$

This goes far beyond Theorem 12, giving in effect—LP’s being regarded as “tractable” problems—a complete understanding of the asymptotics of chromatic and list-chromatic indices of k-bounded hypergraphs, even if we abandon assumptions such as (11) entirely. Note it contains Theorem 12 via Theorem 11, since the existence of a distribution p on $\mathcal{M} = \mathcal{M}(\mathcal{H})$ satisfying

$$\displaystyle{\sum \{p(M) : A \in M \in \mathcal{M}\}\sim 1/D\qquad \forall A \in \mathcal{H}}$$

is the same as ${\chi }^{{\prime}{\ast}}(\mathcal{H}) \sim D$.

Even the very special case of Conjecture 7,

$$\displaystyle{ \mbox{ for multigraphs }G,\chi ^{\prime}(G) {\sim \chi }^{{\prime}{\ast}}, }$$

(18)

is open, and of considerable interest. (For multigraphs χ ^′ ∗ is given by Edmonds’ Matching Polytope Theorem ([26] or, e.g., [82]). More precise versions of (18) were proposed by Goldberg (see [89]), Andersen [6], Seymour [83] and again Goldberg [45]. The most important results on chromatic indices of multigraphs are those of Shannon [85] and Vizing [90]; see also [35]. For χ _l ′ of a multigraph G, the current upper bound is 9D(G) ∕ 5, due to Hind [52].)

For one way of attacking (18) see Question 1 below.

7 Normal Distributions

As mentioned earlier, a central role in the proof of Theorem 9 is played by so-called “normal” distributions on the set of matchings of a graph. In this section we say what these are and try to give some idea of what they have to do with Theorem 9. Then in Sect. 8 we describe some recent results for the special case of uniform distribution.

Let G = (V, E) be a graph and $\mathcal{M} = \mathcal{M}(G)$ the set of matchings of G. For $M \in \mathcal{M}$, v ∈ V, we write v ≺ M if v is contained in some edge of M.

A normal distribution on $\mathcal{M}$ is a probability distribution p = p _λ derived from some λ : E → R ⁺ according to

$$\displaystyle\begin{array}{rcl} & & \qquad \qquad w(M) =\prod _{A\in M}\lambda _{A}, {}\\ & & p(M) = w(M)/\sum _{M^{\prime}\in \mathcal{M}}w(M^{\prime}). {}\\ \end{array}$$

For p a probability distribution on $\mathcal{M}$, $M \in \mathcal{M}$ chosen according to p and F _i  ∈ E, set $p_{F_{1},\ldots,F_{t}} = Pr(F_{1},\ldots,F_{t} \in M)$. We call the probabilities p _F for F ∈ E the marginals of p.

Let f : E → R ⁺. Edmonds’ Matching Polytope Theorem says (though not in this language) that there is a probability distribution on $\mathcal{M}$ with marginals f iff

$$\displaystyle{ \sum _{F\ni v}f(F) \leq 1\qquad \forall v \in V }$$

(19)

and

$$\displaystyle{ \sum \{f(F) : F \subseteq W\} \leq \lfloor \vert W\vert /2\rfloor \qquad \forall W \subseteq V. }$$

(20)

The matching polytope, MP(G), is the set of such f’s. For normal distributions the analogous characterization was observed by Rabinovich, Sinclair and Wigderson [78]:

Theorem 14.

There exists a normal distribution with marginals f if and only if the inequalities (19) and (20) are strict for all v ∈ V and $W \subseteq V$.

We say that distribution p on $\mathcal{M}$ has the property Ed(δ) if its marginal distribution f is in (1 − δ)MP(G), or equivalently, if the inequalities (19) and (20) hold even when their right hand sides are multiplied by (1 − δ). A crucial ingredient of the proof of Theorem 9 is a somewhat more technical version of

Lemma 1.

For all δ, $\varepsilon > 0$ , and l there exists D such that if p has Ed(δ) and if F ₁ ,…,F _l ∈ E are pairwise at distance at least D in G, then

$$\displaystyle{p_{F_{1},\ldots,F_{l}} = _{\varepsilon }p_{F_{1}}\cdots p_{F_{l}}.}$$

Thus, requiring that the marginals of p stay well away from the boundary of MP(G) guarantees a fair amount of (approximate) independence among the events {F ∈ M}.

Theorem 9 is proved by applying Theorem 8 to a sort of contraction of a randomly generated subhypergraph of the given hypergraph $\mathcal{H}$. To give some idea of the relevance of Lemma 1, we make some simplifying, and slightly vague, assumptions. (The actual proof uses some preliminary reductions to arrive at similar, but somewhat weaker assumptions.)

Suppose $\Gamma$ is a set of pairs—thought of as a graph—from V such that $\max \{\bar{t}(\{x,y\}) :\{ x,y\}\notin \Gamma \}$ is small, and such that each $A \in \mathcal{H}$ is the union of some collection of edges of $\Gamma$, called the parts of A, which are pairwise far apart in $\Gamma$. Under the latter assumption, the restriction $\bar{t}\vert _{\Gamma }$ is a fractional tiling; moreover, it’s not hard to see that if b(t) is large enough then $f := (1-\vartheta )\bar{t}\vert _{\Gamma } \in (1-\delta )MP(\Gamma )$ for appropriate $\vartheta$, δ, both small positive constants.

Write F ≺ A if F is a part of A. Let p be the normal distribution with marginals f (as shown in [78], p is unique), and let M be chosen according to p. By the preceding remark, Lemma 1 applies to p. Define a new hypergraph ${\mathcal{H}}^{{\ast}}$ on vertex set V ^∗, and ${t}^{{\ast}} : {\mathcal{H}}^{{\ast}}\rightarrow {\mathbf{R}}^{+}$ by

$$\displaystyle\begin{array}{rcl} & & \qquad \qquad \qquad {V }^{{\ast}} =\{ {F}^{{\ast}} : F \in M\}, {}\\ & & {\mathcal{H}}^{{\ast}} =\{ {A}^{{\ast}} : A \in \mathcal{H},\mbox{ all parts of }A\mbox{ are in }M\} {}\\ \end{array}$$

(with F ^∗ ∈ A ^∗ iff F ≺ A), and

$$\displaystyle{{t}^{{\ast}}({A}^{{\ast}}) =\prod _{ F\prec A}f{(F)}^{-1}t(A)\qquad \forall {A}^{{\ast}}\in {\mathcal{H}}^{{\ast}}.}$$

We prove Theorem 9 by showing that typically (using “ ≈ ” and “ ≲ ” only qualitatively in what follows)

$$\displaystyle{\rho (\mathcal{H}) \lesssim \rho ({\mathcal{H}}^{{\ast}}) \lesssim {t}^{{\ast}}({\mathcal{H}}^{{\ast}}) \approx t(\mathcal{H}).}$$

Note for example that if the various events {F ∈ M} were mutually independent, then we’d have $E[{t}^{{\ast}}({\mathcal{H}}^{{\ast}})] = t(\mathcal{H})$.

Let us just say a little about the middle inequality, which is the heart of the matter. To prove it, we intend to apply a mild generalization of Theorem 8 to the pair $({\mathcal{H}}^{{\ast}},{t}^{{\ast}})$. The main point (of the whole business) is to show that t ^∗ is (usually and in an appropriate sense) an approximate fractional tiling of ${\mathcal{H}}^{{\ast}}$. This goes roughly as follows.

Suppose we condition on {F ∈ M} (for some $F \in \Gamma$) and consider $\bar{{t}^{{\ast}}}({F}^{{\ast}}) =\sum \{ {t}^{{\ast}}({A}^{{\ast}}) : {F}^{{\ast}}\in {A}^{{\ast}}\in {\mathcal{H}}^{{\ast}}\}$. This has (conditional) expectation

$$\displaystyle\begin{array}{rcl} & & \sum _{A\succ F}Pr({A}^{{\ast}}\in {\mathcal{H}}^{{\ast}}\vert F \in M)\prod _{ G\prec A}f{(G)}^{-1}t(A) \approx f{(F)}^{-1}\sum \limits _{ A\succ F}t(A) {}\\ & & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad = f{(F)}^{-1}\bar{t}(F) = {(1-\vartheta )}^{-1} \approx 1, {}\\ \end{array}$$

since according to Lemma 1 and our simplifying assumptions,

$$\displaystyle{Pr({A}^{{\ast}}\in {\mathcal{H}}^{{\ast}}\vert F \in M) = Pr(G \in M\ \forall F\neq G \prec A\vert F \in M) \approx \prod _{ F\neq G\prec A}f(G).}$$

Moreover—we leave the reader to ponder this nicest point—Lemma 1 enables us to use Chebyshev’s inequality to show that $\bar{{t}^{{\ast}}}({F}^{{\ast}})$ (again conditioned on {F ∈ M}) is usually close to its mean. (There’s a slight lie here: we should add an assumption to the effect that for $\{x,y\} \in \Gamma$, $\bar{t}(\{x,y\})$ is not too small.)

Thus, typically, $\bar{{t}^{{\ast}}}({F}^{{\ast}})$ will be close to 1 for mostF ^∗ ∈ V ^∗, which is basically what we want.

8 Random Matchings

For the rest of our discussion we consider uniform distribution on $\mathcal{M}(G)$ (so the normal distribution corresponding to λ ≡ 1). The main results here, Theorems 17 and 18, are surprisingly strong, and show that the distributions in question are in some respects much nicer than seems to have been previously realized.

The material of this section is a little tangential to the topics of Sects. 2–6, but I include it here for two reasons. First, I do think of it as growing out of the earlier work. Second, understanding the extent to which the results described here extend to k-bounded hypergraphs would greatly enhance our understanding of these objects, and would in some cases (see in particular Conjecture 8 and Question 1) have specific consequences for questions considered above.

Let G be a graph and let M be drawn uniformly at random from $\mathcal{M}(G)$. Mainly following [74, p. 341], we set $\xi =\xi (G) = \vert M\vert$ and $p_{k}(G) = Pr(\xi = k)$, and let μ = μ(G) and σ = σ(G) denote respectively the mean and standard deviation of ξ.

In what follows we deal with a sequence {G _n } of (simple) graphs. We abbreviate ξ(G _n ), μ(G _n ) and σ(G _n ) to ξ _n , μ _n and σ _n , and in addition, set | V (G _n ) |  = v _n , | E(G _n ) |  = e _n , D(G _n ) = D _n and ν(G _n ) = ν _n . To avoid trivialities we always assume v _n  → ∞ (n → ∞).

In 1981 C. Godsil [43] gave sufficient conditions for asymptotic normality of the distributions {p _k (G _n )}:

Theorem 15.

If $D_{n}^{2}/e_{n} \rightarrow 0$ then the distribution $\{p_{k}(G_{n})\}_{k\geq 0}$ of matching sizes in G _n is asymptotically normal.

That is, for each x ∈ R

$$\displaystyle{Pr(\frac{\xi _{n} -\mu _{n}} {\sigma _{n}} < x) \rightarrow \frac{1} {\sqrt{2\pi }}\int _{-\infty }^{x}{e}^{-{t}^{2}/2 }dt\quad (n \rightarrow \infty ).}$$

The same conclusion was obtained by Ruciński [81] under a weaker hypothesis:

Theorem 16.

If ν _n ∕D _n →∞ then $\{p_{k}(G_{n})\}_{k\geq 0}$ is asymptotically normal.

The main result of [63] is a necessary and sufficient condition:

Theorem 17.

The distribution $\{p_{k}(G_{n})\}_{k\geq 0}$ is asymptotically normal if and only if

$$\displaystyle{ \nu _{n} -\mu _{n} \rightarrow \infty \ (n \rightarrow \infty ). }$$

(21)

Let p(G, x) denote the probability generating function of the sequence {p _k (G)},

$$\displaystyle{p(G,x) =\sum \limits _{ k=0}^{\nu (G)}p_{ k}(G){x}^{k}.}$$

A fundamental fact, proved in [51] (see also [50]) and [72], is

$$\displaystyle{ \mbox{ for every }G,p(G,x)\mbox{ has real roots}. }$$

(22)

The significance of this for our discussion was first noticed by L. Harper [49] in his proof of asymptotic normality of the sequence {S(n, k) ∕ B _n } _k ≥ 1 (with S(n, k) the Stirling number of the second kind and B _n the Bell number). Harper’s neat observation is that, given (22), a necessary and sufficient condition for asymptotic normality of $\{p_{k}(G_{n})\}_{k\geq 0}$ is that

$$\displaystyle{ \sigma _{n} \rightarrow \infty. }$$

(23)

Thus Godsil and Ruciński just need to prove (23) under their respective hypotheses (in both cases the key is the fact, shown in [51], that if p(G, x ₀) = 0, then | x ₀ | ≥ 4(D(G) − 1)), while proving Theorem 17 amounts to bounding ν − μ as a function of σ. (The current proof gives $\nu -\mu = O{(\sigma }^{8})$; curiously, one can have ν − μ as large as $\Omega ({n}^{6})$, which seems likely to be the truth.)

Having said this, let us stress that, as illustrated by the next result, Theorem 17 is by no means a matter of replacing one unverifiable condition by another. (We write δ _n for the minimum degree of G _n .)

Corollary 3.

Each of the following implies asymptotic normality.

• (a) ν _n ∕D _n →∞

• (b) $\delta _{n } = (1 - o(1))D_{n}$

• (c) $\nu _{n } > (1 - o(1))v_{n}/2$

(The reader might try to see why each of (a)–(c) implies (21).)

Thus we recover Theorems 15 and 16, and for example have asymptotic normality for any sequence of regular graphs—note Theorems 15 and 16 do not apply to sequences of regular graphs for which degree grows in proportion to the number of vertices—or graphs with perfect matchings. The latter includes Harper’s theorem (again, see [43] or [79, p. 213] for the connection). Slightly unbalanced complete bipartite graphs show that (c) can’t be relaxed to “$\nu _{n} > (1-\varepsilon )v_{n}/2$” if $\varepsilon > 0$ is fixed.

We don’t have space to say much about the proof of Theorem 17. As of now it is not very easy, though there are some special cases—e.g., sequences of regular graphs or sequences as in Theorems 15 and 16—for which the methods of [63] give fairly simple proofs. Though there’s no concrete connection between these methods and the guided-random approach of earlier sections, they do have in common a reliance on having a lot of approximate independence in the relevant probability spaces. For the earlier results, this independence is usually derived from something like (11). For Theorem 17, and also for Theorem 9 (see Lemma 1), the required independence derives from the following simple fact.

Let M be a random matching drawn from a normal distribution on a graph G, and for vertex x, set p(x) = Pr(x ≺ M). For x ∈ V, $W \subseteq V (G)$, set $\mu (W) =\mu _{G}(W) =\sum _{w\in W}p(w)$ and $\mu (W\vert \bar{x}) =\mu _{G-x}(W \setminus \{ x\})$. (Thus μ(W) is the expected number of vertices of W covered by M, while $\mu (W\vert \bar{x})$ is the same number conditioned on {x⊀M}.)

Lemma 2.

If $x\notin W$ , then $\big\vert \mu (W) -\mu (W\vert \bar{x})\big\vert \leq p(x)$.

In particular, conditioning on {x⊀M} changes μ(W) by at most 1.

As noted above, Theorem 17 provides the first proof of (23) for sequences of regular graphs. In fact, as shown even more recently in [67], the values of μ and σ ² for a regular graph are remarkably well determined just by degree and number of vertices:

Theorem 18.

For any d-regular simple graph G,

• (a) $v(G) - 2\mu (G) \sim v(G)/\sqrt{d}$,

• (b) ${\sigma }^{2 } (G) \sim v(G)/(4\sqrt{d})$

(limits taken as d →∞).

Actually (a) is a consequence of the finer

$$\displaystyle{p(\bar{x}) := Pr(x \not\prec M) \sim {d}^{-1/2}\quad \forall x \in V (G).}$$

(It’s worth stressing once more the use of the uniformity convention: the rates of convergence in the last three assertions depend on nothing but d.)

The proof of Theorem 18 is again based in part on martingale concentration results, in this case for martingales related to random self-avoiding walks on the graphs in question. (The connection takes a little too long to discuss here, but see [44] for an indication of the relation between matchings and self-avoiding walks.)

Let us close with a conjecture and a question which take us back to some of the topics discussed earlier. (Though we won’t pursue the subject here, it would also be of considerable interest to understand to what extent Theorem 17 continues to hold for k-bounded hypergraphs; see [63] for some speculation as to what might be true in this direction.)

Conjecture 8.

For fixed k and simple, k-uniform, D-regular $\mathcal{H}$,

$$\displaystyle{p(\bar{v}) \sim {D}^{-1/k}\quad \forall v \in V (\mathcal{H}).}$$

If we relax “simple” to (11), then the conclusion should be $p(\bar{x}) \rightarrow 0$, which, like Theorem 11, would say that the value of ν predicted by Theorem 7 is actually the average size of an appropriately defined random matching. Given the sophistication of the distribution of Theorem 11 (and the difficulty of Theorem 7 itself), it would be extremely interesting if uniform distribution accomplished the same thing.

Finally, an affirmative answer to the following would imply (18) (in the same way that Theorem 11 implies Theorem 10), and would also be very interesting in its own right.

Question 1.

Is it true that for each $\varepsilon > 0$ there exist t and D ₀ such that for every D ≥ D ₀ and D-regular multigraph G with χ ^′∗ (G) = D, there is a probability distribution p on $\mathcal{M} = \mathcal{M}(G)$ satisfying

• (a) $p_{A} = _{\varepsilon }1/D\quad \forall A \in E(G)$ , and

• (b) For M chosen according to p, and $A \in \mathcal{H}$ , the event {A ∈ M} is independent of the events $\{\{B \in M\} : \Delta (A,B) > t\}$ ?

Added in Proof

Conjecture 7 for bipartite multigraphs, so in particular the Dinitz Conjecture (Conjecture 5), was proved by Fred Galvin around the end of 1993 [F. Galvin, The list chromatic index of a bipartite multigraph, J. Combinatorial Th. (B) 63 (1995), 153–158].

Anders Johansson [A. Johansson, An improved upper bound on the choice number for triangle free graphs, manuscript, 1994], again along the lines of the proof of Theorem 12, proved $\chi _{l}(G) = O(D/\log D)$ for triangle-free G (compare Theorem 13).

Another major application of the semirandom method discussed in Sects. 4 and 6 was given in [J.H. Kim, The Ramsey number R(3, t) has order of magnitude t ² ∕ logt, Random structures and Algorithms 7 (1995), 173–207].

Joel Spencer [J. Spencer, Asymptotic packing via a branching process, Random structures and Algorithms 7 (1995), 167–172.] showed that the “natural” proof suggested after Theorem 7 does indeed work.

A simpler proof of Theorem 8, based on the [77] proof of Theorem 7, was given in [J. Kahn, A linear programming perspective on the Frankl-Rödl-Pippenger Theorem, Random Structures and Algorithms 8 (1996), 149–157].

A proof of (18), based on normal distributions and the approximate independence results of [66], was given in [J. Kahn, Asymptotics of the chromatic index for multigraphs, J. Combinatorial Th. (B) 68 (1996), 233–254].

The list-coloring version of (18) (so Conjecture 7 for multigraphs) was proved in [J. Kahn, Asymptotics of the list-chromatic index for multigraphs, Random Structures & Algorithms 17 (2000), 117–156].

Several of the above results, together with further applications of the ideas sketched in Sect. 6, are discussed in detail in [M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, Springer, Berlin, 2002.]