* Schrieber (2000) T. Schreiber, “Measuring information transfer”, Phys. Rev. Let., Vol. 85, No. 2, pp.461-464, 2000
  * Sabesan et al. (2007) S. Sabesan, K. Narayanan, A. Prasad, L. Iasemidis, A. Spanias and K. Tsakalis, “Information Flow in Coupled Nonlinear Systems: Application to the Epileptic Human Brain”, Data Mining in Biomedicine, Data Mining in Biomedicine, 2007
  * Darbellay & Vajda (1999) G. Darbellay and I. Vajda, “Estimation of the Information by an adaptive partitioning of the observation space”, IEEE Trans. On Information Theory, Vol. 45, No.4, 1999

Reconstructing the Galactic halo’s accretion history: A finite mixture model
approach

Duane Lee
Department of Astronomy
Columbia University
New York, New York, USA

Will Jessop
Department of Statistics
Columbia University
New York, New York, USA

## Abstract

The stellar halo that surrounds our Milky Way Galaxy is thought to have been
built, at least in part, from the agglomeration of stars from many smaller
galaxies. This talk outlines an approach to reconstructing the history of
Galactic accretion events by looking at the distribution of the chemical
abundances of halo stars. The full distribution is assumed to result from the
superpositionof stellar populations accreted at different times from
progenitor galaxies of different sizes. Our approach uses the Expectation-
Maximization (EM) algorithm to find the maximum-likelihood estimators that
assess the contribution of each of these progenitors in forming the Galaxy.

Scientific Program

|  Thursday, February 24, 2011 |
---|---|---
10:00 |  Welcome | Michael Way (GISS)
|  | Catherine Naud (GISS)
10:20 |  How long will it take. A historical approach to boundary crossing. | Victor de la Peña (Columbia)
10:45 |  Cosmology through the Large-Scale Structure of the Universe | Eyal Kazin (NYU)
11:30 |  On the shoulders of Gauss, Bessel, and Poisson: links, chunks, spheres, and conditional models | William Heavlin (Google)
12:15 |  Mining Citizen Science Data: Machine Learning Challenges | Kirk Borne (GMU)
13:00 |  Lunch Break |
14:30 |  Tracking Climate Models: Advances in Climate Informatics | Claire Monteleoni (Columbia)
15:15 |  Spectral Analysis Methods for Complex Source Mixtures | Kevin Knuth (SUNY/Albany)
16:00 |  Beyond Objects: Using machines to understand the diffuse universe | Joshua Peek (Columbia)
16:45 |  Viewpoints: A high-performance visualization and analysis tool | Michael Way (GISS)
|  Friday, February 25, 2011 |
10:00 |  Clustering Approach for Partitioning Directional Data in Earth and Space Sciences | Christian Klose (Think Geohazards)
10:45 |  Planetary Detection: The Kepler Mission | Jon Jenkins (NASA/Ames)
11:30 |  Understanding the possible influence of the solar activity on the terrestrial climate: A times series analysis approach | Elizabeth Martínez-Gómez (Penn State)
12:15 |  Bayesian adaptive exploration applied to optimal scheduling of exoplanet Radial Velocity observations | Tom Loredo (Cornell)
13:00 |  Lunch Break |
14:30 |  Bayesian Inference from Photometric Surveys | Tamás Budavári (JHU)
15:15 |  Long-Range Forecasts Using Data Clustering and Information Theory | Dimitris Giannakis (NYU)
16:00 |  Comparison of Information-Theoretic Methods to estimate the information flow in a dynamical system | Deniz Gencaga (CCNY)
16:45 |  Reconstructing the Galactic halo’s accretion history: A finite mixture model approach | Duane Lee and Will Jessop (Columbia)

Participants

Ryan Abrahams |  CUNY Graduate Center |
---|---|---
Hannah Aizenman |  CCNY/Computer Science |
Arif Albayrak |  NASA GES DISC |
Kehinde-Paul Alabi |  CCNY/Computer Science |
Vivienne Baldassare |  CUNY/Hunter College/Physics |
Imre Bartos |  Columbia/Physics |
Mike Bauer |  Columbia-NASA/GISS |
Rohit Bhardwaj |  Columbia/Computer Science |
Amitai Bin-Nun |  University of Pennsylvania/Astronomy |
James Booth |  NASA/GISS |
Kirk Borne |  George Mason University |  speaker
Andreas Breiler |  IdeLaboratoriet |
Douglas Brenner |  American Museum of Natural History |
Tamas Budavari |  Johns Hopkins University |  speaker
Samantha Chan |  Lamont-Doherty Earth Observatory, Columbia University |
Milena C. Cuellar |  BCC. CUNY |
Victor de al Pena |  Columbia/Statistics |  speaker
Danielle Dowling |  CUNY Graduate Center |
Tarek El-Gaaly |  Rutgers/Computer Science |
Daniel Feldman |  CUNY/College of Staten Island |
Stephanie Fiorenza |  CUNY/College of Staten Island/Physics |
Carl Friedberg |  NYC/Comets.com |
Deniz Gencaga |  CCNY/EE, NOAA-CREST |  speaker
Dimitrios Giannakis |  Center for Atmosphere Ocean Science, Courant Institute of Mathematical Sciences |  speaker
Irina Gladkova |  CCNY/Computer Science |
Elizabeth Gomez |  Penn State University/Statistics |  speaker
Joshua Gordon |  Columbia/Computer Science |
Sam Gordon |  Columbia |
Michael Grossberg |  CCNY/Computer Science |

Participants cont’

Michael Haken |  NASA/GSFC, Science Systems & Applications, Inc. |
---|---|---
Zachary Haberman |  SUNY at Albany/Physics |
Naveed Hasan |  Columbia/Computer Science |
Nicholas Hatzopoulos |  CUNY Gradate Center |
William D Heavlin |  Google, Inc |  speaker
Kay Hiranaka |  CUNY Graduate Center |
Hao Huang |  Stony Brook University/Computer Science |
Darryl Hutchinson |  CUNY Graduate Center |
Ilknur Icke |  CUNY Graduate Center/Computer Science |
Geetha Jagannathan |  Columbia/Computer Science |
Jon Jenkins |  SETI Institute/NASA Ames Research Center |  speaker
Will Jessop |  Columbia/Statistics |  speaker
Ed Kaita |  SSAI@GSFC/NASA |
Eyal Kazin |  New York University |  speaker
Lee Case Klippel |  Columbia University |
Christian D. Klose |  Think GeoHazards |  speaker
Kirk Knobelspiesse |  ORAU-NASA/GISS |
Kevin Knuth |  SUNY at Albany |  speaker
Ioannis Kostopoulos |  CUNY Graduate Center |
Duane Lee |  Columbia/Astronomy |  speaker
Erbo Li |  Columbia/Computer Science |
Charles Liu |  CUNY at CSI |
Thomas Loredo |  Cornell/Astronomy |  speaker
Chris Malone |  SUNY at Stony Brook/Physics and Astronomy |
Szabolcs Marka |  Columbia/Physics |
Zsuzsa Marka |  Columbia Astrophysics Laboratory |
Haley Maunu |  SUNY at Albany/Physics |
Vinod Mohan |  Columbia |
Claire Monteleoni |  Columbia/Computer Science |  speaker

