An incidence geometry is a set $P$ (the "points"), a set $L$ (the "lines"), and a relation $I\subseteq P\times L$ ("incidence"). Equivalently, a bipartite graph with the halves of the partition labeled by $P$ and $L$.

A projective plane is an incidence geometry satisifying the following axioms:

  1. For every pair of distinct points, there is a unique line incident to both of them.
  2. For every pair of distinct lines, there is a unique point incident to both of them.
  3. (Non-degeneracy) There are $4$ points, no $3$ of which are collinear.

Equivalently, a bipartite graph with no subgraph isomorphic to the complete bipartite graph $K_{2,2}$, but such that any subgraph isomorphic to a subgraph of $K_{2,2}$ is contained in a subgraph isomorphic to a maximal proper subgraph of $K_{2,2}$. Plus non-degeneracy. Replacing $2$ and $2$ with $m$ and $n$ gives the following natural generalization:

A $(m,n)$-pseudoplane is an incidence geometry satisfying the following axioms:

  1. For every $m$ distinct points, there are exactly $(n-1)$ distinct lines which are incident to all of them.
  2. For every $n$ distinct lines, there are exactly $(m-1)$ distinct points which are incident to all of them.

It's possible that there is a natural non-degeneracy axiom to include, but the correct formulation is not clear to me. (See update below)

I recently wrote a paper with Gabe Conant studying the model theory of existentially closed projective planes, and we were led to define $(m,n)$-pseudoplanes when we realized that almost all of our results generalized easily to these structures. But we have had trouble locating them in the combinatorics literature. For example, they do not appear to be mentioned explicitly in the Handbook of Combinatorial Designs (though it's entirely possible I overlooked them in that massive tome!).

Question: What is known about $(m,n)$-pseudoplanes? Do they appear under a different name in the literature? I would appreciate any and all references.

Update: In Summer 2018, my REU student Matisse Peppet and I investigated the combinatorics of $(m,n)$-pseudoplanes (when $m,n\geq 2$). I hope you will forgive me bumping this question and advertising Matisse's results below; we are preparing a paper on the topic, and I am still looking for references to $(m,n)$-pseudoplanes in the combinatorics literature. Of course, I especially want to know if any of the results below are already known, or if there is any similar relevant work out there (I am a logician, combinatorics is not my area of expertise).

Matisse identified the following non-degeneracy axiom, generalizing the non-degeneracy axiom for projective planes:

There exist $mn$ points, no $(m+1)$ of which are incident to a single line, and there exist $mn$ lines, no $(n+1)$ of which are incident to a single point.

She then proved the following theorems:

  1. In any non-degenerate $(m,n)$-pseudoplane, there are constants (possibly infinite cardinals) $P_a$ and $L_b$ for $0\leq a \leq n$ and $0\leq b \leq m$ such that for any set of $a$ lines, there are exactly $P_a$ points incident to these lines, and for any set of $b$ points, there are exactly $L_b$ lines incident to these points. (Recall that in projective planes, we have $P_0 = L_0 = k^2+k+1$, $P_1 = L_1 = k+1$, and $P_2 = L_2 = 1$, where $k$ is the order of the plane.)

  2. There are no finite non-degenerate $(m,n)$-pseudoplanes when $m\geq 3$ or $n\geq 3$. The proof involves deriving conflicting identities involving the constants $P_a$ and $L_b$.

  3. Nevertheless, there are infinite non-degenerate $(m,n)$-pseudoplanes. In any such structure, there is a single infinite cardinal $\kappa$ such that $P_a = L_b = \kappa$ for all $0\leq a < n$ and $0\leq b < m$.

  4. As a consequence of 2, the theory of existentially closed $(m,n)$-pseudoplanes has no prime model when $m\geq 3$ or $n\geq 3$. This question is still open for projective planes (when $m = n = 2$); Gabe and I showed that it is equivalent to a longstanding open problem: does every finite $K_{2,2}$-free configuration embed in a finite projective plane? Of course, 2 shows that this question trivializes when $m\geq 3$ or $n\geq 3$, since the non-degeneracy configuration does not embed in any finite $(m,n)$-pseudoplane.

It remains open to classify the (finite) degenerate $(m,n)$-pseudoplanes when $m\geq 3$ or $n\geq 3$ (it may be that there is no satisfying classification).

  • $\begingroup$ More an idea than a reference. This looks to me like a set covering or lottery system (how many tickets to guarantee one of them has two of the five numbers). Relax a condition, find the common structure, then see if someone has specialized it to your case. Gerhard "Good Luck In Your Search" Paseman, 2018.06.13. $\endgroup$ – Gerhard Paseman Jun 13 '18 at 19:57
  • $\begingroup$ I'm sure that you mean: For every n distinct lines, there are exactly (m−1) distinct points which are incident to all of them. Do you know non-trivial examples? I can see that the triples from a $4$ point set are a $(3,2)$ but that seems like the only one. $\endgroup$ – Aaron Meyerowitz Jun 14 '18 at 8:21
  • 1
    $\begingroup$ @AaronMeyerowitz Yes, thanks. Note that I'm not assuming finiteness - it's easy to build infinite examples by starting with a $K_{m,n}$-free configuration and adjoining points and lines "freely" to satisfy the axioms. $\endgroup$ – Alex Kruckman Jun 14 '18 at 11:49
  • $\begingroup$ I guess you know about symmetric balanced incomplete block designs? They are not defined via your two properties but I think they satisfy them... People usually study them for your parameter $m$ being equal to $2$, although I don't see why this is necessary. I don't have time now to think this through properly so will leave this as a comment... $\endgroup$ – Nick Gill Oct 4 '18 at 13:56

Your Answer

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

Browse other questions tagged or ask your own question.