Bollobás–Erdős–Tuza conjecture

A graph on nn vertices is cc-hollow if every inclusion-maximal independent set has size at least cncn. Write τ(G)\tau(G) for the smallest size of a vertex set meeting all maximal independent sets. The conjecture says τ(G)=o(n)\tau(G)=o(n) for each fixed 0<c<10\lt c\lt1. 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 cc-hollow graphs requiring Ωc(n1/3/logn)\Omega_c(n^{1/3}/\log n) 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 0<c<10\lt c\lt1, there exist cc-hollow graphs on arbitrarily large numbers nn of vertices with τ(G)=Ωc(nlogn)\tau(G)=\Omega_c(\sqrt{n\log n}).

Construction. Fix an integer K≥1K\ge1 and 0<λ<1/40\lt\lambda\lt1/4 such that e−λK/(K+1)>ce^{-\lambda}K/(K+1)\gt c. Set η=λ/16\eta=\lambda/16, A=1/8A=1/8, and take a fixed κ>0\kappa\gt0 small enough that, with B=1+log(4/(κλ))B=1+\log(4/(\kappa\lambda)),

A+2λκ≤12,4κ(1+B)A<18.A+2\lambda\kappa\le \tfrac12,\qquad \frac{4\kappa(1+B)}{A}\lt\tfrac18 .

All logarithms in this proof are natural. Take a sufficiently large multiple ss of four. Set t=⌊κslogs⌋t=\lfloor\kappa s\log s\rfloor and r=⌈2t/(ηs)⌉r=\lceil2t/(\eta s)\rceil. Let HH be the join of rr parts, each a disjoint union of ss cliques of size ss. Thus between distinct parts all edges are present, while within a part only edges of its constituent cliques are present. Let M=rs2=|V(H)|M=rs^2=|V(H)| and add an independent set II of size KMKM. Connect each pair in V(H)×IV(H)\times I independently with probability p=λ/sp=\lambda/s. The resulting graph GG has order n=(K+1)rs2n=(K+1)rs^2.

All maximal independent sets are large. Each maximal independent set JJ of HH takes one vertex from each clique of one part. For fixed JJ, the number of vertices of II with no neighbour in JJ is binomial with mean KM(1−p)sKM(1-p)^s. Since K(1−p)s→Ke−λ>c(K+1)K(1-p)^s\to Ke^{-\lambda}\gt c(K+1), the probability that this count is below cncn is exp(−Ωc(M))\exp(-\Omega_c(M)) by a binomial lower-tail bound. There are rssr s^s choices for JJ. Consequently with probability tending to one every such JJ leaves at least cncn nonneighbours in II. Any independent subset of HH extends to such a JJ, so the same bound on nonneighbours holds for every independent subset of HH. In a maximal independent set of GG, all nonneighbours in II of its intersection with HH must be included. Thus GG is cc-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.

  1. For every Z⊆IZ\subseteq I with 1≤z=|Z|≤s/41\le z=|Z|\le s/4, and any z−1z-1 of the matching cliques, at least ηs\eta s vertices in the remaining matching cliques have a neighbour in ZZ.
  2. For every R⊆IR\subseteq I with s/4<|R|≤ts/4\lt |R|\le t, let j≥0j\ge0 be the index with 2−j−1t<|R|≤2−jt2^{-j-1}t\lt |R|\le2^{-j}t and put ℓj=⌊Alogs/(j+B)⌋\ell_j=\lfloor A\log s/(j+B)\rfloor. Among any s/4s/4 of the greedy cliques, at least ηs\eta s vertices have at least ℓj\ell_j neighbours in RR.

For property 1 there are at least s2/4s^2/4 candidate vertices. The probability that a candidate has a neighbour in ZZ is 1−(1−p)z≥λz/(2s)1-(1-p)^z\ge \lambda z/(2s), using pz≤1pz\le1 and 1−e−x≥x/21-e^{-x}\ge x/2 on [0,1][0,1]. The candidate indicators are independent. Their mean sum is at least λsz/8≥2ηs\lambda sz/8\ge2\eta s. The failure probability for fixed ZZ and excluded cliques is at most exp(−λsz/64)\exp(-\lambda sz/64). Over all parts the number of choices for order zz is at most r(KM)zsz−1r(KM)^z s^{z-1}, so the sum of the failure bounds tends to zero.

For property 2 we have j=O(loglogs)j=O(\log\log s) and hence ℓj≥1\ell_j\ge1 for large ss. Also

λκ42−jlogs≤p|R|≤λκlogs.\frac{\lambda\kappa}{4}\,2^{-j}\log s\le p|R|\le\lambda\kappa\log s.

For one vertex the binomial mass at ℓj\ell_j, using (uv)≥(u/v)v\binom{u}{v}\ge(u/v)^v and (1−p)|R|≥e−2p|R|(1-p)^{|R|}\ge e^{-2p|R|}, is at least

(p|R|ℓj)ℓje−2p|R|.\left(\frac{p|R|}{\ell_j}\right)^{\ell_j} e^{-2p|R|}.