Participants cont’

Catherine Naud |  NASA/GISS |
---|---|---
Alejandro Nunez |  CUNY Graduate Center |
Indrani Pal |  IRI, The Earth Institute |
Vladimir Pavlovic |  Rutgers/Computer Science |
Joshua Peek |  Columbia/Astronomy |  speaker
Fergie Ramos |  Student/College of New Rochelle |
Khary Richardson |  CUNY Graduate Center |
William Rossow |  CCNY/NOAA-CREST |
Syamantak Saha |  NYU Stern |
Destry Saul |  Columbia/Astronomy |
Joshua Schlieder |  SUNY at Stony Brook |
Frank Scalzo |  NASA/GISS |
Bodhisattva Sen |  Columbia/Statistics |
Monika Sikand |  Stevens Institute of Tech/Physics |
Michal Simon |  SUNY at Stony Brook/Physics and Astronomy |
Ishan Singh |  Columbia |
Damain Sowinski |  CUNY Graduate Center |
Ilya Tsinis |  NYU/Courant |
Maria Tzortziou |  GSFC/NASA - University of Maryland |
Michael Way |  NASA/GISS |
Adrian Weller |  Columbia/Computer Science |
Laird Whitehill |  Cornell/Astronomy |
Alexander Wong |  JP Morgan Chase |
Nettie Wong |  American Museum of Natural History |
Emmi Yonekura |  Columbia University |
Shinjae Yoo |  Brookhaven National Lab/Computer Science Center |
Sejong Yoon |  Rutgers/Computer Science |
Dantong Yu |  Brookhaven National Lab |

Video Links

Introduction |  Michael Way
---|---
http://www.youtube.com/watch?v=CHEoya_e2Do |  (NASA/GISS)
How long will it take. A historical approach to boundary crossing |  Victor de la Peña
http://www.youtube.com/watch?v=3gfHeerVqHs |  (Columbia U)
Cosmology through the Large-Scale Structure of the Universe |  Eyal Kazin
http://www.youtube.com/watch?v=es4dH0jBJYw |  (NYU)
On the shoulders of Gauss, Bessel, and Poisson: links, chunks, spheres, and conditional models |  William Heavlin
http://www.youtube.com/watch?v=FzFAxaXTkUQ |  (Google Inc.)
Mining Citizen Science Data: Machine Learning Challenges |  Kirk Borne
http://www.youtube.com/watch?v=XoS_4axsb5A |  (GMU)
Tracking Climate Models: Advances in Climate Informatics |  Claire Monteleoni
http://www.youtube.com/watch?v=78IeffwV6bU |  (Columbia U)
Spectral Analysis Methods for Complex Source Mixtures |  Kevin Knuth
http://www.youtube.com/watch?v=t9mCoff5YZo |  (Suny/Albany)
Beyond Objects: Using machines to understand the diffuse universe |  Joshua Peek
http://www.youtube.com/watch?v=hgp8CeR43So |  (Columbia U)
Viewpoints: A high-performance visualization and analysis tool |  Michael Way
http://www.youtube.com/watch?v=FsW64idYw6c |  (NASA/GISS)
Clustering Approach for Partitioning Directional Data in Earth and Space Sciences |  Christian Klose
http://www.youtube.com/watch?v=5Ak6_rvayqg |  (Think Geohazards)
Planetary Detection: The Kepler Mission |  Jon Jenkins
http://www.youtube.com/watch?v=2dnA95smRE0 |  (NASA/Ames)
Understanding the possible influence of the solar activity on the terrestrial climate: A times series analysis approach |  Elizabeth Martínez-Gómez
http://www.youtube.com/watch?v=CXmC1dh9Wdg |  (Penn State)
Bayesian adaptive exploration applied to optimal scheduling of exoplanet Radial Velocity observations |  Tom Loredo
http://www.youtube.com/watch?v=B1pVtHmu9E0 |  (Cornell U)
Bayesian Inference from Photometric Surveys |  Tamas Budavari
http://www.youtube.com/watch?v=xCzUl0HtWGM |  (JHU)
Long-Range Forecasts Using Data Clustering and Information Theory |  Dimitris Giannakis
http://www.youtube.com/watch?v=pFDqP94btCg |  (NYU)
Comparison of Information-Theoretic Methods to estimate the information flow in a dynamical system |  Deniz Gencaga
http://www.youtube.com/watch?v=ejX_MWImP6A |  (CCNY)
Reconstructing the Galactic halo’s accretion history: |  Duane Lee &
A finite mixture model approach |  Will Jessop
http://www.youtube.com/watch?v=moehYYsIOFw |  (Columbia U)


# Coloring problems on arrangements of pseudolines111 S. Roch was funded by
the DFG-Research Training Group ’Facets of Complexity’ (DFG-GRK 2434). Special
thanks to Rimma Hämäläinen for the stimulating discussions on this topic.

Sandro Roch  Technische Universität Berlin
<EMAIL_ADDRESS>
###### Abstract

Arrangements of pseudolines are a widely studied generalization of line
arrangements. They are defined as a finite family of infinite curves in the
Euclidean plane, any two of which intersect at exactly one point. One can
state various related coloring problems depending on the number $n$ of
pseudolines. In this article, we show that $n$ colors are sufficient for
coloring the crossings avoiding twice the same color on the boundary of any
cell, or, alternatively, avoiding twice the same color along any pseudoline.
We also study the problem of coloring the pseudolines avoiding monochromatic
crossings.

##  1 Introduction

An arrangement of pseudolines or pseudoline arrangement is a finite family of
simple continuous curves $f_{1},\cdots,f_{n}:\mathbb{R}\to\mathbb{R}^{2}$ in
the Euclidean plane with

$\lim_{t\to\infty}\lVert f_{i}(t)\rVert=\lim_{t\to-\infty}\lVert
f_{i}(t)\rVert=\infty,$

and the property that each pair $f_{i},f_{j}$, $i\neq j$ crosses in exactly
one point. A pseudoline arrangement is simple, if at most two pseudolines
cross in a single point, see Figure 1(a) and Figure 1(b) for examples of a
non-simple and a simple arrangement of $6$ pseudolines.

