% 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}