By the lower bound on p|R|p|R|, we have max{0,log(ℓj/(p|R|))}≤j+B\max\{0,\log(\ell_j/(p|R|))\}\le j+B. The displayed probability is therefore at least s−A−2λκ≥s−1/2s^{-A-2\lambda\kappa}\ge s^{-1/2}. The s2/4s^2/4 candidate vertices have independent indicators, so their mean count is at least s3/2/4s^{3/2}/4. The probability they give fewer than ηs\eta s successes is exp(−Ω(s3/2))\exp(-\Omega(s^{3/2})). There are at most r2s∑u≤t(KMu)=exp(Oc(s(logs)2))r2^s\sum_{u\le t}\binom{KM}{u}=\exp(O_c(s(\log s)^2)) choices in property 2. This proves the simultaneous claim.

Avoiding a proposed transversal. Fix an outcome with the preceding properties and a vertex set TT of size at most tt. Some part of HH contains at most t/r≤ηs/2t/r\le\eta s/2 vertices of TT. Work in that part, removing its vertices in TT from consideration. Start with R=T∩IR=T\cap I. While |R|>s/4|R|\gt s/4, choose a vertex from an unused greedy clique with at least ℓj\ell_j neighbours in RR, and remove those neighbours from RR. For large ss we have ℓj≥Alogs/(2(j+B))\ell_j\ge A\log s/(2(j+B)) for every relevant jj. At scale jj there are at most 1+2−jt/ℓj1+2^{-j}t/\ell_j greedy choices, so in total there are at most

O(loglogs)+2κsA∑j≥02−j(j+B)=O(loglogs)+4κ(1+B)As<s/4.O(\log\log s)+\frac{2\kappa s}{A}\sum_{j\ge0}2^{-j}(j+B) =O(\log\log s)+\frac{4\kappa(1+B)}{A}s\lt s/4 .

Thus at every step at least s/4s/4 greedy cliques are unused. Property 2 provides the required choice even after the deletions.

After this process |R|≤s/4|R|\le s/4. Match RR to distinct matching cliques, joining a vertex of RR to a clique if it has a neighbour among its unremoved vertices. If a nonempty set Z⊆RZ\subseteq R had at most |Z|−1|Z|-1 adjacent cliques, we could exclude |Z|−1|Z|-1 matching cliques containing all of them. Property 1 would then give at least ηs\eta s 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 JJ of HH disjoint from TT. Every vertex in T∩IT\cap I is adjacent to JJ. Add to JJ all vertices of II with no neighbour in JJ. The result is a maximal independent set of GG disjoint from TT.

This proves τ(G)>t\tau(G)\gt t. Since r=Θc(logs)r=\Theta_c(\log s) and n=(K+1)rs2n=(K+1)rs^2, we have t=Θc(nlogn)t=\Theta_c(\sqrt{n\log n}), as claimed.

Limit of the random construction

More generally, suppose each of the rr joined parts of HH consists of ss cliques of size bb and the independent set II still has size KrsbKrsb. Each maximal independent set of GG is determined by its intersection with HH. This intersection is empty or comes from one part, with at most one vertex per clique. Thus there are at most 1+r(b+1)s1+r(b+1)^s maximal independent sets. If GG is cc-hollow, a uniform random sample hits them all with positive probability once its size is Oc(slog(b+1)+log(r+1))O_c(s\log(b+1)+\log(r+1)). With independent cross-edge probability λ/s\lambda/s, a vertex in II has expected degree λrb\lambda r b. With probability at least 1−2−|I|1-2^{-|I|} some vertex in II has degree at most 2λrb2\lambda r b. Its closed neighbourhood meets every maximal independent set. On this event the two bounds give

τ(G)=Oc(min{rb,slog(b+1)+log(r+1)})=Oc(nlogn).\tau(G) =O_c\!\left(\min\{rb,s\log(b+1)+\log(r+1)\}\right) =O_c(\sqrt{n\log n}).

The final estimate follows by bounding the minimum of rbrb and slog(b+1)s\log(b+1) by their geometric mean, and using n=(K+1)rsbn=(K+1)rsb. The construction attains this order for every fixed cc. The conjectured sublinear upper bound for arbitrary cc-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 k≥2k\ge2 if it can be built from single vertices by substitution into quotient graphs on at most kk 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 i(G)i(G) for the minimum size of a maximal independent set. Every nonempty graph GG of modular width at most k≥2k\ge2 satisfies

τ(G)≤(|V(G)|i(G))4k+1.\tau(G)\le \left(\frac{|V(G)|}{i(G)}\right)^{4k+1}.

In particular, τ(G)≤c−(4k+1)\tau(G)\le c^{-(4k+1)} for every cc-hollow graph in this class, with no bound on the number of substitution levels. Cooper–Hollars give the sharper estimate τ(G)≤1/c\tau(G)\le 1/c for cographs. Cooper–Hollars, Section 5

Packing lemma. For at most kk items of weights wj∈(0,1)w_j\in(0,1) there is a random subset of total weight strictly below 11 with inclusion probabilities at least 1−wj1/(4k)1-w_j^{1/(4k)}.