(a)

(b)

(c)

Figure 1: A non-simple (a) and a simple (b) pseudoline arrangement together
with a corresponding tiling (c).

Pseudoline arrangements are widely studied objects. They were first described
in 1926 by Levi [18] and were further studied by Ringel [20] and Grünbaum
[13]. Every line arrangement is also a pseudoline arrangement. On the other
hand, there exist arrangements of at least $n\geq 8$ pseudolines that cannot
be “strechted”, i.e. they are not isomorphic to any line arrangement, see [20]
and [12]. But pseudoline arrangements are not only a generalization of line
arrangements: Isomorphism classes of simple arrangements are in correspondence
with a rich variety of other objects, such as rhombic tilings of
$2$-dimensional zonotopes (indicated in Figure 1(c)), classes of reduced words
of permutations and oriented matroids of rank $3$. For a general introduction
to pseudoline arrangements we refer to [8], [10] and [2, ch. 6].

###  1.1 Related work

In 2006, Felsner, Hurtado, Noy and Streinu [9] studied the arrangement graph
$G_{\mathcal{A}}$ of a pseudoline arrangement $\mathcal{A}$, which consists of
the crossings in $\mathcal{A}$ as vertices and its edges are formed by the
arcs between them. They give a short argument that $G_{\mathcal{A}}$ can be
colored using three colors if $\mathcal{A}$ is simple. As $G_{\mathcal{A}}$ is
planar, it is clearly $4$-colorable, including for non-simple arrangements. In
[5] one can find an infinite family of line arrangements that require $4$
colors.

In 2013, Bose et al. [3] introduced further coloring problems on line
arrangements. An arrangement decomposes the Euclidean plane into cells: The
example in Figure 1(a) consists of $7$ bounded cells and $12$ unbounded cells.
One of the most remarkable results in [3] states that coloring the lines of a
simple arrangement of $n$ lines avoiding cells whose bounding lines have all
the same color requires at most $\mathcal{O}(\sqrt{n})$ colors. This was
improved to $\mathcal{O}(\sqrt{n/\log n})$ by Ackerman, Pach, Pinchasi,
Radoičić and Tóth [1], extending it also to non-simple line arrangements.
Finding line arrangements that require many colors in such a coloring seems to
be a difficult task; in [3] they provide a construction that requires
$\Omega\left(\log/n\log\log n\right)$ colors.

###  1.2 Results

In [3] and [1], the language of hypergraph coloring serves as a common
formalization of the different coloring concepts and allows for the use of
results from this field. If $\mathcal{H}=(V,\mathcal{E})$ is a hypergraph, a
vertex coloring of $\mathcal{H}$ is a coloring of the vertices avoiding
monochromatic edges, i.e. hyperedges whose contained vertices are assigned all
the same color, while an edge coloring of $\mathcal{H}$ is a coloring of the
hyperedges with no vertex being incident to two edges of the same color. The
(vertex) chromatic number $\chi(\mathcal{H})$ is the minimal number of colors
of a vertex coloring, while the edge chromatic number
$\chi^{\prime}(\mathcal{H})$ is the minimal number of colors of an edge
coloring. Note that vertex coloring is not equivalent to edge coloring of the
hypergraph dual.

Our results can all be stated in terms of two hypergraphs: The vertices of
$\mathcal{H}_{\text{cell-vertex}}(\mathcal{A})$ are the (bounded and
unbounded) cells of $\mathcal{A}$, and each crossing $c$ defines a hyperedge
consisting of the cells that contain $c$ on their boundary. At the same time,
the hypergraph $\mathcal{H}_{\text{line-vertex}}(\mathcal{A})$ is defined on
the set of $n$ pseudolines as vertices and each crossing in $\mathcal{A}$
defines a hyperedge consisting of the pseudolines involved in $c$. Section 2
is devoted to problems in which the crossings are colored. We show
$\chi^{\prime}(\mathcal{H}_{\text{cell-vertex}})\leq n$ for every pseudoline
arrangement:

######  Theorem 1.

Let $\mathcal{A}$ be an arrangement of $n$ pseudolines. The crossings of
$\mathcal{A}$ can be colored using $n$ colors so that no color appears twice
on the boundary of any cell.

Figure 2: Coloring that fulfills the statements of Theorem 1 and Theorem 2
simultaneously.

The abovementioned results in [3] and [1] are bounds on the chromatic number
of a hypergraph $\mathcal{H}_{\text{line-cell}}$ restricted to the case of
line arrangements. However, none of the coloring problems that are discussed
in [3] relates lines with crossings. This is done in the following two
theorems, the first one of which shows $\chi^{\prime}(\mathcal{H}_{\text{line-
vertex}})\leq n$:

######  Theorem 2.

Let $\mathcal{A}$ be an arrangement of $n$ pseudolines. The crossings of
$\mathcal{A}$ can be colored using $n$ colors so that no color appears twice
along any pseudoline.

Figure 2 shows an example of a coloring as guaranteed in Theorem 1 and in
Theorem 2. In Section 3, we study the number of colors required to color the
pseudolines avoiding monochromatic crossings. In addition to several minor
results, we prove:

######  Theorem 3.

Let $\mathcal{A}$ be an arrangement of $n$ pseudolines. The pseudolines of
$\mathcal{A}$ can be colored using $\mathcal{O}(\sqrt{n})$ colors avoiding
monochromatic crossings of degree at least $4$.

Here, the degree of a crossing is the number of pseudolines that intersect in
said crossing.

##  2 Coloring crossings

###  2.1 Avoiding twice the same color on the boundary of any cell

The following Lemma 1 and Lemma 2 are well-known facts about pseudoline
arrangements. They constitute the drawing of a pseudoline arrangement as a
wiring diagram, see [10]. Assuming such a wiring diagram, our proof of Theorem
2 will consist of a greedy coloring of the crossings from left to right.
Nevertheless, we provide the simple proofs of these facts for the sake of
completeness. The following Lemma 1 implies that a bounded (unbounded) cell
contains at most $n$ ($n-1$) crossings on its boundary.

######  Lemma 1.

For any cell $F$ and any pseudoline $l$ in a pseudoline arrangement, $l$
contains at most one boundary segment of $F$.

###### Proof.

Suppose $l$ contains two boundary segments $r$ and $s$ of $F$ as in Figure 3.
Then there is at least one intermediate segment $t$ that belongs to a
pseudoline $l^{\prime}$ which must intersect $l$ at least twice. This
contradicts the definition of a pseudoline arrangement. ∎

