A graph on vertices is -hollow if every inclusion-maximal independent set has size at least . Write for the smallest size of a vertex set meeting all maximal independent sets. The conjecture says for each fixed . Taking graph complements gives the first question in Erdős Problem 611. Erdős–Gallai–Tuza, Problem 2 · Erdős Problems wiki · Research issue
Cooper and Hollars give -hollow graphs requiring vertices in a transversal. Their conjecture concerns all maximal independent sets. The separate Bollobás–Erdős–Tuza conjecture concerning only maximum independent sets has a weaker hypothesis on the independence number and uses different methods. Searches by both formulations, the problem number and the authors' names found no resolution of the maximal version or prior occurrence of the lower bound below. Cooper–Hollars, Conjectures 1.1 and 1.2 and Theorem 1.7 · Bai–Chang–Yan on maximum independent sets
A lower bound of order the square root of n log n
Theorem. For each fixed , there exist -hollow graphs on arbitrarily large numbers of vertices with .
Construction. Fix an integer and such that . Set , , and take a fixed small enough that, with ,
All logarithms in this proof are natural. Take a sufficiently large multiple of four. Set and . Let be the join of parts, each a disjoint union of cliques of size . Thus between distinct parts all edges are present, while within a part only edges of its constituent cliques are present. Let and add an independent set of size . Connect each pair in independently with probability . The resulting graph has order .
All maximal independent sets are large. Each maximal independent set of takes one vertex from each clique of one part. For fixed , the number of vertices of with no neighbour in is binomial with mean . Since , the probability that this count is below is by a binomial lower-tail bound. There are choices for . Consequently with probability tending to one every such leaves at least nonneighbours in . Any independent subset of extends to such a , so the same bound on nonneighbours holds for every independent subset of . In a maximal independent set of , all nonneighbours in of its intersection with must be included. Thus is -hollow.
Adjacencies in a part. Reserve half the cliques of each part for matching, and use the other half for greedy choices. We prove that with probability tending to one the following hold in every part at once.
- For every with , and any of the matching cliques, at least vertices in the remaining matching cliques have a neighbour in .
- For every with , let be the index with and put . Among any of the greedy cliques, at least vertices have at least neighbours in .
For property 1 there are at least candidate vertices. The probability that a candidate has a neighbour in is , using and on . The candidate indicators are independent. Their mean sum is at least . The failure probability for fixed and excluded cliques is at most . Over all parts the number of choices for order is at most , so the sum of the failure bounds tends to zero.
For property 2 we have and hence for large . Also
For one vertex the binomial mass at , using and , is at least
By the lower bound on , we have . The displayed probability is therefore at least . The candidate vertices have independent indicators, so their mean count is at least . The probability they give fewer than successes is . There are at most choices in property 2. This proves the simultaneous claim.
Avoiding a proposed transversal. Fix an outcome with the preceding properties and a vertex set of size at most . Some part of contains at most vertices of . Work in that part, removing its vertices in from consideration. Start with . While , choose a vertex from an unused greedy clique with at least neighbours in , and remove those neighbours from . For large we have for every relevant . At scale there are at most greedy choices, so in total there are at most
Thus at every step at least greedy cliques are unused. Property 2 provides the required choice even after the deletions.
After this process . Match to distinct matching cliques, joining a vertex of to a clique if it has a neighbour among its unremoved vertices. If a nonempty set had at most adjacent cliques, we could exclude matching cliques containing all of them. Property 1 would then give at least candidate neighbours in the remaining cliques, more than were removed. Hall's theorem therefore gives the matching. Use one neighbour from each matched clique and fill all other unused cliques with any unremoved vertex. Together with the greedy choices this gives a maximal independent set of disjoint from . Every vertex in is adjacent to . Add to all vertices of with no neighbour in . The result is a maximal independent set of disjoint from .
This proves . Since and , we have , as claimed.
Limit of the random construction
More generally, suppose each of the joined parts of consists of cliques of size and the independent set still has size . Each maximal independent set of is determined by its intersection with . This intersection is empty or comes from one part, with at most one vertex per clique. Thus there are at most maximal independent sets. If is -hollow, a uniform random sample hits them all with positive probability once its size is . With independent cross-edge probability , a vertex in has expected degree . With probability at least some vertex in has degree at most . Its closed neighbourhood meets every maximal independent set. On this event the two bounds give
The final estimate follows by bounding the minimum of and by their geometric mean, and using . The construction attains this order for every fixed . The conjectured sublinear upper bound for arbitrary -hollow graphs remains open.
A constant upper bound for bounded modular width
The conjecture holds with a constant upper bound for graphs of bounded modular width. Here a graph has modular width at most if it can be built from single vertices by substitution into quotient graphs on at most vertices. Substitution replaces each quotient vertex by a nonempty graph, with all edges between two substituted graphs precisely when their quotient vertices are adjacent. Arbitrary disjoint unions and joins can be built using binary substitutions. This agrees with the convention of bounding the arity of the prime nodes in a modular decomposition. Maximal clique decompositions by modular width, Section 6.2
Theorem. Write for the minimum size of a maximal independent set. Every nonempty graph of modular width at most satisfies
In particular, for every -hollow graph in this class, with no bound on the number of substitution levels. Cooper–Hollars give the sharper estimate for cographs. Cooper–Hollars, Section 5
Packing lemma. For at most items of weights there is a random subset of total weight strictly below with inclusion probabilities at least .
Set and call an item large if its weight is at least . Give each large item a disjoint interval inside of length . The intervals fit because and their total length is at most . Choose a uniform point in . If it belongs to the interval for , take and every small item of weight strictly below . This subset has weight strictly below . The unconditional probability that a small item is omitted in the union of the intervals satisfies
Indeed, omission from the subset in the interval of requires , and by the mean value theorem on . Thus . For this follows from and . For it follows from the comparison at and from the fact that is increasing.
On the complement of those intervals, use only the small items with conditional inclusion probabilities
These numbers lie in and ensure the required total probabilities. The conditional expected weight satisfies
To realize the prescribed probabilities, decompose into extreme points of the polytope , . Each extreme point has at most one fractional coordinate, since two such coordinates could move in opposite weighted directions. Sample an extreme point according to the decomposition and round its fractional coordinate up with probability equal to its value. The resulting subset has weight at most . This completes the proof of the packing lemma.
Weighted transversal lemma. Let be a nonempty family of nonempty subsets on at most indices. Suppose , that for every , and that . For , there is a transversal with
Set . If every , then . All ratios equal one and every member of contains every index. A singleton suffices. Otherwise apply the packing lemma to the weights for indices with . This gives a random set of cost less than one. For each of those indices the omission probability is at most . At the other indices the omission probability is . Hence the expected -weight of the indices outside is strictly below . Some outcome leaves outside weight below one, so its hits every member of .
Substitution. For a quotient with substituted graphs , the maximal independent sets of the result are precisely the unions of maximal independent sets of the over a maximal independent set of . The occupied modules must be independent and maximal in the quotient, and the chosen sets within them must be maximal there. Conversely those two properties dominate every vertex of outside the union. Put , , and . Take and . The weighted transversal lemma supplies a set of quotient vertices hitting all its maximal independent sets. The union of transversals in modules indexed by hits every maximal independent set of . By induction from a single vertex, its size is at most
The same proof gives for the maximum-independent-set conjecture, where is the minimum size of a transversal of all maximum independent sets. In this case the quotient family consists of maximum-weight independent sets, with module weights , and the chosen sets inside the occupied modules must be maximum independent sets there.