Sublinear clique transversals under a large-clique hypothesis: is $\tau(G)=o_c(n)$? (Erdős #611)
Statement
For a graph $G$ on $n$ vertices, the clique transversal number $\tau(G)$ is the minimum number of vertices meeting every maximal clique of $G$ (an inclusion-maximal complete subgraph). Fix $c>0$. Is it true that if every maximal clique of $G$ has at least $cn$ vertices, then $\tau(G)=o_c(n)$ — that is, $\tau(G)/n\to0$ as $n\to\infty$ for each fixed $c$? More precisely, estimate the least $k_c(n)$ such that whenever every maximal clique of $G$ has at least $k_c(n)$ vertices, $\tau(G)<(1-c)n$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) that for every fixed $c>0$, having all maximal cliques of size $\geq cn$ forces $\tau(G)=o_c(n)$; OR a disproof — an explicit family of graphs with all maximal cliques of size $\geq cn$ yet $\tau(G)\gg n$, with proof. A determination of the threshold growth $k_c(n)$ up to constant factors also fully resolves the quantitative form. ADVANCES: improve either known bound on $k_c(n)$ beyond those in the background — the lower bound $k_c(n)\geq n^{c'/\log\log n}$, or the transversal bound $\tau(G)\leq n-(kn)^{1/2}$ — with proof; OR prove the sublinear-transversal conclusion for a natural subclass of graphs with proof; OR compute $\tau(G)$ exactly for explicit large-clique families up to a new size via reproducible ILP search with a certificate, charting $k_c(n)$ empirically. Deliver the proof file, the improved-bound proof, or the search code plus certified results.
Background
A problem of Erdős, Gallai, and Tuza [EGT92], reiterated in [Er94; Er99]. Known bounds: for the threshold question they proved $k_c(n)\geq n^{c'/\log\log n}$ for some $c'>0$, and that if every maximal clique has size at least $k$ then $\tau(G)\leq n-(kn)^{1/2}$. Bollobás and Erdős established a sharp endpoint: if every maximal clique has at least $n+3-2\sqrt{n}$ vertices then $\tau(G)=1$, and this threshold is best possible. The general behaviour of $\tau(G)$ is the subject of erdosproblems.com/610, and the companion inequality $\tau(G)\le n-H(n)$ is Erdős #151 (erdosproblems.com/151). Listed as open on erdosproblems.com/611 (fetched 2026-07-13, status 'open', tagged 'graph theory'). No Erdős prize is attached. The attacker's tool: ILP-based computation of $\tau(G)$ (minimum clique transversal as a hitting set over the maximal cliques) on graphs engineered to have all maximal cliques large, to probe the growth of $k_c(n)$ and hunt for extremal configurations, alongside probabilistic constructions for lower bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #611 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.