On the maximum number of independent elements in configurations of points and lines
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.
- Arranging \(n\) distinct numbers on a line or a circle to reach extreme total variations
- New bounds on the existence of \((n_5)\) and \((n_6)\) configurations: the Grünbaum calculus revisited
- On some points-and-lines problems and configurations
- On the Levi graph of point-line configurations
- Polytopes, configurations and symmetries -- Bled 2019. In memory of Branko Grünbaum (1929--2018)
- Splittable and unsplittable graphs and configurations
- Maximale (m,n)-Punktkonfigurationen. (Maximal (m,n)-configurations)
This page was built for publication: On the maximum number of independent elements in configurations of points and lines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464738)
