The maximum chromatic number of the disjointness graph of segments on \(n\)-point sets in the plane with \(n\leq 16\) (Q6614724)

This article investigates the chromatic number of disjointness graphs formed by line segments connecting points in general positions in the plane. The article, spanning 37 pages, defines one definition, poses two questions, proves one theorem, eight propositions, three corollaries, ten lemmas, and ten claims, and makes two remarks. It is divided into five sections.\N\NLet \(P\) be a finite set of points in general position in the plane. The disjointness graph of the segments \(D(P)\) of \(P\) is the graph whose vertices are all closed straight-line segments with endpoints in \(P\), two of which are adjacent in \(D(P)\) if and only if they are disjoint. Let \(\chi (D(P))\) denote the chromatic number of \(D(P)\), and \(d(n)\), \(n \ge 2\) and \(n \in \mathbb{Z^+} \), denote the maximum \(\chi (D(P))\) taken over all sets \(P\) of \(n\) points in the general position of the plane. This paper proves its main theorem, stated as Theorem 2, as \(d(n) = n-2\) if and only if \(n \in \{3, 4,\dots,16\}\). An example of its computational complexity is as follows: \(D(X)\) has a subset \(S\) with at least 100 vertices such that if \(v\in S\), then \(D(X)\setminus \{v\}\) can be colored with only 13 colors.\N\NSection 1. Introduction, discusses the basic definitions, the disjointness graph and its relation to the Kneser graph, a literature review of the concepts, a background discussion on the question of the value of \(d(n)\) for each \(n \in \mathbb{Z^+}\) and states it as the central theme of the paper, denoted as Theorem 2 above. To prove \(d(n) = n-2\) \(n \in \{3, 4,\dots,16\}\), the paper uses an \(n\)-point set \(P\) in general position in the plane such that \(\chi (D(P)) =n-2\).\N\NSection 2. The 16-point set \(X\), defines the set \(X\) via its coordinates and describes its geometric properties. The set \(X\) is partitioned into the subsets \( A= \{a_1,a_2, \dots, a_5\}\), \(B =\{b_1, b_2, \dots, b_5\}\), \(T_1 = \{t_1^1, t_1^2, t_1^3\}\) and \(T_2 = \{t_2^1, t_2^2, t_2^3\}\). Since the diagram of the given 16-point set \(X\) is an essential part of the article, an approximate alt-text for the figure is as follows: The diagram shows two sets of points: \(A= a_1\) to \(a_5\), represented at the top of the diagram and \(B=b_1\) to \(b_5\), represented at the bottom of the diagram. These points are labeled with their coordinates: \(a_1=(-54,93)\), \(a_2=(-48,90)\), \(a_3=(-40,88)\), \(a_4=(48,89)\), \(a_5=(54,92)\), \(b_1=(-81,-80)\), \(b_2=(-74,-76)\), \(b_3=(-68,-75)\), \(b_4=(74,-77)\), \(b_5=(81,-81)\). The points \(a_1\) to \(a_5\) are connected by a polyline (lines joining the points). Similarly, the points \(b_1\) to \(b_5\) are connected by another polyline. These polygons form an hourglass shape. Lines connect corresponding points between the two sets (\(a_1\) to \(b_4\) and \(a_5\) to \(b_3\)) forming a crisscross pattern. Near the middle of the figure, there is a dashed ellipse, which encloses the subsets: \(T_1\) and \(T_2\). Points of \(T_1\) are connected by a polyline, and points of \(T_2\) are similarly connected. Lines connect corresponding points between \(T_1\) and \(T_2\) forming a shape with symmetry across a vertical axis.\N\NSection 3. Preliminaries, introduces useful notational conventions, terminology, and concepts and proves a few basic facts that are utilised in most of the proofs.\N\NSection 4. Technical claims behind the proof of Theorem 2, presents the crucial technical work of the paper, wherein the main claims supporting the proof of the theorem are established. Most of these proofs involve case analysis, focusing on the cardinality of the optimal coloring of subsets of \(X\). The symmetry of the set \(X\) and the numerous separable subsets it contains play a central role. This section, where all lemmas and claims are proved is the largest in the paper. It meticulously examines each possible case and its subcases in detail.\N\NSection 5. Proof of Theorem 2, concludes by formally establishing the theorem of the paper through a combination of results from the previous sections. The core of the proof demonstrates that any subset \(X^{\prime}\) of the given 16-point set \(X\) satisfies the inequality \(\chi(D(X^{\prime})) \ge |X^{\prime}|-2\) for each \(|X^{\prime}|\ge 3\).\N\NNotable propositions include:\N\N\begin{itemize}\N\item \(\chi (D(P)) \le |P|-2\). (This proposition establishes the upper bounds.)\N\item Let \(\Psi\) be the set of \(\binom{16}{2}\) closed straight line segments with endpoints in the set \(X\) defined above and \(S \subset X\). For \(x_1x_2 \in \Psi\setminus S\), there are many different colorings of \(D(X)\) with \(14\) colors in which the color of \(x_1x_2\) is not assigned to any other segment of \(\Psi\). (This proposition illustrates the tightness of the theorem of the paper.)\N\item Let \(P^{\prime} \subset P\), and let \(\gamma\) be an optimal coloring of \(D(P)\). Then, the following holds: (i) If \(|P^{\prime}|\ge 3\) and \(\chi (D(P)) =|P|-2\), then \(\chi (D(P^{\prime})) =|P^{\prime}|-2\). (ii) If \(P^{\prime}\) is separable with respect to \(\gamma\) and \(\gamma(P^{\prime})=|P^{\prime}|\), then \(\chi (D(P)) \ge \chi (D(P \setminus P^{\prime})) +|P^{\prime}|\). (iii) If \(S_1, \dots, S_r\) are different stars of \(\gamma\) with apices \(v_1, \dots, v_r\), respectively, then \(\chi (D(P \setminus \{v_1,\dots, v_r\})) = \chi (D(P))-r\), where an apex is a point of \(P\) that is incident with all the segments of the chromatic class \(c\).\N\item Let \(\gamma\) be a 4-coloring of \(D(C_5)\), where \(C_5\) denotes a set of 5 points in (general and) convex position in the plane. Let \(\gamma^\ast (C5)\) denote the number of points in \(C_5\) that are apices of some star of \(C_5\) with respect to \({\gamma}\big|_{C_5} \). If \(\gamma^\ast (C_5) = 5\), then \(C_5\) has two points \(p\) and \(q\) such that \(\{pq\}\) is a 2-star of \(\gamma\) and neither \(p\) nor \(q\) is an apex of any other star of \(\gamma\).\N\item If \(\gamma\) is a 3-coloring of \(D(C_5)\), then \(\gamma^\ast (C_5) \le 2\).\N\item \( \chi (D(A \cup T_2)) = 6\) and \( \chi (D(B \cup T_1)) = 6\).\N\item Let \(\Delta\) be a triangle with corners in \(A \cup B\), let \(l\) be a side of \(\Delta\) such that \(l\in A\ast B\), and let \(Q = T_1\cup \Delta \cup T_2\). If \(\gamma\) is an optimal coloring of \(D(Q)\) and \(\Delta\) contains \(T_1 \cup T_2\) in its interior, then \(l\) belongs to a star of \(\gamma (Q)\) or \(|\gamma (Q)| \ge |Q|-2\).\N\end{itemize}\N\NKey lemmas and claims include:\N\begin{itemize}\N\item If \(Q \subset T_1 \cup I \cup T_2\) with \(I \in \{A, B\}\) and \(|Q| \ge 3\), then \( \chi(D(Q)) =|Q|-2\).\N\item Let \(A^{\prime} \subset A\), \(B^{\prime} \subset B\) and \(T^{\prime} \subset (T_1 \cup T_2)\) be such that \(|A^{\prime}|=|B^{\prime}|=|T^{\prime}|=3\). If \(Q\) is a subset of \(A^{\prime} \cup T^{\prime} \cup B^{\prime}\) with \(|Q|\ge 3\), then \( \chi(D(Q)) =|Q|-2\).\N\item Let \(a_i,a_j \in A\), \(b_p,b_q \in B\) and \(Q = T_1 \cup \{a_i, a_j, b_p, b_q\} \cup T_2\). If \(\gamma\) is an optimal coloring of \(D(Q)\), then \(|\gamma (D(Q))|\ge 8\).\N\item Let \(\Delta_0\) be a triangle with vertices in \(A \cup B\), and let \(Q \subseteq T_1\cup \Delta_0 \cup T_2\) with \(|Q|\ge 3\). If \(\gamma\) is an optimal coloring of \(D(Q)\), then \(|\gamma (Q)| \ge |Q|-2\).\N\item Let \(\Delta_U\) be a triangle with corners in \(U \in\{A, B\}\), \(v_p,v_q \in (A \cup B)\setminus U\) and \(Q = T_1 \cup \Delta_U \cup \{v_p, v_q\}\cup T_2\). If \(\gamma\) is an optimal coloring of \(D(Q)\), then \(|\gamma (D(Q))|\ge 9\).\N\end{itemize}\N\NThrough explicit case-by-case analysis, the authors determine the exact values of \(d(n)\) for \(n \le 16\), providing insights into how the chromatic number evolves as the number of points increases. By employing computational and combinatorial approaches, including exhaustive enumeration and geometric constraints, the study systematically explores small point sets, providing foundational results for future research. This work contributes to combinatorial geometry and graph theory by validating results through incremental coloring arguments for representative subsets and deepening understanding of segment arrangements and their colorings.