Do all graphs with $n$ vertices and $m$ edges have a special property?

Question

Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.

For which values of $n$ and $m$ does the following requirement hold:

$\forall G \in \mathcal{G}$ there exist $V_1 \subset V,V_2 \subset V$ such that:

1. $(v_1 \in V_1 \land v_2 \in V_2) \implies \{v_1,v_2\} \in E$,
2. $|V_1||V_2|+|V_1|+|V_2| \gt n$?

Constraint $1$ is equivalent to say that $V_1$ and $V_2$ are the parts of an embedded complete bi-partite subgraph.

I am particularly interested in the case $n=53$ and $m=113$.

Since the above problem might be too difficult, a simpler one could be: how to design an algorithm (with a feasible time for $n=53$ and $m=113$) to decide whether a given graph $G \in \mathcal{G}$ satisfies or not the requirement?

Any hint?

Answer 1

For $n=53$ and $m=113$, you can't even get close in general. Take 7 copies of $K_5$ and 3 copies of $K_6$, all disjoint. Remove any two edges; now you have 53 vertices and 113 edges. No complete bipartite subgraph has more than 6 vertices. If you don't like disconnected graphs, delete 9 more edges without disconnecting any component and add 9 edges to connect the components into a path (the new edges forming bridges). Since bridges can't belong to complete bipartite graphs other than $K_{1,k}$ you still don't have complete bipartite subgraphs that are big enough.

Regarding practical algorithms for graphs of about this size, first note that if there is a large enough bipartite subgraph then there is one with the smallest side at most 6 vertices. $K_{6,7}$ is just big enough. Given $V_1\subseteq V$, the largest bipartite subgraph with one side equal to $V_1$ is given by $V_1$ plus all the common neighbours of $V_1$. So you can find the answer just by looking at all $\sum_{k=1}^6\binom{53}{k}=26144847$ subsets of size up to 6. For a computer that's not many.

For super-fast implementation, store the neighbours of each vertex as bit-vectors in 64-bit words. The common neighbours of a set are the bitwise AND of the neighbours of the vertices and almost all modern computers can count the 1-bits in a word in a single machine instruction. Make the subsets recursively (or as 6 nested loops if you don't need it too general) so you can give up on a branch of the search that already has too few or sufficiently many common neighbours. I'm confident that a running time which is a small fraction of a second in the worst case is possible.

Answer 2

Let $\psi(n)\approx\sqrt{n}$ denote the positive solution to $x^2+2x=n$. Note that if $|V_1||V_2|+|V_1|+|V_2|>n$, then either $|V_1|\geq \psi(n)$ or $|V_2|\geq \psi(n)$. This implies that all subgraphs which satisfy constraint $1$ have a vertex of degree at least $\psi(n)$.

Let $\phi(n)$ denote the largest even integer less than $\psi(n)$. If $m\leq n\phi(n)$, then there exists a graph $G\in\mathcal{G}$ that does not have this property. In particular, any $\phi(n)$-regular graph on $n$ vertices will not have this property. Thus, $m\geq \Omega(n^{1.5})$ is a necessary but not sufficient condition for this property. (As an additional note, you should be able to get a far superior lower bound via an application of the probabilistic method.)

For the specific case of $n=53$ and $m=113$, we can do better than the trivial brute force algorithm. Note that for $$|V_1||V_2|+|V_1|+|V_2|> 53$$ to be satisfied, either $|V_1|\geq 7$ or $|V_2|\geq 7$.

Fix $a\in [7,52]$, let $b$ be the smallest integer such that $ab+a+b>53$. Note $b\leq 6$. Find the set $U$ of all vertices with degree at least $a$. For each subset $S\in\binom{U}{b}$, check whether the common neighborhood of $S$ has at least $a$ vertices. The key idea is that because $G$ is sparse, $U$ cannot be too large. There are likely many tricks you could use to increase the speed of your implementation. For example, any vertex whose degree is less than $b$ cannot be part of the desired subgraph, so you could prune all low-degree vertices from your graph first. This is equivalent to saying that the desired subgraph (if it exists) must be contained in the $b$-core of your graph.