Figure 3: Proof idea of Lemma 1.

In the following, we assume that a fixed unbounded cell of $\mathcal{A}$ is
marked as the north cell $N$. This induces an orientation of the pseudolines
in which $N$ lies to the left of each pseudoline, see Figure 4(a). Moreover,
this induces an orientation of the arrangement graph $G_{\mathcal{A}}$, whose
vertices are the crossings and its edges represent the arcs between any two
successive crossings, see Figure 4(b).

(a)

(b)

(c)

Figure 4: The orientation induced by fixing a north cell is acyclic.

######  Lemma 2.

The directed graph $G_{\mathcal{A}}$ is acyclic.

###### Proof.

Number the pseudolines in counterclockwise order, starting from $N$, as shown
in Figure 4(b). Suppose there is a counterclockwise oriented cycle of length
$k$ consisting of arcs that belong to the pseudolines
$l_{1},\cdots,l_{k},l_{k+1}=l_{1}$ in this order. For any $i$, $l_{i+1}$
crosses $l_{i}$ from right to left, which implies $l_{i}\leq l_{i+1}$, see
Figure 4(c) for an illustration. Hence $l_{1}\leq\cdots\leq l_{k}\leq
l_{k+1}=l_{1}$, therefore $l_{1}=\cdots=l_{k}$, which is a contradiction. The
argument for a clockwise cycle is analogous. ∎

Fix a topological sorting $\pi$ of $G_{\mathcal{A}}$, which exists because of
the fact that $G_{\mathcal{A}}$ is acyclic (Lemma 2). We aim for coloring the
crossings of $\mathcal{A}$ greedily in the order of $\pi$. For any crossing
$c$, a conflict ancestor is a crossing $c^{\prime}$ that comes before $c$
w.r.t. $\pi$ and both $c$ and $c^{\prime}$ are on the boundary of a common
cell. Figure 5(a) shows an example: The red crossings are conflict ancestors
of $c$; the orange crossing may be a conflict ancestor depending on $\pi$.

(a)

(b)

(c)

Figure 5: (a): Example for conflict ancestors; (b), (c): Distinction between
the cases of $F$ being an unbounded or a bounded cell in the proof of Lemma 3.

######  Lemma 3.

Independently of the choice of the topological sorting, every crossing has at
most $n-1$ conflict ancestors.

###### Proof.

Let $c$ be a crossing of degree $k$ in $\mathcal{A}$, and let
$p_{1},\cdots,p_{k}$ denote the involved pseudolines. Let
$\mathcal{A^{\prime}}:=\mathcal{A}-\\{p_{1},\cdots,p_{k}\\}$ be the
arrangement obtained by dropping $p_{1},\cdots,p_{k}$. Let $F$ be the cell of
$\mathcal{A^{\prime}}$ in whose area $c$ lies in $\mathcal{A}$. Every conflict
ancestor $c^{\prime}$ of $c$ is a crossing on the boundary of $F$, which is
either also a crossing in $\mathcal{A}^{\prime}$ (type I), or arises as a
crossing when reinserting $p_{1},\cdots,p_{k}$ (type II). We distinguish two
cases, which are both illustrated in Figure 5(b) and Figure 5(c). In both
Figures, crossings that can be conflict ancestors of $c$ are colored yellow
(type I) or green (type II).

  * •

Case 1: The cell $F$ is unbounded. By Lemma 1, $F$ contains at most $n-k-1$
crossings on its boundary, which bounds the conflict ancestors of type I.
Reinserting $p_{1},\cdots,p_{k}$ in $\mathcal{A}^{\prime}$ adds at most $2k$
crossings on the boundary of $F$, of which at most $k$ are incoming neighbors
of $c$. The outgoing ones cannot be conflict ancestors of $c$, as they appear
after $c$ in every topological sorting. Hence, the conflict ancestors of type
II are bounded by $k$. In total, $c$ has at most $n-1$ conflict ancestors.

  * •

Case 2: The cell $F$ is bounded. By Lemma 1, $F$ contains at most $n-k$
crossings on its boundary, which bounds the conflict ancestors of type I. As
in the previous case, conflict ancestors of type II are bounded by $k$. So far
this argument shows that $c$ has at most $n$ conflict ancestors in total. We
have to argue that at least one of the crossings in $\mathcal{A^{\prime}}$
that lie on the boundary of $F$ cannot be a conflict ancestor of type I.
Observe that in $G_{\mathcal{A}}$ there always exists a directed path from $c$
to some crossing $t$ in $\mathcal{A^{\prime}}$ which lies on the boundary of
$F$: Starting from $c$, take any outgoing arc to some crossing $c^{\prime}$.
If $c^{\prime}$ is not already a crossing in $\mathcal{A^{\prime}}$, then
follow the pseudoline that forms in $\mathcal{A}^{\prime}$ the boundary
segment of $F$ on which $c^{\prime}$ lies until reaching a crossing in
$\mathcal{A^{\prime}}$ (See path $c$-$c^{\prime}$-$t$ in the example in Figure
5(c)). In every topological sorting, $t$ comes after $c$, so $t$ cannot be a
conflict ancestor of $c$.∎

###### Proof of Theorem 1.

Mark an arbitrary unbounded cell in $\mathcal{A}$ as the north cell. Choose an
arbitrary topological sorting $\pi$ of the corresponding acyclic orientation
of $G_{\mathcal{A}}$ (Lemma 2). Color the crossings in this order: When
coloring a crossing $c$, we cannot use a color that was already assigned to a
crossing $c^{\prime}$ which lies together with $c$ on the boundary of a common
cell. These are exactly the conflict ancestors, whose number is bounded by
$n-1$ in Lemma 3. So among $n$ colors, there is always a spare color
available. ∎

The bound in Theorem 1 is tight: Consider a convex $n$-gon $F$ without
parallel sides. Extending the sites in a straight way to infinity defines a
line arrangement in which $F$ is a cell that has $n$ crossings on its
boundary, see Figure 6. Hence, avoiding twice the same color on the boundary
of $F$ requires $n$ colors.

Figure 6: Construction that shows that Theorem 1 is tight. Figure 7: Coloring
simple arrangements is equivalent to edge-coloring of $K_{n}$.

###  2.2 Avoiding twice the same color along any pseudoline

In view of Theorem 2, we now focus on coloring the crossings of a pseudoline
arrangement $\mathcal{A}$ avoiding twice the same color along any pseudoline.
If $\mathcal{A}$ is simple, this is equivalent to edge-coloring of the
complete graph $K_{n}$, see Figure 7. It is a well-known fact that if $n$ is
odd one requires exactly $n$ colors, and if $n$ is even then $n-1$ colors are
sufficient. So Theorem 2 is interesting in particular for non-simple
arrangements. Unfortunately, we were unable to find an elementary proof or a
simple deterministic algorithm for establishing such a coloring in the non-
simple case, even though intuitively it seems to be the easier case, as less
crossings appear on each pseudoline.

