A projective plane $Π$ is a 3-tuple $(P,L,I)$ where $P$ and $L$ are sets, and $I$ is a relation between $P$ and $L$, such that:

  • For every two elements $p_1$, $p_2\in P$, there exists a unique element $l \in L$ such that $p_1 I l$ and $p_2 I l$.

  • For every two elements $l_1$, $l_2\in P$, there exists a unique element $p \in L$ such that $p I l_1$ and $p I l_2$.

A finite projective plane is a projective plane where $P$ and $L$ are finite.

Identify projective planes with the bipartite graph with two parts $P$ & $L$ where $p\in P$ is connected to $l \in L$ iff $pIl$.

Such graphs do not have $C_4$ as a subgraph: Suppose there's a $C_4$ subgraph formed by the vertices $p_1,l_1,p_2,l_2$ where $p_1$ and $p_2$ are both connected to $l_1$ and $l_2$. Then the element $l$ where $p_1 I l$ and $p_2 I l$ is not unique, thus violating the rules. Their induced subgraphs has no $C_4$s, either.

Q: Is the converse true, i.e. if $G$ is a $C_4$-free bipartite graph, is there a projective plane $Π$ where $G$ is an induced subgraph of $Π$?

One cannot expect the conjecture above holding for finite-field planes: Let $Γ$ be the Desagures graph. Let $e$ be an edge of $Γ$(The Desagures graph is edge-transitive, so all edges are the same) .

The Desagures theorem states, if the configuration $Γ\e$ can be found in a finite-field plane, then the edge $e$ is also present there. So $Γ\e$ is not an induced subgraph of any finite-field plane.

Known: All graphs with 13 vertices or less are subgraphs of finite-field projective planes, as checked by computer.

By the Lefschetz principle, if $G$ is a subgraph of the incidence graph of $\mathbb{RP}^2$, then $G$ is the subgraph of an incidence graph of some finite-field plane. So trees satisfy the conjecture.


This is an open problem posed by Erdos in "Some old and new problems in various branches of combinatorics" (see section 6). There hasn't been any substantial progress since then. After posing the question Erdos writes "I have no idea how to attack this problem", and that seems to be state of the art.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.