A partial linear space (or a linear hypergraph) 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 $H$ of points such that for every line $l$ we have $|l \cap H| = 1$ or $l \subseteq H$. 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$ hyperplanes are the same as 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$?
Edit1: In generalized quadrangles of order (s,t) the hyperplanes are completely classified. They are one of the following: perp of a point, a full subquadrangle or an ovoid. I am not aware of any such classification for generalized hexagons.
Edit2: For $r = 2$ this problem is NP-Hard so it seems like it would be fruitless to try this in full generality.
