% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.23}{21(2)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins



\usepackage{latexsym,epsfig}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{enumerate}
%\usepackage{url,hyperref}
\usepackage{subfigure}
%\usepackage[margin=1.0in]{geometry}

\let\doendproof\endproof

\long\def\cut{\ignore}
\long\def\ignore#1{}

\def\DB{{\rm DB}}
\def\eps{\varepsilon}
\def\ch{{\rm ch}}
\def\cross{{\rm cr}}
\def\eqdef{\stackrel{\mathrm{def}}{=}}

\newenvironment{packed_enum}{

\begin{enumerate}[(1)]
  \setlength{\itemsep}{2pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}

\newenvironment{proofof}[1]
      {\medskip\noindent{\em Proof of #1:}\hspace{1mm}}
      {\hfill$\Box$\medskip}


\graphicspath{{.},{figures/}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[lemma]{Observation}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{problem}[lemma]{Problem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{claim}[lemma]{Claim}

\def\qed{\ifvmode\mbox{ }\else\unskip\fi\hskip 1em plus 10fill$\Box$}
\newcommand{\Ex}{\mathop{\bf E\/}}
\def\A{\mathcal{A}}
\def\HH{\mathcal{H}}
\def\R{\mathbb{R}}

\newcommand{\segment}[1]{\overline{#1}}
\newcommand{\ray}[1]{\overrightarrow{#1}}

\newcommand{\bbox}{\vrule height7pt width4pt depth1pt}

\def\eyal#1{{\sc Eyal says: }{\marrow\sf #1}}
\def\rom#1{{\sc Rom says: }{\marrow\sf #1}}
\def\geza#1{{\sc G\'{e}za says: }{\marrow\sf #1}}
\def\janos#1{{\sc J\'{a}nos says: }{\marrow\sf #1}}
\def\rados#1{{\sc Rado\v{s} says: }{\marrow\sf #1}}



\title{\bf A note on coloring line arrangements}

\author{
Eyal Ackerman\\
\small Department of Mathematics, Physics, and Computer Science\\[-0.8ex]
\small University of Haifa at Oranim\\[-0.8ex]
\small Tivon 36006, Israel\\
\small {\tt ackerman@sci.haifa.ac.il}\\
\and
J\'{a}nos Pach\thanks{
Supported by NSF grant CCF-08-30272,  by Hungarian Science Foundation EuroGIGA Grant OTKA NN 102029, and by 
Swiss National Science Foundation grants 200021-137574 and
200020-144531.}\\
\small EPFL, Lausanne, Switzerland\\[-0.8ex]
\small  and Alfr\'ed R\'{e}nyi Institute, Budapest, Hungary\\
\small {\tt pach@cims.nyu.edu} \\
\and
Rom Pinchasi\thanks{
Supported by ISF grant (grant No. 1357/12).}\\
\small Mathematics Department\\[-0.8ex]
\small Technion---Israel Institute of Technology\\[-0.8ex]
\small Haifa 32000, Israel\\
\small {\tt room@math.technion.ac.il}\\ 
\and
Rado\v{s} Radoi\v{c}i\'{c}\\
\small Department of Mathematics, Baruch College\\[-0.8ex]
\small City University of New York, New York, U.S.A.\\
\small {\tt rados.radoicic@baruch.cuny.edu}\\
\and
G\'{e}za T\'{o}th\thanks{
Supported by Hungarian Science Foundation Grant OTKA K
83767 and NN 102029.}\\
\small Alfr\'{e}d R\'{e}nyi Institute\\[-0.8ex]
\small Budapest, Hungary\\
\small {\tt geza@renyi.hu} 
}

\date{\dateline{Aug 26, 2012}{Apr 26, 2014}{May 9, 2014}\\
\small Mathematics Subject Classifications: 52C30}

\begin{document}

\maketitle

\vspace*{-\baselineskip}

\begin{abstract}
We show that the lines of every arrangement of $n$ lines in the plane can be colored
with $O(\sqrt{n/ \log n})$ colors such that no face of the arrangement is monochromatic.
This improves a bound of Bose et al.~by a $\Theta(\sqrt{\log n})$ factor.
Any further improvement on this bound would also improve
the best known lower bound on the following problem of Erd\H{o}s:
estimate the maximum number of points in general position
within a set of $n$ points containing no four collinear points.
\end{abstract}

{\bf Keywords:} Arrangements of lines, chromatic number, sparse hypergraphs.

\section{Introduction}
\label{sec:intro}

Given a \emph{simple} arrangement $\A$ of a set $L$ of lines in $\R^2$ (no parallel lines and no three lines going
through the same point), decomposing the plane into the set $C$ of cells (i.e. maximal connected components of
$\R^2\setminus L$), Bose et al.~\cite{BCC12} defined a hypergraph $\HH_{\mbox{\tiny{line-cell}}} = (L, C)$
with the vertex set $L$ (the set of lines of $\A$), and each hyperedge $c\in C$ being defined by the set of
lines forming the boundary of a cell of $\A$. They initiated the study of the chromatic number of
$\HH_{\mbox{\tiny{line-cell}}}$, and proved that for $|L| = n$, $\chi (\HH_{\mbox{\tiny{line-cell}}}) = O(\sqrt{n})$
and $\chi (\HH_{\mbox{\tiny{line-cell}}}) = \Omega \left(\frac{\log{n}}{\log{\log{n}}}\right)$.
In other words, they proved that the lines of every simple arrangement of $n$ lines can be colored with
$O(\sqrt{n})$ colors so that there is no monochromatic face; furthermore, they provided an intricate construction
of a simple arrangement of $n$ lines that requires $\Omega \left(\frac{\log{n}}{\log{\log{n}}}\right)$ colors.

%Let $\A$ be an arrangement of lines in the plane.
%Denote by $\chi(\A)$ the minimum number of colors required for
%coloring the lines of $\A$ such that there is no monochromatic face in $\A$,
%that is, the boundary of every face is colored with at least two colors.
%Bose et al.~\cite{BCC12} proved that $\chi(A) \leq O(\sqrt{n})$ for every
%\emph{simple} arrangement $\A$ of $n$ lines, and that there are arrangements
%that require $\Omega(\log n / \log\log n)$ colors.

In this short note, we improve their upper bound by a $\Theta(\sqrt{\log n})$ factor,
and extend it to not necessarily simple arrangements.

\begin{theorem}\label{thm:main}
The lines of every arrangement of $n$ lines in the plane can be colored
with $O(\sqrt{n/ \log n})$ colors so that no face of the arrangement is monochromatic.
\end{theorem}

A set of points in the plane is in \emph{general position} if it does not contain three collinear points.
Let $\alpha(S)$ denote the maximum number of points in general position in a set $S$ of points in the plane,
and let $\alpha_{4}(n)$ be the minimum of $\alpha(S)$ taken over all sets $S$ of $n$ points in the plane with
no four point on a line. Erd\H{o}s pointed out that $\alpha_{4}(n) \leq n/3$ and suggested the problem of
determining or estimating $\alpha_{4}(n)$.
F\"uredi~\cite{Fu91} proved that $\Omega(\sqrt{n \log n}) \leq \alpha_{4}(n) \leq o(n)$.

We observe that any improvement of the bound in Theorem~\ref{thm:main}
would immediately imply a better lower bound for $\alpha_{4}(n)$.
Indeed, suppose that $\chi(A) \leq k(n)$ for any arrangement of $n$ lines,
and let $P$ be a set of $n$ points, no four on a line.
Let $P^*$ be the dual arrangement of a slightly perturbed $P$
(according to the usual point-line duality, see, e.g.,~\cite[\S~8.2]{BCKO08}).
Color $P^*$ with $k(n)$ colors such that no face is monochromatic,
let $S^* \subseteq P^*$ be the largest color class, and let $S$ be its dual point set.
Observe that the size of $S$ is at least $n/k(n)$ and it does not contain three
collinear points, since the three lines that correspond to any three collinear points in $P$
bound a face of size three in $P^*$.

\section{Proof of Theorem~\ref{thm:main}}
\label{sec:proof}

Let $\A$ be an arrangement of a set $L$ of $n$ lines, decomposing the plane into the set $C$ of
cells, and let $\HH_{\mbox{\tiny{line-cell}}}$ be the corresponding hypergraph (defined as in the previous
section). We show that $\chi (\HH_{\mbox{\tiny{line-cell}}}) = O\left(\sqrt{\frac{n}{\log{n}}}\right)$.

%We show that $O(\sqrt{n/\log n})$ colors suffice for coloring the lines of $\A$
%such that no face in $\A$ is monochromatic.
%% First, observe that it is enough to consider the faces of size at least three.
%% Indeed, suppose we manage to color the lines in $\A$ with $k$ colors such that no face
%% of size at least three is monochromatic.
%% Define a graph whose vertex set consists of the lines in $\A$ and in which
%% two vertices are adjacent if the two corresponding lines bound a face of size two.
%% Since every line bounds at most four faces of size two, this graph is $5$-colorable.
%% Therefore $\chi(A) \leq 5k$.
%Call a subset of lines \emph{independent} if there is no face %(of size at least three)
%that is bounded just by lines from this subset.

An independent set in $\HH_{\mbox{\tiny{line-cell}}}$ is a set $S\subset L$ such that for every
$c\in C$, $c$ is not a subset of $S$ (in other words, no cell of $\A$ has its boundary formed only by
lines in $S$). The proof is based on the following fact.

\begin{theorem}\label{thm:independent}
There is an absolute constant $c>0$ such that the size $\alpha (\HH_{\mbox{\tiny{line-cell}}})$ of the
maximum independent set is at least $c\sqrt{n \log n}$.
%There is an absolute constant $c>0$ such that every arrangement of $n$ lines contains at least
%$c\sqrt{n \log n}$ independent lines.
\end{theorem}

We color the lines in $\A$ so that no face %of size at least three
is monochromatic by following the same method as in~\cite{BCC12} (where they used the weaker
version of Theorem~\ref{thm:independent} stating $\alpha (\HH_{\mbox{\tiny{line-cell}}}) = \Omega (\sqrt{n})$).
That is, we iteratively find a large independent set of lines (whose existence is
guaranteed by Theorem~\ref{thm:independent}), color them with the same (new) color, and remove them from $\A$.
% Once the number of remaining lines is at most $\sqrt{n/\log n}$, we assign a unique
% color to each of them and the algorithm terminates.

Clearly, this algorithm produces a valid coloring.
We verify, by induction on $n$, that at most $\frac{2}{c}\sqrt{n/\log n}$ colors are used in this coloring. We assume the bound is valid for all $n \leq 256$
(by taking sufficiently small $c>0$). For $n>256$, we have
$\log 4 < \frac{1}{4}\log n$.
Let $i$ be the smallest integer such that after $i$ iterations the number of remaining lines is at most $n/4$.
Since in each of these iterations at least $c\sqrt{\frac{n}{4}\log\frac{n}{4}} \geq c\sqrt{\frac{n}{8}\log n}$ vertices (lines) are removed,
$i \leq \frac{n/4}{c\sqrt{\frac{n}{8}\log n}} \leq \frac{1}{\sqrt{2}c}\sqrt{n/\log n}$.
Therefore, by the induction hypothesis the number of colors that the algorithm uses is at most
\begin{align*}
\hspace*{28mm} i+\frac{2}{c}\sqrt{\frac{\frac{n}{4}}{\log \frac{n}{4}}} &\leq
\frac{1}{\sqrt{2}c}\sqrt{\frac{n}{\log n}} + \frac{1}{c}\sqrt{\frac{n}{\log n-\frac{1}{4}\log n}}\\ 
&< \frac{1}{\sqrt{2}c}\sqrt{\frac{n}{\log n}} + \frac{\sqrt{4/3}}{c}\sqrt{\frac{n}{\log n}} < \frac{2}{c}\sqrt{\frac{n}{\log n}}.\hspace*{21mm}\text{\qed}
\end{align*}

The proof of Theorem~\ref{thm:independent} is based on a result on independent sets in sparse hypergraphs.
%A \emph{hypergraph} $H=(V,E)$ consists of a set of vertices $V$
%and a set of edges $E \subseteq 2^V$.
%If the size of every edge is $k$, then $H$ is \emph{$k$-uniform}.
%For a set $Z \subseteq V$ the \emph{induced} hypergraph $H[Z]$
%consists of $Z$ and the edges of $H$ that are contained in $Z$.
%A set $I \subseteq V$ is an \emph{independent set} of $H$, if $I$ contains no edge of $H$.
%
%Kostochka et al.~\cite{KMV} proved that every $n$-vertex $(k+1)$-uniform hypergraph
%in which every $k$ vertices are contained in at most $d < n/(\log n)^{3k^2}$ edges
%contains an independent set of size $\Omega\left(\left(\frac{n}{d}\log\frac{n}{d}\right)^{1/k}\right)$.
Given a hypergraph $\HH$ on a vertex set $V$, the sub-hypergraph $\HH[X]$ induced by $X \subset V$ consists of all
edges of $\HH$ that are contained in $X$. A hypergraph $\HH = (V, E)$ is $k$-uniform if every edge $e\in E$ has
size $k$. Given a $k$-uniform hypergraph $\HH$ and a set $S\subset V$ with $|S| = k-1$, the co-degree of $S$ is
the number of all vertices $v\in V$ such that $S\cup \{v\}\in E$. Kostochka et al.~\cite{KMV} proved that if
$\HH$ is a $k$-uniform hypergraph, $k\ge 3$, with all co-degrees at most $d$, then
$\alpha (\HH) \ge c_{k}\left(\frac{n}{d}\log \frac{n}{d}\right)^{\frac{1}{k-1}}$, where $c_k > 0$.

%In fact, a careful look at their proof reveals the following result,
%that we stated for $3$-uniform hypergraphs, since this is the case that we need.
%
%\begin{theorem}[\cite{KMV}]\label{thm:hypergraphs}
%Let $H=(V,E)$ be an $n$-vertex $3$-uniform hypergraph,
%such that every pair of vertices appear in at most $d < n /(\log n)^{12}$ edges.
%Let $X \subseteq V$ be a random set of vertices chosen independently with probability
%$p=n^{-2/5}/(d\log\log\log n)^{3/5}$,
%and let $Z$ be an independent set chosen uniformly at random from the independent sets in $H[X]$.
%Then with high probability $\Ex[|Z|] \geq \Omega(\sqrt{n \log n})$.
%\end{theorem}

In fact, a careful look at their proof reveals the following result, that we state for
$3$-uniform hypergraphs, since this is the case that we need.

\begin{lemma}[\cite{KMV}]\label{thm:hypergraphs}
Let $\HH = (V, E)$ be a $3$-uniform hypergraph on $|V| = n$ vertices with all co-degrees at most $d$,
$d < n/(\log{n})^{12}$. Let $X$ be a random subset of $V$, obtained by choosing each vertex of $V$ independently
with probability $p = \frac{n^{-2/5}}{(d\log{\log{\log{n}}})^{3/5}}$. Let $Z$ be a set chosen uniformly at
random among all the independent sets of $\HH[X]$. Then, with high probability $|Z| = \Omega (\sqrt{n\log{n}})$.
\end{lemma}

With Lemma~\ref{thm:hypergraphs} in hand we can now prove Theorem~\ref{thm:independent}.

\begin{proofof}{Theorem~\ref{thm:independent}}
%Let $L$ be a set of $n$ lines and let $\A$ be the corresponding arrangement.
%For a subset $L' \subseteq L$ we say that a face $f$ of $\A$ is \emph{bad} with respect to $L'$
%if all the lines bounding $f$ are in $L'$.
%
%Define a $3$-uniform hypergraph $H$ whose vertex set are the lines in $\A$ and whose edge set
%consists of sets of three vertices such that the corresponding lines bound a face of size three in $\A$.
%Observe that every pair of lines can bound at most four faces of size three,
%therefore every pair of vertices in $H$ appears in at most four edges.
%Let $X$ be a random set of vertices (lines) chosen independently with probability
%$p=n^{-2/5}/(4\log\log\log n)^{3/5}$.
%There are $O(n^2)$ faces in $\A$ and $O(n)$ of them are of size two (since every line can bound at most four
%such faces).
%Therefore, the expected number of bad faces with respect to $X$ of size different than three is
%$O(p^2n+p^4n^2)=o(\sqrt{n/\log n})$.
%
%It follows from Theorem~\ref{thm:hypergraphs} and Markov's inequality that with high probability
%the set of lines that correspond to $X$ contains a subset $Z$ of $\Omega(\sqrt{n \log n})$ lines
%such that there are no faces of size three that are bad with respect to $Z$,
%and the number of bad faces of size different than three is $o(\sqrt{n/\log n})$.
%By removing from $Z$ a vertex from each bad face we obtain an independent set of lines
%of size $\Omega(\sqrt{n \log n})$.
A cell of an arrangement $\A$ is called an $r$-cell, if $r$ lines of $L$ are forming its boundary.
Let $\HH_{\triangle} \subset \HH_{\mbox{\tiny{line-cell}}}$ be the $3$-uniform hypergraph with the vertex set $L$
being the set of lines, and each hyperedge defined by the triple of lines forming the boundary of a 3-cell
of $\A$. Since any two lines can participate in the boundaries of at most four 3-cells of $\A$,
all co-degrees of $\HH$ are at most $d = 4$. Now, as in Lemma~\ref{thm:hypergraphs}, let
$X$ be a random subset of $L$, obtained by choosing each line in $L$ independently with probability
$p = \frac{n^{-2/5}}{(4\log{\log{\log{n}}})^{3/5}}$. Since there are $O(n^2)$ faces in $\A$ and $O(n)$ of
them are 2-cells (since every line can bound at most four such faces), the expected number of $2$-cells of
$\A$ in $\HH_{\mbox{\tiny{line-cell}}}[X]$ is $O(p^2n) = o(\sqrt{n\log{n}})$, and the expected number of
$r$-cells, $r\ge 4$, of $\A$ in $\HH_{\mbox{\tiny{line-cell}}}[X]$ is $O(p^4n^2) =  o(\sqrt{n\log{n}})$.
From Lemma~\ref{thm:hypergraphs} it follows that there exists a set $Z \subset X \subset L$ of size
$\Omega (\sqrt{n\log{n}})$, that is an independent set of $\HH_{\triangle}[X]$, and such that
the number of $r$-cells, $r\neq 3$, of $\A$ in $\HH_{\mbox{\tiny{line-cell}}}[Z]$ is $o(\sqrt{n\log{n}})$.
Removing from $Z$ one vertex (line) for each such $r$-cell, we obtain an independent set of
$\HH_{\mbox{\tiny{line-cell}}}$ of size $\Omega (\sqrt{n\log{n}})$.
\end{proofof}

%\paragraph{Acknowledgment.}
%We thank anonymous referees for several helpful suggestions for improving the presentation of the paper.


\begin{thebibliography}{99}
%\itemsep -1pt

\bibitem{BCC12}
P.~Bose, J.~Cardinal, S.~Collette, F.~Hurtado, S.~Langerman, M.~Korman, and P.~Taslakian,
Coloring and guarding arrangements,
{\em Discrete Mathematics and Theoretical Computer Science} {\bf 15} (2013),
139--154. Also in: 
{\em 28th European Workshop on Computational Geometry (EuroCG)},
March 19--21, 2012, Assisi, Perugia, Italy, 89--92. 

\bibitem{BCKO08}
M.~de Berg, O.~Cheong, M.~van Krefeld, M.~Overmars,
{\em Computational Geometry: Algorithms and Applications},
3rd edition, Springer, 2008.

\bibitem{Fu91}
Z.~F\"uredi,
Maximal independent subsets in Steiner systems and in planar sets,
{\em SIAM J.\ Disc.\ Math.}~{\bf 4}~(1991), 196--199.

\bibitem{KMV}
A.~Kostochka, D.~Mubayi, J.~Verstra\"{e}te,
On independent sets in hypergraphs,
{\em Random Structures and Algorithms} {\bf 44} (2014), 224--239.

\end{thebibliography}

\end{document}
