Let me introduce the question with an example. If we have the complete graph $K_n$ on $n$ vertices, and a subset of $\approx \frac{n}{\sqrt{3}}$ of the vertices, then they can define at most $\binom{n/\sqrt{3}}{2}\approx \frac{1}{3} \cdot \frac{n^2}{2}\approx \frac{1}{3} \binom{n}{2}$ edges. Another way to say this is that when we take more than one third of the possible $\binom{n}{2}$ edges of the complete graph $K_n$, then we have to cover at least $\approx\frac{n}{\sqrt{3}}$ vertices.

Are there arbitrarily large graphs (not necessarily complete) in which any set of $1/3$ of its edges covers a better proportion of the vertices? More precisely, is there an $\alpha>1/\sqrt{3}$ and a graphs with $n$ vertices ($n$ arbitrarily large) and $m$ edges such that any set of at least $\frac{m}{3}$ of its edges covers at least $\alpha n$ vertices?

Partial progress:

  • Complete and balanced bipartite graphs also yield $1/\sqrt{3}$.
  • I did some probabilistic method to try to prove that $1/\sqrt{3}$ is optimal. Given a graph on $n$ vertices and $m$ edges, if we choose a vertex with probability $\frac{1}{\sqrt{3}}$ then the expected number of chosen vertices is $\frac{n}{\sqrt{3}}$ and the expected number of edges is $\frac{m}{3}$. So intuitively there should be collection of at least $n/3$ edges that covers only near $\frac{n}{\sqrt{3}}$ vertices. But I am unsure on how to proceed here (inequalities, maybe?).
  • $\begingroup$ Ask it in MathOverFlow... $\endgroup$ – MR_BD Sep 30 '16 at 17:35
  • $\begingroup$ Have you got an answer? $\endgroup$ – Aqua Jan 31 '18 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.