In 1972, Erdős, Faber and Lovász met on a party and came up with the following
problem (see [7]): Let $A_{1},\cdots,A_{n}$ be a family of sets, each of
cardinality $n$, and $\lvert A_{i}\cap A_{j}\rvert\leq 1$ for all $i<j$. Can
one color the elements of $\bigcup_{i}A_{i}$ using $n$ colors such that each
$A_{i}$ contains all colors? This became known as the Erdős-Faber-Lovász
conjecture. It was eventually proven in 2021 by Kang et al. [15]. In
hypergraph language, it is equivalent to the following statement:

######  Theorem 4 (D. Y. Kang, T. Kelly, D. Kühn, A. Methuku & D. Osthus,
2021).

For every simple hypergraph $\mathcal{H}$ with $n$ vertices,
$\chi^{\prime}(H)\leq n$.

Here, a hypergraph $\mathcal{H}=(V,\mathcal{E})$ is simple if all hyperedges
have cardinality at least $2$ and for all $E_{1},E_{2}\in\mathcal{E}$,
$E_{1}\neq E_{2}$ it holds that $\lvert E_{1}\cap E_{2}\rvert\leq 1$.

###### Proof of Theorem 2.

The statement is equivalent to the existence of an edge-coloring of the
hypergraph $\mathcal{H}_{\text{line-vertex}}$ using $n$ colors.
$\mathcal{H}_{\text{line-vertex}}$ is simple, because there can be at most one
pseudoline passing through any pair of crossings, otherwise this would mean a
pair of pseudolines crossing twice. Then the statement follows from Theorem 4.
∎

It would be nice to have a bound on the required number of colors that also
takes into account how far the arrangement is away from being a simple
arrangement. For this purpose, we introduce $\operatorname{mx}(\mathcal{A})$,
which is defined as the maximal number of crossings along any pseudoline in
$\mathcal{A}$. For simple arrangements we have
$\operatorname{mx}(\mathcal{A})=n-1$. If one excludes trivial arrangements in
which all pseudolines cross in a single point
($\operatorname{mx}(\mathcal{A})=1$), then the parameter $\operatorname{mx}$
bounds the number of pseudolines from above. This is why
$\operatorname{mx}(\mathcal{A})$ can be interpreted as an alternative measure
of the size of an arrangement. In fact it was shown recently in [6] that the
number of pseudolines is linearly bounded by $\operatorname{mx}$, in
particular $n\leq 845\cdot\operatorname{mx}(\mathcal{A})$ for large values of
$n$. A weaker quadratic upper bound can be obtained as a simple observation:

######  Observation 1.

For every non-trivial arrangement $\mathcal{A}$ of $n$ pseudolines we have

$n\leq\operatorname{mx}(\mathcal{A})\left(\operatorname{mx}(\mathcal{A})-1\right)+1\leq\left(\operatorname{mx}(\mathcal{A})\right)^{2}.$

###### Proof.

Let $l$ be an arbitrary pseudoline of $\mathcal{A}$. Every other pseudoline
crosses $l$ in one of at most $\operatorname{mx}(\mathcal{A})$ crossings. Let
$c$ be any such crossings. The pseudolines that cross $l$ in $c$ must cross
any other pseudoline $l^{\prime}\neq l$ in distinct crossings; see Figure 8(a)
for an illustration. Hence, their number is bounded by
$\operatorname{mx}(\mathcal{A})-1$, as $l^{\prime}$ has one further crossing
with $l$ and at most $\operatorname{mx}(\mathcal{A})$ crossings in total.
Therefore, the number of pseudolines different to $l$ is bounded by
$\operatorname{mx}(\mathcal{A})\left(\operatorname{mx}(\mathcal{A})-1\right)$.
∎

(a)

(b)

Figure 8: (a): Illustration for the proof of Observation 1; (b): Arrangement
with $\operatorname{mx}=4$ that requires $7$ colors.

######  Conjecture 1.

There is a constant $c$ so that the crossings of every pseudoline arrangement
$\mathcal{A}$ can be colored using $\operatorname{mx}(\mathcal{A})+c$ colors
so that no color appears twice along any pseudoline.

Figure 8(b) shows a coloring of an arrangement $\mathcal{A}$ with $9$
pseudolines and $\operatorname{mx}(\mathcal{A})=4$ using $7$ colors. One can
verify that this coloring is minimal. Hence, a constant as in Conjecture 1 had
to fulfill $c\geq 3$. We were unable to find any arrangement where this gap is
larger. If such a constant exists we expect it to be small.

We make use of the following result by Kahn [14, 16] in order to show that
Conjecture 1 holds at least asymptotically and under a certain restriction. A
hypergraph $\mathcal{H}$ is $k$-bounded if all hyperedges have cardinality at
most $k$. Moreover, the codegree $\operatorname{codeg}(\mathcal{H})$ is
defined as the maximum intersection $\lvert E_{1}\cap E_{2}\rvert$ over all
pairs of hyperedges $E_{1},E_{2}\in\mathcal{E}$, $E_{1}\neq E_{2}$.

######  Theorem 5 (Kahn, 1996).

For every $k,\varepsilon>0$, there exists $\delta>0$ such that the following
holds: If $\mathcal{H}$ is a $k$-bounded hypergraph of maximum degree at most
$D$ and $\operatorname{codeg}(\mathcal{H})\leq\delta\cdot D$, then
$\mathcal{H}$ can be list edge colored using $(1+\varepsilon)\cdot D$ colors.

The following Proposition 1 is a simple application of Theorem 5.

######  Proposition 1.

For every $k,\varepsilon>0$, there exists an $\text{mx}_{0}\in\mathbb{N}$ so
that the following holds: If a pseudoline arrangement $\mathcal{A}$ only
contains crossings of degree at most $k$ and fulfills
$\operatorname{mx}(\mathcal{A})\geq\text{mx}_{0}$, then its crossings can be
colored using $(1+\varepsilon)\cdot\operatorname{mx}(\mathcal{A})$ colors so
that no color appears twice along any pseudoline.

###### Proof.

Let $k,\varepsilon>0$. Applying Theorem 5 provides a certain $\delta>0$. Set
$\text{mx}_{0}:=1/\delta$.

