The maximal complete bipartite subgraphs of the partition graph $\mathcal{P}(3^3)$. The concept of a partition graph is similar to the Kneser graph concept.

Every vertex of a partition graph $\mathcal{P}(g^g)$ is a partition of $\{1,2, ..., g^2 \}$ into $g$ cells of size $g$. Two vertices $u$ and $v$ are adjacent if the intersection of each cell of $u$ with each cell of $v$ be nonempty.

I am working on $\mathcal{P}(3^3)$. The vertices of this graph are partitions of $\{1,2, ..., 9\}$ into $3$ cells of size $3$, and two vertices $u$ and $v$ are adjacent if each cell of $u$ has an element in each cell of $v$.
I am looking for all maximal complete bipartite subgraphs of this graph. I have already managed to find $K_{1,36}$ (th degree of each vertex is $36$), $K_{2,2}$, $K_{4,4}$, $K_{6,4}$, $K_{2,12}$.
I am not looking for the number of complete bipartite subgraphs, I need to find all maximal complete bipartite subgraphs. Any help would be appreciated.
 A: The situation here is as follows. (Excuse me for repeating your conclusions.)

*

*In fact, in the graph $G$ there exists a complete subgraph $K_{1,36}$ simply because the degree of each vertex of the graph $G$ is $36$.


*Then there exists a subgraph $K_{2,12}$ and no subgraph $K_{2,n}$ with $n>12$.


*There exists a subgraph $K_{4,6}$ and no subgraphs $K_{4,n}$ with $n>6$.


*There are no subgraphs $K_{m,n}$ with $m\leq n$ and $m>4$ and $K_{3,n}$ with $n>6$.
This follows from this consideration.
For each fixed vertex $v$ there exists a set $U$ of vertices $G$ such that $|U|=27$ and $v,x$ have exactly $12$ common neighbors for each $x\in U$ and no more than $4$ neighbors for each $x\notin U$.
Then all complete bipartite subgraphs containing a fixed vertex $v$ and several vertices of $U$ are easily computed.
To summarize, you have actually listed all possible complete bipartite subgraphs of $G$. Apparently, if $G$ contains a subgraph $K_{m,n}$, then $G$ also contains a subgraph $K_{r,s}$ for any $r\leq m$ and $s\leq n$.
I will add more: this is a remarkable question.
Sketch of the proof.
Since the group of permutations $S_9$ lies in the group of automorphisms of the graph $G$, that is, $S_n\leq\operatorname{Aut}(G)$, we can assume that $v=(123)(456)(789)$.
Denote by $N_G(v,x)$ the set of all common neighbors of $v$ and $x$.
It is not difficult to prove that $|N_G(v,x)| =12$ if $x$  has the form $(123)(\cdots)(\cdots)$ or $(\cdots)(456)(\cdots)$ or $(\cdots)(\cdots)(789)$.
If $x$  has the form $(1\cdot\cdot)(2\cdot\cdot)(3\cdot\cdot)$, then $|N_G(v,x)|=2$.
If $x$  has the form $(12\cdot)(3\cdot\cdot)(\cdots)$ or $(13\cdot)(2\cdot\cdot)(\cdots)$ or $(23\cdot)(1\cdot\cdot)(\cdots)$
and the last bracket is not $(456)$ or $(789)$, then $|N_G(v,x)|=4$.
It follows that if the vertices $v, x_1,\ldots,x_s$, $s\geq1$, have more than four common neighbors, then they all have a common cell. We can assume that the common cell is $(123)$.
There are $10$ vertices having cell $(123)$ including $v$. We can assume that $x_1=(123)(457)(689)$ (for the third time we use that $S_n\leq\operatorname{Aut}(G)$). Now there are $8$ possibilities for choosing $x_2$. I haven't come up with anything other than a brute force, but the brute force is very small. The result is $|N_G(v,x_1,x_2)|\leq6$.
And so on.
