Skip to main content
2 of 8
edited tags; edited title
Anurag
  • 1.2k
  • 1
  • 20
  • 29

A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear space is a subset of points such that every line intersects in one or all points. This coincides with the notion of hyperplanes in projective spaces. Some other examples of partial linear spaces: Generalized Quadrangles, Near Polygons, Generalized Polygons.

We need to find an efficient way to compute hyperplanes of a given finite partial linear space that has a constant number of points per line.

This can also be formulated in terms of finding certain kind of subsets of the vertex set in a $r$-uniform hypergraph. For $r = 2$ every vertex cover is a hyperplane (not sure if there is an efficient way to compute all vertex covers) and for $r=3$ the following trick works pretty well:

Since each line has three points incident with it, a subset of points/vertices is a hyperplane if and only if it intersects every line/edge in $1$ or $3$ points. This is the same as saying that the characteristic vector of its complement belongs to the null space of the incidence matrix over $\mathbb{F}_2$. Therefore we have a pretty efficient way of finding all hyperplanes. Assuming that we know the full automorphism group of our partial linear space we can also compute the number of distinct hyperplanes upto isomorphism.

For general $r$-uniform hypergraphs a hyperplane intersects every edge in exactly $1$ or $r$ points. Is there an efficient way of computing hyperplanes for $r = 4$ or for higher values of $r$?

Anurag
  • 1.2k
  • 1
  • 20
  • 29