Truncated projective plane


A truncated projective plane is a special kind of a hypergraph that is constructed in the following way.
Consider the Fano plane, which is the projective plane of order 2. It has 7 vertices and 7 edges.
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 and 4 edges.

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 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, and. 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:
.
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:
.
Therefore, the TPP is an extremal hypergraph for Ryser's conjecture.
The minimum fractional vertex-cover size of the TPP is r-1 too:
.