When is a 0-1 matrix a one-intersection incidence matrix?

Question

The following problem is what motivated my previous MO question.

It is easily seen that for any given 0-1 matrix $M$, one can always find a set $\mathcal P$ of points, and a set $\mathcal C$ of simple curves in the plane, so that their incidence matrix is exactly the matrix $M$. Suppose, however, that any pair of curves from $\mathcal C$ is now allowed to intersect in at most one point (be it a point of $\mathcal P$ or any other point), and let's say that the matrix $M$ is realizable if such $\mathcal P$ and $\mathcal C$ can be found. Clearly, a necessary condition for this is that the scalar product of any two rows of $M$ be at most $1$, but this condition is insufficient: say, for $q$ large enough, by the Szemeredi-Trotter theorem, the point-line incidence matrix of the finite projective plane $PG(2,q)$ has two many incidences to be realizable. What are other reasonable necessary / sufficient conditions for $M$ to be realizable? What are "small" examples of non-realizable 0-1 matrices?

---

Added June 03, 2013

Here is a very specific question along these lines. Everything I presently can say on the problem above is essentially symmetric in $\mathcal P$ and $\mathcal C$. This suggests that, perhaps, there is some duality between points and curves involved. Accordingly, I wonder whether, by any chance, it can be true that $M$ is realizable if and only if its transpose $M^t$ is realizable?

Answer 1

(I suspect a lot of this is known to Seva, but it's probably helpful to have it written down.)

One lower-bounding argument: Anything that's representable by lines and points is representable by curves and points. When checking if this is so, we can delete any row with just two $1$s, as you can draw a line between any two points. (this generalizes Seva's point in the comments.) Similarly, there is no need for lines to be parallel, so we can delete a column with just two $1$s. Thus we can assume that every row and column has at least three $1$s, which gives a minimum of $7$ vertices: One vertex must be on three edges, each of which contains two other vertices. This is attained uniquely by the Fano plane.

To get an upper-bounding argument, we just need an effective Szemeredi-Trotter theorem. We can do this just by looking at the proof, e.g. on Wikipedia. We construct a graph whose number of edges $e$ is just the number of $1$ entries of the matrix, minus the number of rows. Using the explicit bound $e \leq 4 n$ or $e\leq \left(64 m^2/n^2\right)^{1/3}$. This gives an explicit inequality.

For the projective plane over $\mathbb F_q$, we have $n= q^2+q+1$, $m=q^2+q+1$, $e = q (q^2+q+1)$. Thus it can only be representible for $q \leq 4$. So the projective plane over $\mathbb F_5$ is an example. I guess this isn't very reasonably small.

I think a simple Euler characteristic bound might work better. If there are $P$ points and $C$ curves, $I$ incidences, and $c$ bonus crossings where two curves cross away from a points, we get a graph in the plane with $P+c$ vertices and $I-C +2c$ edges, so it has $2+I+c-P-C$ faces. With the inequality $3F \leq 2E$, since two curves cannot intersect in more than two points, so all faces are triangles are larger, we get the inequality:

\[ 6+ 3I + 3c -3P - 3C \leq 2I - 2C+4c\]

\[ I \leq 3P + C + c-6\]

For the projective plane, $c=0$ because each pair of edges already intersect at a point. $I=(q+1)(q^2+q+1)$, $P=q^2+q+1$, $C=q^2+q+1$, so we get

\[(q+1)(q^2+q+1) \leq 4 (q^2+q+1) - 6\]

which improves it to the projective plane over $\mathbb F_3$.

The main explanation for the gap between the lower bounding technique and the lower bounding technique is that the first one always makes curves going off to infinity. If the curves went off to infinity, the Fano plane would no longer be possible.