Graph and hypergraph colouring via nibble methods: a survey (Q6086395): Difference between revisions

The semi-random method, or the `nibble method' is a technique that first appeared (in a nascent form) in a paper of \textit{M. Ajtai} et al. [Eur. J. Comb. 2, 1--11 (1981; Zbl 0474.10038)] and then in a more explicit form in the paper of \textit{V. Rödl} [Eur. J. Comb. 6, 69--78 (1985; Zbl 0565.05016)] that has now become a powerful technique in the arsenal of the probabilistic paradigm in combinatorial problems. One way to think about the nibble method is to view this as an `induction paradigm' within the ambit of the probabilistic method. To make this more precise, let us pick a hypergraph coloring problem as a test case to illustrate this idea more coherently. Suppose one wishes to prove that a hypergraph that broadly satisfies certain pseudorandomness conditions may be edge colored using relatively few colors such that the resulting coloring satisfies certain nice properties, then an inductive argument would require us to pick a `small' collection of edges (which will be part of the first color class) such that the residual hypergraph (which may be defined in a variety of ways depending on the problem of interest) continues to enjoy the pseudorandom properties, albeit with `worse' error bounds than the original hypergraph. The art of this method is in fine-tuning this (random) step so that the residual hypergraph is as pseudorandom as the original, and the plethora of examples and proofs illustrate the power of this technique. This survey is a great addition to the literature that highlights this technique. The authors prefer to (for good reason) restrict their attention to problems and results concerning graph and hypergraph coloring problems (including list versions of these problems), and highlight many of the results and improvements of those results over the years by several researchers. The range of results they include is as good as it can get. The pièce de résistance is section 5 where they give detailed sketches of the authors' recent remarkable proof of the Erdős-Faber-Lovász conjecture for large \(n\). This section doubles as a good introduction to reading their paper and describes the iterative absorption process (finding absorbers at each step of an iterative process) in some detail, and yet the presentation is lucid and well-motivated. For the entire collection see [Zbl 1519.00033].