Why is the finite-projective-plane minus a single edge r-partite?

105 Views Asked by At

Let $P_r$ be the finite projective plane in which each line contains $r$ points (when it exists). For example, $P_2$ is a triangle, $P_3$ is the Fano plane, and $P_r$ exists whenever $r-1$ is the power of a prime number.

Let $P_r'$ be $P_r$ with one line removed. Füredi (1981) claims that $P_r'$ is an $r$-partite hypergraph (page 158, below Corollary 5).

I do not understand why this is true: the projective plane is certainly not constructed as an $r$-partite hypergraph. Why does it become $r$-partite when we omit a single line from it?

For example, consider the Fano plane, which has 7 hyperedges {123, 145, 167, 246, 257, 347, 356}. Suppose we delete the last hyperedge 356. How is the remaining hypergraph 3-partite? What are the parts?

For your convenience, here are the relevant paragraphs from the paper.

Definition of $P_r$:

enter image description here

Definition of $P_r'$:

enter image description here

Claim that it is $r$-partite:

enter image description here

EDIT: After reading the answer by Saul Spatz, I now think there is a typo in the paper: $P'_r$ is constructed from $P_r$ by deleting one point plus all lines that contain it. So for example, if in the Fano plane we delete point 7, we get a hypergraph with 6 vertices and 4 edges: {1,2,3}, {1,5,4}, {6,2,4}, {6,5,3}. It is tripartite with partition {1,6}, {2,5}, {3,4}.

This also explains why he says that $\tau^*(P'_r)=r-1$: after removing one point, there are $r^2-r$ remaining points. Assigning a weight of $1/r$ to every point yields a fractinal cover of size $r-1$.

EDIT 2: I now see that this construct has a name in the literature - it is called the Truncated projective plane.

1

There are 1 best solutions below

11
On BEST ANSWER

In a projective plane, just as each line has $r$ points, each point lies on $r$ lines. So, if we consider each point $P$ on the deleted line, there are $r-1$ lines remaining which used to meet in $P$ but no longer intersect. These $r-1$ lines form a pencil of parallel lines. There are $r$ such pencils.

The author's terminology seems idiosyncratic. It is usual to say that a projective plane of order $r$ has $r+1$ points on a line. For example, the famous result that there is no projective plane of order $10$ is referring to a plane with $11$ points on a line.

EDIT

In response to the OP's comment. If edge $356$ is deleted the six remaining edges become $$ 12, 14, 17, 24, 27, 47$$ and the parts are $$ \{12,47\}\\ \{14,27\}\\ \{17,24\}$$

EDIT

I believe I understand where the confusion lies. The author states that $P_r$ is the hypergraph consisting of the lines of the projective plane. I take this to mean that the lines are the vertices of the hypergraph, and you take it to mean that the lines are the edges. Without seeing more of the text, I can't be sure of the author's usage, but I believe my interpretation to be in line with common parlance. Also, I can't see how to make sense of his further statements if the line are the edges.