Coloring intersection points of line segments Sam Lowery Department of Mathematics & Statistics 2022 Symposium for Student Research, Scholarship, and Creative Activity Graphs Graphs vertices edges Complete graphs 𝐾! 𝐾" 𝐾# 𝐾$ 𝐾% Coloring a graph Coloring a graph means coloring its vertices so that adjacent vertices get different colors Coloring a graph πœ’(𝐺): smallest possible number of colors with which a graph 𝐺 can be colored Coloring a graph πœ’(𝐺): smallest possible number of colors with which a graph 𝐺 can be colored πœ’ 𝐺 =3 Coloring a graph πœ’(𝐾& ) = 𝑛 Set of line segments Set of line segments 𝑀 Intersection points 𝑃(𝑀) Intersection points 𝑀(𝑀): most intersection points in a segment Intersection points 𝑀(𝑀) = 5 Corresponding graph 𝐺' Coloring a set of segments Coloring a set of segments means coloring the intersection points so that no segment has ffffffff points with the same color. Coloring a set of segments πœ’(𝑀): smallest possible number of colors with which a set of segments 𝑀 can be colored Coloring a set of segments πœ’(𝑀): smallest possible number of colors with which a set of segments 𝑀 can be colored πœ’ 𝑀 =5 ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. πœ’(𝐺) cannot be less than 𝑛, since at least 𝑛 colors are needed for each copy of 𝐾& ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& , every pair of which has at most one vertex in common. Then, πœ’(𝐺) = 𝑛. [Kang et al. 2021] announced a proof for large enough 𝑛 ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝑀 be a set of π‘š curves, each pair of which has at most one point in common. Then, πœ’ 𝑀 ≀ π‘š. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝑀 be a set of π‘š curves, each pair of which has at most one point in common. Then, πœ’ 𝑀 ≀ π‘š. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝑀 be a set of π‘š curves, each pair of which has at most one point in common. Then, πœ’ 𝑀 ≀ π‘š. ErdΕ‘s-Faber-LovΓ‘sz Conjecture Let 𝑀 be a set of π‘š curves, each pair of which has at most one point in common. Then, πœ’ 𝑀 ≀ π‘š. πœ’(𝑀) can be less than π‘š. Coloring a set of segments Let 𝑀 be a set of π‘š segments. What’s πœ’(𝑀)? Bounds 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| Bounds Need 𝑀(𝑀) colors for the segment with 𝑀(𝑀) intersections Follows from proof of EFL Conjecture 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| Bounds Need 𝑀(𝑀) colors for the segment with 𝑀(𝑀) intersections Follows from proof of EFL Conjecture 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| easy to compute Complexity of πœ’(𝑀) Computing πœ’(𝑀) is NP-Complete, even if 𝑀 is a set of segments where no five segments intersect in the same point. Reduction using a special case of PLANAR GRAPH COLORING Bounds Need 𝑀(𝑀) colors for the segment with 𝑀(𝑀) intersections Follows from proof of EFL Conjecture 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| easy to compute Bounds Need 𝑀(𝑀) colors for the segment with 𝑀(𝑀) intersections Follows from proof of EFL Conjecture 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| hard to compute easy to compute Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 1? Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 1? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 2? Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 1? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 2? β€’ Can πœ’ 𝑀 β‰₯ 𝑀 𝑀 + 3? Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 1? Characterizations are hard to derive β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 2? β€’ Can πœ’ 𝑀 β‰₯ 𝑀 𝑀 + 3? Hard to find one Questions Experimentally, πœ’ 𝑀 usually seems to be a lot closer to 𝑀 𝑀 than to |𝑀|. β€’ When is πœ’ 𝑀 = 𝑀 𝑀 ? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 1? β€’ When is πœ’ 𝑀 = 𝑀 𝑀 + 2? β€’ Can πœ’ 𝑀 β‰₯ 𝑀 𝑀 + 3? What is πœ’ 𝑀 for 𝑀 with special structure? Easier to answer Some characterizations Odd # of sides β€œcircuit-free β€œgrid-like arrangements” arrangements” β€œbisected polygon arrangements” πœ’ 𝑀 = 𝑀(𝑀) πœ’ 𝑀 = 𝑀(𝑀) πœ’ 𝑀 = 𝑀 𝑀 + 2 Some characterizations β€œstandard drawing of 𝐾&,& ” πœ’ 𝑀 = π‘₯, 𝑦 : 1 ≀ π‘₯, 𝑦 ≀ 𝑛, gcd π‘₯, 𝑦 = 1 + 2 Approach for ____ family Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula for arbitrary 𝑛 – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula for arbitrary 𝑛 – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Approach for ____ family β€’ Wrote program to generate instance of size 𝑛 β€’ Computed optimal coloring for 𝑛 = 2,3, … , 10 β€’ Looked up sequence of chromatic numbers in Online Encyclopedia on Integer Sequences β€’ Noticed it almost matches one sequence β€’ Modified formula for that sequence to match exactly β€’ Analytically proved formula for arbitrary 𝑛 – Proof is based on showing that sets of intersections are grouped at different y-coordinates, and points in these levels get the same color, which is necessary and sufficient Longest diagonal segments intersect all others, so 𝑀(𝑀) colors are necessary, and also sufficient Some characterizations If 𝑀 is a segment cactus different from then πœ’ 𝑀 ≀ |𝑀| βˆ’ 1. , What about lines? In a set 𝑀 of lines, every pair of non-parallel lines intersect 𝑀 𝑀 ≀ πœ’ 𝑀 ≀ |𝑀| still holds What about lines? The following are equivalent: β€’ If 𝑀 is a set of π‘š lines drawn in the plane, then 𝑀 has a coloring with π‘š colors. β€’ If 𝑀 is a set of π‘š segments drawn in the plane, then 𝑀 has a coloring with π‘š colors. What about lines? The following are equivalent: β€’ If 𝑀 is a set of π‘š lines drawn in the plane, then 𝑀 has a coloring with π‘š colors. β€’ If 𝑀 is a set of π‘š segments drawn in the plane, then 𝑀 has a coloring with π‘š colors. An analogous statement does not necessarily hold for subfamilies of segments/lines Approach for ____ family Approach for ____ family β€’ Randomly noticed one small example πœ’ 𝑀 =𝑀 𝑀 +2 Approach for ____ family β€’ Randomly noticed one small example πœ’ 𝑀 =𝑀 𝑀 +2 β€’ Noticed another that was similar to it πœ’ 𝑀 =𝑀 𝑀 +2 Approach for ____ family β€’ Randomly noticed one small example πœ’ 𝑀 =𝑀 𝑀 +2 β€’ Noticed another that was similar to it πœ’ 𝑀 =𝑀 𝑀 +2 β€’ Tried to extend the pattern β€’ Harder to verify large examples by hand Approach for ____ family β€’ β€’ β€’ β€’ Wrote integer program to help verification Used program to check more examples Saw πœ’ 𝑀 = 𝑀 𝑀 + 2 holds for all of them Analytically proved formula – Proof is based on converting the set of segments to a graph, finding a coloring that always works, and showing that no smaller coloring exists Future work β€’ Find a set with πœ’ 𝑀 β‰₯ 𝑀 𝑀 + 3 or show this can’t exist. β€’ Run more extensive computational experiments Future work β€’ Find a set with πœ’ 𝑀 β‰₯ 𝑀 𝑀 + 3 or show this can’t exist. β€’ Run more extensive computational experiments Thank you