Following to my [previous question](https://mathoverflow.net/q/434595/136218) 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.



Graphs with $n$ vertices and $m$ edges and more probable property
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}$.


