Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
By Kuratowski, K_5, which gives a five by ten matrix with column sum 2. You might get a nine by six example with K3,3. Gerhard "Ask Me About Binary Matrices" Paseman, 2013.06.01 –  Gerhard Paseman Jun 1 '13 at 15:54
    
If a matrix can be realized this way, then deleting rows, deleting columns, and turning $1$s to $0$s$ will produce other matrices that can be realized this way, except potentially for some weird scenario with three lines tangent at a point. This gives a "minor" relation on matrices, and you might be able to find a finite, short list of forbidden minors. –  Will Sawin Jun 1 '13 at 16:48
    
@Will: so far, I don't have any single reasonably small forbidden minor, and neither have I any reason to believe that there are finitely many forbidden minors. –  Seva Jun 1 '13 at 17:44
    
@Gerhard: not quite. In fact, the incidence matrix of any graph (including $K_5$ and $K_{3,3}$) is realizable. For, one can represent the vertices by arbitrarily chosen points in the plane, and the edges by line segments joining the corresponding points. This way any two curves (segments) intersect in at most one point –  Seva Jun 1 '13 at 20:27
    
The smallest two matrices which are not linearly representible for trivial reasons are the Fano plane and affine space over $\mathbb F_3$ minus a point. You have shown how to draw the Fano plane. I think I know how to draw affine space over $\mathbb F_3$ minus a point, I'm going to figure out how to make a pretty picture to show you. This means that any bad configuration must have at least 9 vertices, decreasing the gap to just 4. I actually don't know if the dual result is true, that each bad configuration must have at least 9 edges. –  Will Sawin Jun 16 '13 at 18:25
show 3 more comments

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

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.

share|improve this answer
    
For your lower-bounding argument, do you claim that if $M$ is not realizable, then a matrix obtained from $M$ by removing a row with just two $1$s is not realizable either? If so, could you explain? (From a realization of the "shortened matrix", say $M'$, how can one get a realization of the original matrix $M$? Just adding a line segment may not work, as the realization of $M'$ can potentially involve curves which are not segments. It is not true that if a matrix is realizable, then it is realizable with segments only.) Similarly, why can one remove weight-$2$ columns? –  Seva Jun 2 '13 at 12:32
    
No. I am claiming that if $M$ is not realizable by straight lines, then removing such a row or column will not make it realizable. The reason for this should hopefully be clear, but since some things are realizable by curves and not straight lines, this can only provide a lower bound. By the way, I think the next couple arrangements to check are affine space over $\mathbb F_3$ and affine space over $\mathbb F_3$ minus a point. Can these be realizes by curves? –  Will Sawin Jun 2 '13 at 13:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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