Graphs with $n$ vertices and $m$ edges and more probable property

Question

Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail.

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 exists at least one complete $k$-partite subgraph of $G$ with $2 \le k \le n$ and with parts $V_1, \ldots ,V_k$ such that:

$$\prod_{j=1}^k (1+|V_j|)-1 \gt \frac{4n}{3}?$$

In particular I am interested in the case $n=39$ and $m=113$. With respect to the previous question, I have lowered $n$ but increased the minimum of the expression to $4n/3$. I am not sure how to adapt the counterexamples there to this generalization of the problem.

Answer 1

There is a $C_4$-free bipartite graph $B$ with 19 vertices on one side, 20 vertices on the other side, and 92 edges. Its vertices have degree 4 or 5, so it is easy to find a path $P$ of 21 edges in $K_{19,20}-B$. Now consider the 113-edge union $G=B\cup P$.

Since $G$ is bipartite, it has no complete multipartite subgraph other than complete bipartite graphs. Now by inspection $K_{2,6}$, $K_{3,5}$ and $K_{4,4}$ still contain $C_4$ if a path or fragments of a path is removed, so $G$ doesn't contain them. Also the degree of $G$ is at most 7. So the only complete bipartite graphs that $G$ might contain are $K_{1,1},\ldots,K_{1,7},K_{2,2},K_{2,3},K_{2,4},K_{2,5},K_{3,3},K_{3,4}$. The maximum possible $\prod (|V_i|+1)-1$ is 19 if $K_{3,4}$ is present. Probably it is possible to choose $P$ so that $K_{3,4}$ is avoided, in which case the maximum would be 17.

Here is the $20\times 19$ incidence matrix of $B$. Actually the same argument works with any $C_4$-free bipartite graph with at least 78 edges and no vertices of very high degree. There are very many choices.

  1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
  1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0
  0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
  1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0
  0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
  0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
  0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0
  1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0
  0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0
  0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0
  0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0
  0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0
  0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0
  0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1
  0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
  0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0
  0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0
  0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0
  0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1
  0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1

ADDED: Instead of choosing $P$ as a single path, choose vertex-disjoint paths of 1 or 2 edges. Now (needs checking) I think that $G$ can't even contain $K_{3,3}$.