Return to Answer

(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$.

(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.

(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$.

(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$.

(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(q^2+q+1)$, $P=q^2+q+1$, $C=q^2+q+1$, so we get

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

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

(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$.