Now let $\mathcal{A}$ be a pseudoline arrangement that only contains crossings
of degree at most $k$ and with
$\operatorname{mx}(\mathcal{A})\geq\text{mx}_{0}$. The maximum degree $D$ of
$\mathcal{H}_{\text{line-vertex}}$ equals $\operatorname{mx}(\mathcal{A})$.
Moreover, the codegree of $\mathcal{H}_{\text{line-vertex}}$ is exactly $1$,
because two crossings in $\mathcal{A}$ can have at most one pseudoline in
common, hence $\operatorname{codeg}(\mathcal{H}_{\text{line-
vertex}})=1\leq\delta\cdot D$. Finally, $\mathcal{H}_{\text{line-vertex}}$ is
$k$-bounded, as each crossing in $\mathcal{A}$ is of degree at most $k$. Then,
by the statement of Theorem 5, the hypergraph $\mathcal{H}_{\text{line-
vertex}}$ can be list edge colored using
$(1+\varepsilon)\cdot\operatorname{mx}(\mathcal{A})$ colors. By the simple
fact that list edge coloring is stronger than edge coloring, this implies the
existence of the desired coloring of $\mathcal{A}$ using the same number of
colors. ∎

##  3 Coloring pseudolines

A _pseudoline coloring_ of an arrangement $\mathcal{A}$ is defined as a
coloring of the pseudolines in $\mathcal{A}$ such that there are no
monochromatic crossings, i.e. crossings of pseudolines of a single color
class. We let $\chi_{pl}(\mathcal{A})$ denote the minimal number of colors in
a pseudoline coloring of $\mathcal{A}$.

###  3.1 Pseudoline colorings and ordinary points

The study of pseudoline colorings is closely related to the study of _ordinary
points_. An ordinary point is defined as a crossing of exactly two
pseudolines, also known as simple crossing. Every non-trivial pseudoline
arrangement contains at least $\lceil 6n/13\rceil$ ordinary points [17]. Two
pseudolines that cross each other in an ordinary point must be assigned
different colors. Hence, for simple arrangements $\mathcal{A}$ we have
$\chi_{pl}(\mathcal{A})=n$.

In the following we want to take a closer look at the relationship between
$\chi_{pl}(\mathcal{A})$ and the structure of the ordinary points in a
pseudoline arrangement. For this purpose, we define the ordinary graph
$G_{o}(\mathcal{A})$ that has the $n$ pseudolines of $\mathcal{A}$ as its
vertices and two of them share an edge if and only if they cross each other in
an ordinary point. Clearly,
$\chi_{pl}(\mathcal{A})\geq\chi(G_{o}(\mathcal{A}))$.

As a first natural question we ask how many ordinary points a pseudoline
arrangement can have if it admits a pseudoline coloring with $k$ colors. Let
$\sigma_{k}(n)$ denote the maximum number of ordinary points of an arrangement
$\mathcal{A}$ of $n$ pseudolines with $\chi_{pl}(\mathcal{A})\leq k$.

######  Proposition 2.

We have $\sigma_{k}(n)\in\Theta(n^{2})$. More precisely, let $t_{k}(n)$ denote
the Turán number, i.e. the maximum number of edges that a graph on $n$
vertices without containing a $(k+1)$-clique can have. Then we have
$t_{k}(n)-n\leq\sigma_{k}(n)\leq t_{k}(n)$.

###### Proof.

For the upper bound, suppose that an arrangement of pseudolines $\mathcal{A}$
has more than $t_{k}(n)$ ordinary points, so $G_{o}(\mathcal{A})$ has more
than $t_{k}(n)$ edges. By Turán’s theorem, $G_{o}(\mathcal{A})$ contains a
$(k+1)$-clique, so the corresponding pseudolines $p_{1},\cdots,p_{k+1}$
pairwise cross in ordinary points, and hence, must be colored using at least
$k+1$ different colours.

For the lower bound, take any simple arrangement of $k$ pseudolines and
replace each of them by a strip of $\lfloor n/k\rfloor$ or $\lceil n/k\rceil$
parallel pseudolines, so that one obtains an “arrangement” of $n$ curves in
total. So far, the ordinary graph of this “arrangement” is identical to the
Turán graph having $t_{k}(n)$ edges. In order to make it a proper pseudoline
arrangement, one has to twist each of the strips, as illustrated in Figure 9
on an example with $k=4$ and $n=14$. This reduces the number of ordinary
points by $n$. The so obtained arrangement $\mathcal{A}$ clearly fulfills
$\chi_{pl}(\mathcal{A})\leq k$. ∎

Figure 9: Constructing an arrangement with $t_{k}(n)-n$ ordinary points.

We would like to know how much $\chi_{pl}(\mathcal{A})$ and
$\chi(G_{o}(\mathcal{A}))$ can differ and make the folloring observation:

######  Proposition 3.

There are arbitrarily large arrangements with
$\chi_{pl}(\mathcal{A})=2\cdot\chi(G_{o}(\mathcal{A}))$.

###### Proof.

Start with a simple arrangement of $r$ pseudolines. Replace each pseudoline by
a strip of $3$ pseudolines, each of them being twisted in an additional
crossing of degree $3$. The ordinary graph of the so obtained arrangement
$\mathcal{A}$ of $3r$ pseudolines is the complete $r$-partite graph
$K_{3,\cdots,3}$, which can be $r$-colored. However, for a pseudoline
coloring, one requires $2$ distinct colors for each of the $r$ strips, so
$\chi_{pl}(\mathcal{A})=2r$. Figure 10 gives an example. ∎

Figure 10: Arrangement $\mathcal{A}$ with $\chi_{pl}(\mathcal{A})=6$ and
$\chi(G_{o}(\mathcal{A}))=3$.

It is unknown to us whether the factor of $2$ in Proposition 3 can be further
improved.

Next, we want to analyse the computatiponal complexity of
$\chi_{pl}(\mathcal{A})$. The following lemma serves as an NP-hardness
reduction.

######  Lemma 4.

For every graph $G$ on $n$ vertices and $m$ edges, there exists an arrangement
$\mathcal{A}_{G}$ of $n+\binom{n}{2}-m+1$ pseudolines with
$\chi_{pl}(\mathcal{A}_{G})\in\\{\chi(G)+1,\chi(G)+2\\}$ that can be computed
efficiently.

###### Proof.

