Truncated projective plane

A truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.[1][2]

• Take a finite projective plane.
• Remove one of the points (vertices) in the plane.
• Remove all lines (edges) containing that point.

These objects have been studied in many different settings, often independent of one another, and so, many terminologies have been developed. Also, different areas tend to ask different types of questions about these objects and are interested in different aspects of the same objects.

Example

Consider the Fano plane, which is the projective plane of order 2. It has 7 vertices {1,2,3,4,5,6,7} and 7 edges {123, 145, 167, 246, 257, 347, 356}.

It can be truncated e.g. by removing the vertex 7 and the edges containing it. The remaining hypergraph is the TPP of order 2. It has 6 vertices {1,2,3,4,5,6} and 4 edges {123, 154, 624, 653}.

Combinatorics of dual affine planes

A finite projective plane of order n has n + 1 points on every line (n + 1 = r in the hypergraph description). There are n² + n + 1 total points and an equal number of lines. Each point is on n + 1 lines. Every two distinct points lie on a unique line and every two distinct lines meet at a unique point.

By removing a point and all the lines that pass through that point, the configuration that is left has n² + n points, n² lines, each point is on n lines and each line contains n + 1 points. Each pair of distinct lines still meet at a unique point, but two distinct points are on at most one line. This dual affine plane is thus a configuration of type ((n² + n)_n (n²)_{n + 1}).

The points can be partitioned into n + 1 sets of n points apiece, where no two points in the same partition set are joined by a line. These sets are the analogs of classes of parallel lines in an affine plane, and some authors refer to the points in a partition piece as parallel points in keeping with the dual nature of the structure.[3]

Projective planes constructed from finite fields (Desarguesian planes) have automorphism groups that act transitively on the points of the plane, so for these planes the point removed to form the dual affine plane is immaterial, the results of choosing different points are isomorphic. However, there do exist non-Desarguesian planes and the choice of point to remove in them may result in non-isomorphic dual affine planes having the same parameters.

An affine plane is obtained by removing a line and all the points on that line from a projective plane. Since a projective plane is a self-dual configuration, the dual configuration of an affine plane is obtained from a projective plane by removing a point and all the lines through that point. Hence the name of this configuration.

Hypergraph properties

It is known that the projective plane of order r-1 exists whenever r-1 is a prime power; hence the same is true for the TPP.

The finite projective plane of order r-1 contains r²-r+1 vertices and r²-r+1 edges; hence the TPP of order r-1 contains r²-r vertices and r²-2r+1 edges.

The TPP of order r-1 is an r-partite hypergraph: its vertices can be partitioned into r parts such that each hyperedge contains exactly one vertex of each part. For example, in the TPP of order 2, the 3 parts are {1,6}, {2,5} and {3,4}. In general, each of the r parts contains r-1 vertices.

Each edge in a TPP intersects every other edge. Therefore, its maximum matching size is 1:

${\displaystyle \nu (H)=1}$.

On the other hand, covering all edges of the TPP requires all r-1 vertices of one of the parts. Therefore, its minimum vertex-cover size is r-1:

${\displaystyle \tau (H)=r-1}$.

Therefore, the TPP is an extremal hypergraph for Ryser's conjecture.[4][1][5]

The minimum fractional vertex-cover size of the TPP is r-1 too: assigning a weight of 1/r to each vertex (which is a vertex-cover since each hyperedge contains r vertices) yields a fractional cover of size (r²-r)/r=r-1.

Its maximum fractional matching size of the is r-1 too: assigning a weight of 1/(r-1) to each hyperedge (which is a matching since each vertex is contained in r-1 edges) yields a fractional matching of size (r²-2r+1)/(r-1)=r-1. Therefore:[6]

${\displaystyle \tau ^{*}(H)=\nu ^{*}(H)=r-1}$.

Note that the above fractional matching is perfect, since its size equals the number of vertices in each part of the r-partite hypergraph. However, there is no perfect matching, and moreover, the maximum matching size is only 1. This is in contrast to the situation in bipartite graphs, in which a perfect fractional matching implies the existence of a perfect matching.

Design-theoretic aspects

Dual affine planes can be viewed as a point residue of a projective plane,[7] a 1-design,[8] and, more classically, as a tactical configuration.[9]

Since they are not pairwise balanced designs (PBDs), they have not been studied extensively from the design-theoretic viewpoint. However, tactical configurations are central topics in geometry, especially finite geometry.

History

According to Dembowski (1968, p. 5), the term "tactical configuration" appears to be due to E. H. Moore in 1896.[10] For the history of dual configurations, see Duality (projective geometry)#History.

Notes

1. Aharoni, Ron (2001-01-01). "Ryser's Conjecture for Tripartite 3-Graphs". Combinatorica. 21 (1): 1–4. doi:10.1007/s004930170001. ISSN 0209-9683.
2. Füredi, Zoltán (1989-05-01). "Covering the complete graph by partitions". Discrete Mathematics. 75 (1): 217–226. doi:10.1016/0012-365X(89)90088-5. ISSN 0012-365X.
3. Dembowski 1968, p. 306
4. Tuza (1983). "Ryser's conjecture on transversals of r-partite hypergraphs". Ars Combinatorica.
5. Abu-Khazneh, Ahmad; Barát, János; Pokrovskiy, Alexey; Szabó, Tibor (2018-07-12). "A family of extremal hypergraphs for Ryser's conjecture". arXiv:1605.06361 [math].
6. Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912.
7. Beth, Jungnickel & Lenz 1986, p. 79
8. Beth, Jungnickel & Lenz 1986, p. 30
9. Dembowski 1968, p. 4
10. Moore, E.H. (1896), "Tactical memoranda", American Journal of Mathematics, 18: 264–303

References

• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge: Cambridge University Press, ISBN 3-411-01675-2
• Dembowski, Peter (1968), Finite geometries, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlin, New York: Springer-Verlag, ISBN 3-540-61786-8, MR 0233275