On the maximum number of independent elements in configurations of points and lines
type: Item
instance of: scholarly article
title: On the maximum number of independent elements in configurations of points and lines
zbMATH Open document ID: 1310.51002
author: Tomaž Pisanski
author: Thomas W. Tucker
published in: Discrete \& Computational Geometry
publication date: 2014-10-29T00:00:00Z
review text: 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)\) configuratio…
reviewed by: Daniele Bartoli
Mathematics Subject Classification ID: 51A20
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 6362296
zbMATH Keywords: configuration of points and lines
zbMATH Keywords: unsplittable configuration
zbMATH Keywords: unsplittable graph
zbMATH Keywords: independent set
zbMATH Keywords: Levi graph
zbMATH Keywords: Grünbaum graph
MaRDI profile type: Publication
full work available at URL: s00454-014-9618-1
OpenAlex ID: W1994042983
cites work: Uniqueness of graph square roots of girth six
cites work: Self-dual configurations and regular graphs
cites work: Q3757929
cites work: Q3630397
cites work: Configurations from a Graphical Viewpoint
DOI: 10.1007/S00454-014-9618-1
description: scientific article; zbMATH DE number 6362296