Let $G=(V,E)$ be a graph. Assume $V=[n]$ and let $m=\lvert E\rvert$. Consider
an arbitrary simple arrangement $\mathcal{A}$ of $n$ pseudolines in which the
pseudolines are drawn as $x$-monotone curves and no two crossings lie on a
vertical line, see for example the brown pseudolines in Figure 11. Label these
pseudolines by $l_{1},\cdots,l_{n}$. For all $1\leq i<j\leq n$ with
$\\{i,j\\}\notin E$ insert a pseudoline $L_{i,j}$ (green) by drawing a
vertical line going through the crossing between $l_{i}$ and $l_{j}$ and let
all these new pseudolines $L_{i,j}$ cross each other in a common point $p$
lying above $l_{1},\cdots,l_{n}$. Insert one further pseudoline $L^{*}$
(orange) which crosses $l_{1},\cdots,l_{n}$ in ordinary points and the
pseudolines $L_{i,j}$ in $p$.

It remains to show that the so obtained arrangement $\mathcal{A}_{G}$ on
$n+\binom{n}{2}-m+1$ pseudolines fulfills
$\chi(G)+1\leq\chi_{pl}(\mathcal{A})\leq\chi(G)+2$. For the upper bound, given
a proper $k$-coloring $c$ of $G$, observe that the following coloring is a
valid pseudoline coloring of $\mathcal{A}_{G}$: Assign color $c(i)$ to
$l_{i}$, to each pseudoline $L_{i,j}$ assign an extra color $k+1$ and to
pseudoline $L^{*}$ a further extra color $k+2$. For the lower bound, assume
there exists a coloring $c$ of $\mathcal{A}_{G}$ using only $\chi(G)$ colors.
For each $(i,j)\in E$, pseudolines $l_{i}$ and $l_{j}$ must have different
colors, since they cross in an ordinary point. Therefore, by the minimality of
$\chi(G)$, all $\chi(G)$ colors appear on $l_{1},\cdots,l_{n}$ at least once.
As $L^{*}$ crosses all of them in ordinary points, a further color is
required, contradiction. ∎

Figure 11: Reduction from approximating $\chi(G)$ to computing
$\chi_{pl}(\mathcal{A})$.

######  Proposition 4.

Given an arrangement of pseudolines $\mathcal{A}$, it is NP-hard to compute
$\chi_{pl}(\mathcal{A})$.

###### Proof.

In [21] it was shown that for every $\varepsilon>0$, given a graph $G$,
approximating the chromatic number $\chi(G)$ within $n^{1-\varepsilon}$ is NP-
hard. Via Lemma 4, a polynomial time algorithm for computing
$\chi_{pl}(\mathcal{A})$ would provide such an approximation of $\chi(G)$ in
polynomial time. ∎

###  3.2 Avoiding monochromatic crossings of high degrees

Even though $\chi_{pl}(\mathcal{A})$ and $\chi(G_{o}(\mathcal{A}))$ can differ
by a multiplicative factor, as stated in Proposition 3, for most arrangements,
$\chi_{pl}(\mathcal{A})$ does not seem to be far away from
$\chi(G_{o}(\mathcal{A}))$. This is why our focus lies now on a variant of
pseudoline colorings: Instead of avoiding monochromatic crossings of any
degree, including ordinary points, we only forbid crossings of certain degrees
to be monochromatic.

######  Lemma 5.

Let $l,r\in\mathbb{N}$ and let $\mathcal{A}$ be an arrangement of $n$
pseudolines. Then, using

$\left(\frac{4(l+r)}{l-1}n\right)^{\frac{1}{l-1}}\in\mathcal{O}(n^{\frac{1}{l-1}})$

colors, $\mathcal{A}$ can be colored avoiding monochromatic crossings of
degree within $\\{l,l+1,\cdots,l+r\\}$.

###### Proof.

The case $l=2$ is trivial, so assume $l\geq 3$. For some integer $k$, choose
for each pseudoline one out of $k$ colors randomly with uniform distribution.
For each crossing $c$ of degree
$\operatorname{deg}(c)\in\\{l,l+1,\cdots,l+r\\}$, consider the event $E(c)$
that $c$ is monochromatic. We have

$\mathbb{P}[E(c)]=\frac{1}{k^{\operatorname{deg}(c)-1}}\leq\frac{1}{k^{l-1}}=:p.$

Moreover, $E(c)$ is mutually independent of the set of events $E(c^{\prime})$
for all crossings $c^{\prime}$ in $\mathcal{A}$ that do not have a common
pseudoline with $c$. These are all but at most

$\operatorname{deg(c)}\frac{n}{l-1}\leq\frac{l+r}{l-1}n=:d$

many. Applying Lovász Local Lemma (see [19]) on the family of events
$\\{E(c)\\}$, guarantees that with non-zero probability none of these events
occur if $4pd\leq 1$, which is the case when

$k\geq\left(\frac{4(l+r)}{l-1}n\right)^{\frac{1}{l-1}}.$

The statement follows. ∎

Using Lemma 5 we are now able to prove Theorem 3.

###### Proof of Theorem 3.

Assume that all crossings have degree at most $\sqrt{n}$. In this case,
applying Lemma 5 with $l=4$ and $r=\sqrt{n}-4$ gives that

$\left(\frac{4\sqrt{n}}{3}n\right)^{\frac{1}{3}}\in\mathcal{O}(\sqrt{n})$

colors are sufficient in order to avoid monochromatic crossings of degree at
least $4$.

Now, if $\mathcal{A}$ contains crossings of degree higher than $\sqrt{n}$,
eliminate such a crossing by dropping the corresponding bundle of pseudolines
from the arrangement. Repeat this step until all crossings have degree at most
$\sqrt{n}$. One requires less than $\sqrt{n}$ iterations as each iteration
removes more than $\sqrt{n}$ pseudolines. By the argument above, the remaining
arrangement $\mathcal{A^{\prime}}$ can be colored avoiding monochromatic
crossings of degree at least $4$. When reinserting each of the at most
$\sqrt{n}$ removed bundles of pseudolines, one needs at most $2$ extra colors,
in total $2\sqrt{n}$ extra colors. ∎

If we only want to avoid monochromatic crossings of a single degree, then we
can obtain a stronger result by applying again a result from the hypergraph
coloring literature. The following theorem is due to Frieze and Mubayi [11].
Its proof is also based on the probabilistic method, but in addition to Lovász
Local Lemma it uses a rather involved analysis including the Chernoff bound. A
hypergraph is $k$-uniform if all its hyperedges have cardinality $k$.

######  Theorem 6 (Frieze & Mubayi, 2013).

Fix $k\geq 3$. Let $\mathcal{H}$ be a $k$-uniform simple hypergraph with
maximum degree $\triangle$. Then

$\chi(\mathcal{H})\leq
c\left(\frac{\triangle}{\log\triangle}\right)^{\frac{1}{k-1}},$

where $c$ only depends on $k$.

######  Proposition 5.

