Quasi-Random Set Systems

There are many properties of mathematical objects that satisfy what is some-times called a 0-1 law, in the following sense. Under some natural probability measure on the set of objects, the measure of the subset of objects having the given property is either 0 or 1. In the latter case we can say that almost all the objects have the property. Familiar examples of this phenomenon are the following: almost all real numbers are transcendental (or normal to every base), almost all integers are composite, almost all continuous real functions are non-differentiable, etc. It is often the case that the objects under consideration can be partitioned into a countable number of finite classes \(C_ n\), with the probability assigned to an object in \(C_ n\) being just \(1/| C_ n|\). In this case, we say that a property \(P_ n\) satsifies a \(0-1\) law if the fraction of the number of objects in \(C_ n\) that satisfy \(P_ n\) either tends to 0 or tends to 1 as \(n\to\infty\). For example, almost all graphs on \(n\) vertices have maximum cliques and maximum independent sets of size at most \(2\log n\), almost all Boolean functions with \(n\) variables have circuit complexity \((1+o(1))2^ n\) and almost all binary codes of length \(n\) with at most \(2^{nR}\) codewords (with \(R\) less than the binary symmetric channel capacity \(C)\) have arbitrarily small error probability (a special case of Shannon's coding theorem; see \textit{C. Shannon} [Bull. System Tech. J. 27, 379-423 (1948)]). One of the first general results of this type was the theorem of \textit{R. Fagin} [J. Symb. Log. 41, 50-58 (1976; Zbl 0341.02044)] and \textit{Y. V. Glebskii} et al. [Kibernetika 2, 31-42 (1969)], which asserts that every property of graphs that can be expressed in first-order logic satisfies a \(0-1\) law (see \textit{S. Shelah} and \textit{J. Spencer} [J. Am. Math. Soc. 1, No. 1, 97-115 (1988; Zbl 0647.05051)] for recent striking developments in this topic). One obvious method for finding explicit objects having some property \(P_ n\) shared by almost all objects in \(C_ n\) is simply to select one at random. With overwhelming probability (tending to 1 as \(n\to\infty)\), the selected object will have property \(P_ n\). Unfortunately, it may be (and often is) extremely difficult to prove that any particular object does indeed satisfy \(P_ n\). It is our purpose in this paper to describe a method that can to a certain extent circumvent this difficulty. We will show that, for a variety of families, it is possible to identify a natural hierarchy of equivalence classes of properties, all of which are shared by almost all objects in the family. Any object satisfying some property in one of the equivalence classes must of necessity satisfy all of the properties in that class, even though various properties in a class may appear (at first) to be unrelated to each other. Furthermore it is typically easy to verify at least one of the properties in a class (depending upon how the particular object is given), thereby establishing that all the properties in the class hold. Our main focus in this paper will be on combinatorial objects known as hypergraphs, which are the natural generalizations of graphs (cf. \textit{C. Berge} [Hypergraphs. Combinatorics of finite sets. Transl. from the French (1989; Zbl 0674.05001)]). Extensions of these ideas to other structures will be discussed at the end of the paper.

Recommendations

Cites work

Cited in

(44)

This page was built for publication: Quasi-Random Set Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4713353)