Set a=1/(4k)a=1/(4k) and call an item large if its weight is at least 1/21/2. Give each large item vv a disjoint interval inside [0,1][0,1] of length ev=1−wvae_v=1-w_v^a. The intervals fit because ev≤alog2e_v\le a\log 2 and their total length bb is at most 1/41/4. Choose a uniform point in [0,1][0,1]. If it belongs to the interval for vv, take vv and every small item of weight strictly below (1−wv)/k(1-w_v)/k. This subset has weight strictly below 11. The unconditional probability AjA_j that a small item jj is omitted in the union of the intervals satisfies

Aj≤min{b,2ak2wj}.A_j\le \min\{b,2ak^2w_j\}.

Indeed, omission from the subset in the interval of vv requires 1−wv≤kwj1-w_v\le kw_j, and 1−wva≤2a(1−wv)1-w_v^a\le 2a(1-w_v) by the mean value theorem on [1/2,1][1/2,1]. Thus Aj≤wjaA_j\le w_j^a. For wj≥1/(2k)w_j\ge 1/(2k) this follows from b≤1/4b\le 1/4 and (2k)−a≥1/2(2k)^{-a}\ge 1/2. For wj≤1/(2k)w_j\le 1/(2k) it follows from the comparison at 1/(2k)1/(2k) and from the fact that wj1−aw_j^{1-a} is increasing.

On the complement of those intervals, use only the small items with conditional inclusion probabilities

zj=max{0,1−wja−b+Aj}1−b.z_j=\frac{\max\{0,\,1-w_j^a-b+A_j\}}{1-b}.

These numbers lie in [0,1][0,1] and ensure the required total probabilities. The conditional expected weight satisfies

L=∑jwjzj≤a1−b∑jwjlog(1/wj)≤13.L=\sum_j w_jz_j \le \frac{a}{1-b}\sum_j w_j\log(1/w_j) \le \frac13.

To realize the prescribed probabilities, decompose (zj)j(z_j)_j into extreme points of the polytope 0≤yj≤10\le y_j\le1, ∑jwjyj=L\sum_j w_jy_j=L. 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 L+1/2<1L+1/2\lt1. This completes the proof of the packing lemma.

Weighted transversal lemma. Let ℱ\mathcal F be a nonempty family of nonempty subsets on at most kk indices. Suppose xj,qj>0x_j,q_j\gt0, that ∑j∈Fxj≥1\sum_{j\in F}x_j\ge1 for every F∈ℱF\in\mathcal F, and that ∑jqj=1\sum_j q_j=1. For p=4k+1p=4k+1, there is a transversal TT with

∑j∈T(qj/xj)p≤1.\sum_{j\in T}(q_j/x_j)^p\le1.

Set rj=qj/xjr_j=q_j/x_j. If every rj≥1r_j\ge1, then 1≤∑jxj≤∑jqj=11\le\sum_j x_j\le\sum_j q_j=1. All ratios equal one and every member of ℱ\mathcal F contains every index. A singleton suffices. Otherwise apply the packing lemma to the weights rjpr_j^p for indices with rj<1r_j\lt1. This gives a random set TT of cost less than one. For each of those indices the omission probability is at most rjp/(4k)<rjr_j^{p/(4k)}\lt r_j. At the other indices the omission probability is 1≤rj1\le r_j. Hence the expected xx-weight of the indices outside TT is strictly below ∑jxjrj=1\sum_j x_jr_j=1. Some outcome leaves outside weight below one, so its TT hits every member of ℱ\mathcal F.

Substitution. For a quotient QQ with substituted graphs GjG_j, the maximal independent sets of the result GG are precisely the unions of maximal independent sets of the GjG_j over a maximal independent set of QQ. 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 GG outside the union. Put nj=|V(Gj)|n_j=|V(G_j)|, ij=i(Gj)i_j=i(G_j), n=∑jnjn=\sum_j n_j and m=i(G)=minS∈MIS(Q)∑j∈Sijm=i(G)=\min_{S\in\operatorname{MIS}(Q)}\sum_{j\in S} i_j. Take qj=nj/nq_j=n_j/n and xj=ij/mx_j=i_j/m. The weighted transversal lemma supplies a set TT of quotient vertices hitting all its maximal independent sets. The union of transversals in modules indexed by TT hits every maximal independent set of GG. By induction from a single vertex, its size is at most

∑j∈T(nj/ij)p=(nm)p∑j∈T(qj/xj)p≤(nm)p.\sum_{j\in T}(n_j/i_j)^p =\left(\frac{n}{m}\right)^p \sum_{j\in T}(q_j/x_j)^p \le \left(\frac{n}{m}\right)^p.

The same proof gives h(G)≤(|V(G)|/α(G))4k+1h(G)\le (|V(G)|/\alpha(G))^{4k+1} for the maximum-independent-set conjecture, where hh 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 α(Gj)\alpha(G_j), and the chosen sets inside the occupied modules must be maximum independent sets there.