On the maximum number of independent elements in configurations of points and lines (Q464738)

A configuration \(\mathcal{C}\) of type \((v_r)\) is an incidence structure with sets \(\mathcal{P}\) and \(\mathcal{L}\) of objects called \textit{points} and \textit{lines} respectively, satisfying {\parindent=6mm \begin{itemize}\item[1.] \(\mathcal{P}\cap \mathcal{L}=\emptyset\); \item[2.] \(|\mathcal{P}|= |\mathcal{L}|=v\); \item[3.] each line is incident with \(r\) points; \item[4.] each point is incident with \(r\) lines; \item[5.] two distinct points are incident with at most one common line. \end{itemize}} Two elements of \(\mathcal{P}\cup \mathcal{L}\) are said to be \textit{independent} in the following cases: {\parindent=6mm \begin{itemize}\item[--] if they are two points and they do not belong to a common line; \item[--] if they are two lines and they do not intersect in a point; \item[--] if they are a point and a line and the point does not lie on the line. \end{itemize}} Given a configuration \(\mathcal{C}\) of type \((v_r)\), its \textit{Levi graph} \(L(\mathcal{C})\) is an \(r\)-regular bipartite graph with \(V(L(\mathcal{C}))=\mathcal{P}\cup\mathcal{L}\) and edges \(\{(P,\ell) \mid P \in \mathcal{P}, \ell \in \mathcal{L}, P \in \ell\}\). Given a graph \(G\), the graph \(G^2\) is a graph with vertex set \(V(G)\) and an edge between \(u\) and \(w\) if their distance in \(G\) is \(d(u,w) \leq 2\). In the case in which \(G=L(\mathcal{C})\), with \(\mathcal{C}\) a configuration, the edges of the graph \(L^2\) correspond to incidences of point on line, two points on the same line, and two lines through the same point. The main result of this paper is the following. Theorem. Let \(G\) be a regular graph on \(n\) vertices of valence \(r\). The size of the largest independent set of \(G^2\) is at most \(\left\lfloor \frac{n}{r+1}\right\rfloor\). As a consequence, the size of an independent set of elements of a \((v_r)\) configuration is at most \(\left\lfloor \frac{2v}{r+1}\right\rfloor\). Also, the authors construct for any \(r>1\) a \((v_r)\) configuration, with \(r+1 \mid v\), having an independent set achieving the bound. This disproves a previous conjecture due to Grünbaum.