Fix some $l\geq 3$ and let $\mathcal{A}$ be an arrangement of $n$ pseudolines.
Then, the pseudolines in $\mathcal{A}$ can be colored using

$c\cdot\left(\frac{\operatorname{mx}(\mathcal{A})}{\log\operatorname{mx}(\mathcal{A})}\right)^{\frac{1}{l-1}}\in\mathcal{O}\left(\left(\frac{n}{\log
n}\right)^{\frac{1}{l-1}}\right)$

colors avoiding monochromatic crossings of degree exactly $l$, where $c$ only
depends on $l$.

###### Proof.

Recall that pseudoline coloring is equivalent to vertex coloring of
$\mathcal{H}_{\text{line-vertex}}$. However, if we only aim for avoiding
monochromatic crossings of degree $l$, then we only care about hyperedges of
degree $l$ and delete all other hyperedges. The resulting hypergraph is simple
and $l$-uniform. Its maximum degree degree $\triangle$ equals
$\operatorname{mx}(\mathcal{A})$. The statement is hence a direct application
of Theorem 6. ∎

##  4 Conclusion and Future Work

We consider Theorem 1 as our main result. When coloring the crossings avoiding
twice the same color along any pseudoline, Theorem 2 is a direct application
of the recently proven Erdős-Faber-Lovász conjecture. However, for the
specific hypergraphs induced by pseudoline arrangements, one could hope for a
simple deterministic coloring procedure, like the one proposed in [4] that
requires $\lceil(3/2)n-2\rceil$ colors.

We mentioned Conjecture 1 as an open problem. One may also ask whether there
always exists a coloring using $n$ colors that satisfies the conditions of
Theorem 1 and Theorem 2 simultaneously. Figure 12 shows an arrangement of $5$
pseudolines as a counterexample: coloring the crossings avoiding twice the
same color around any cell and twice the same color along any peudoline
requires at least $6$ colors. Are there arbitrarily large examples like that?

When it comes to pseudoline colorings, we asked whether
$\chi_{pl}(\mathcal{A})$ and $\chi(G_{o}(\mathcal{A}))$ can differ by a factor
larger than $2$. Finally, in view of Lemma 5, Theorem 3 and Proposition 5, we
expect it to be possible to color the pseudolines of every arrangement using
$\mathcal{O}(n^{\frac{1}{l-1}})$ colors avoiding monochromatic crossings of
degree at least $l$.

Figure 12: Arrangement of $5$ pseudolines that cannot be simultaneously
colored as in Theorem 1 and Theorem 2.

## References

  * [1] Eyal Ackerman, János Pach, Rom Pinchasi, Radoš Radoičić, and Géza Tóth.  A note on coloring line arrangements.  Electron. J. Combin., 21(2):Article Number 2.23, 2014.  doi:10.37236/2660.
  * [2] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter Ziegler.  Oriented matroids, volume 46 of Encycl. Math. Appl. Cambridge University Press, 2nd edition, 1999.  doi:10.1017/CBO9780511586507.
  * [3] Prosenjit Bose, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, and Perouz Taslakian.  Coloring and guarding arrangements.  Discrete Math. Theor. Comput. Sci., 15(3):139–154, 2013.  URL: https://dmtcs.episciences.org/2072/pdf.
  * [4] W. I. Chang and E. L. Lawler.  Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász.  Combinatorica, 8(3):293–295, 1988.  doi:10.1007/BF02126801.
  * [5] Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Felix Schröder, Raphael Steiner, and Birgit Vogtenhuber.  Coloring circle arrangements: New 4-chromatic planar graphs.  Eur. J. Comb., 2023.  doi:10.1016/j.ejc.2023.103839.
  * [6] Adrian Dumitrescu.  The Dirac–Goodman–Pollack conjecture.  Discrete Comput. Geom., 2023.  doi:10.1007/s00454-023-00487-z.
  * [7] Paul Erdős.  On the combinatorial problems which I would most like to see solved.  Combinatorica, 1:25–42, 1981.  doi:10.1007/BF02579174.
  * [8] Stefan Felsner and Jacob E. Goodman.  Pseudoline arrangements.  In Csaba D. Tóth, Jacob E. Goodman, and Joseph O’Rourke, editors, Handbook of discrete and computational geometry, Discrete Math. Appl., chapter 5. CRC Press, Boca Raton, FL, 3rd revised and updated edition, 2017.
  * [9] Stefan Felsner, Ferran Hurtado, Marc Noy, and Ileana Streinu.  Hamiltonicity and colorings of arrangement graphs.  Discrete Appl. Math., 154(17):2470–2483, 2006.  doi:10.1016/j.dam.2006.04.006.
  * [10] Stefan Felsner and Helmut Weil.  Sweeps, arrangements and signotopes.  Discrete Appl. Math., 109(1-2):67–94, 2001.  doi:10.1016/S0166-218X(00)00232-8.
  * [11] Alan Frieze and Dhruv Mubayi.  Coloring simple hypergraphs.  J. Comb. Theory, Series B, 103(6):767–794, 2013.  doi:https://doi.org/10.1016/j.jctb.2013.09.003.
  * [12] Jacob E. Goodman and Richard Pollack.  Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines.  J. Comb. Theory, Ser. A, 29:385–390, 1980.  doi:10.1016/0097-3165(80)90038-2.
  * [13] Branko Grünbaum.  Arrangements and spreads, volume 10 of Reg. Conf. Ser. Math. Amer. Math. Soc., Providence, RI, 1972.
  * [14] Jeff Kahn.  Asymptotically good list-colorings.  J. Comb. Theory, Ser. A, 73(1):1–59, 1996.  doi:10.1006/jcta.1996.0001.
  * [15] Dong Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.  A proof of the Erdős-Faber-Lovász conjecture.  Ann. Math. (2), 198(2):537–618, 2023.  doi:10.4007/annals.2023.198.2.2.
  * [16] Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.  Graph and hypergraph colouring via nibble methods: A survey, 2021.  arXiv:2106.13733.
  * [17] Jonathan Lenchner.  Sylvester-Gallai Results and Other Contributions to Combinatorial and Computational Geometry.  PhD thesis, Polytechnic University, 2008.
  * [18] Friedrich Levi.  Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade.  Berichte Leipzig 78, 256-267, 1926.
  * [19] Michael Molloy and Bruce Reed.  Graph colouring and the probabilistic method, volume 23 of Algorithms and Combinatorics.  Springer Berlin, 2002.
  * [20] Gerhard Ringel.  Über Geraden in allgemeiner Lage.  Elemente der Mathematik, 12:75–82, 1957.  doi:10.5169/seals-19211.
  * [21] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3:103–128, 2007.  doi:10.4086/toc.2007.v003a006.