-
A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
Authors:
Seth Pettie,
Gábor Tardos
Abstract:
The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width.
The foremost open problems in this area is to resolve the…
▽ More
The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width.
The foremost open problems in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern $P\in\{0,1\}^{k\times l}$ is the bipartite incidence matrix of an acyclic graph (forest), then $\mathrm{Ex}(P,n) = O(n\log^{C_P} n)$, where $C_P$ is a constant depending only on $P$. This conjecture has been confirmed on many small patterns, specifically all $P$ with weight at most 5, and all but two with weight 6.
The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that $\mathrm{Ex}(S_0,n),\mathrm{Ex}(S_1,n) \geq n2^{Ω(\sqrt{\log n})}$, where $S_0,S_1$ are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns $(P_t)$, specifically that for every $t\geq 2$, $\mathrm{Ex}(P_t,n)=Θ(n(\log n/\log\log n)^t)$. This is the first proof of an asymptotically sharp bound that is $ω(n\log n)$.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
On edge-ordered graphs with linear extremal functions
Authors:
Gaurav Kucheriya,
Gábor Tardos
Abstract:
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is $Ω(n\log n)$. This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-or…
▽ More
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is $Ω(n\log n)$. This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs. We also extend the study of extremal function of short edge-ordered paths by Gerbner et al. to some longer paths.
△ Less
Submitted 11 July, 2024; v1 submitted 19 September, 2023;
originally announced September 2023.
-
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Authors:
Seth Pettie,
Gábor Tardos
Abstract:
The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function $\mathrm{Ex}(P,n)$, which is the maximum weight of a matrix $A\in\{0,1\}^{n\times n}$ whose submatrices avoid a fixed pattern $P\in\{0,1\}^{k\times l}$. This theory has been wildly successful at resolving problems in combinatorics, discrete and computational geometry, structural graph theory, and the analys…
▽ More
The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function $\mathrm{Ex}(P,n)$, which is the maximum weight of a matrix $A\in\{0,1\}^{n\times n}$ whose submatrices avoid a fixed pattern $P\in\{0,1\}^{k\times l}$. This theory has been wildly successful at resolving problems in combinatorics, discrete and computational geometry, structural graph theory, and the analysis of data structures, particularly corollaries of the dynamic optimality conjecture.
All these applications use acyclic patterns, meaning that when $P$ is regarded as the adjacency matrix of a bipartite graph, the graph is acyclic. The biggest open problem in this area is to bound $\mathrm{Ex}(P,n)$ for acyclic $P$. Prior results have only ruled out the strict $O(n\log n)$ bound conjectured by Furedi and Hajnal. It is consistent with prior results that $\forall P. \mathrm{Ex}(P,n)\leq n\log^{1+o(1)} n$, and also consistent that $\forall ε>0.\exists P. \mathrm{Ex}(P,n) \geq n^{2-ε}$.
In this paper we establish a stronger lower bound on the extremal functions of acyclic $P$. Specifically, we give a new construction of relatively dense 0-1 matrices with $Θ(n(\log n/\log\log n)^t)$ 1s that avoid an acyclic $X_t$. Pach and Tardos have conjectured that this type of result is the best possible, i.e., no acyclic $P$ exists for which $\mathrm{Ex}(P,n)\geq n(\log n)^{ω(1)}$.
△ Less
Submitted 3 July, 2023; v1 submitted 28 June, 2023;
originally announced June 2023.
-
Where have all the grasshoppers gone?
Authors:
János Pach,
Gábor Tardos
Abstract:
Let $P$ be an $N$-element point set in the plane. Consider $N$ (pointlike) grasshoppers sitting at different points of $P$. In a "legal" move, any one of them can jump over another, and land on its other side at exactly the same distance. After a finite number of legal moves, can the grasshoppers end up at a point set, similar to, but larger than $P$? We present a linear algebraic approach to answ…
▽ More
Let $P$ be an $N$-element point set in the plane. Consider $N$ (pointlike) grasshoppers sitting at different points of $P$. In a "legal" move, any one of them can jump over another, and land on its other side at exactly the same distance. After a finite number of legal moves, can the grasshoppers end up at a point set, similar to, but larger than $P$? We present a linear algebraic approach to answer this question. In particular, we solve a problem of Brunck by showing that the answer is yes if $P$ is the vertex set of a regular $N$-gon and $N\neq 3, 4, 6$. Some generalizations are also considered.
△ Less
Submitted 7 May, 2023; v1 submitted 7 November, 2022;
originally announced November 2022.
-
Successive vertex orderings of fully regular graphs
Authors:
Lixing Fang,
Hao Huang,
Janos Pach,
Gabor Tardos,
Junchi Zuo
Abstract:
A graph G = (V,E) is called fully regular if for every independent set $I\subset V$ , the number of vertices in $V\setminus$ I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orde…
▽ More
A graph G = (V,E) is called fully regular if for every independent set $I\subset V$ , the number of vertices in $V\setminus$ I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph.
As an application of our results, we give alternative proofs of two theorems of Stanley and Gao + Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.
△ Less
Submitted 28 October, 2022; v1 submitted 27 June, 2022;
originally announced June 2022.
-
A characterization of edge-ordered graphs with almost linear extremal functions
Authors:
Gaurav Kucheriya,
Gábor Tardos
Abstract:
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. arXiv:2001.00849. They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are $n^{1+o(1)}$. Here we resolve this conjecture proving the stronger upper bound of $n2^{O(\sqrt{\log n})}$. This represents a gap in the family of possible extremal function…
▽ More
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. arXiv:2001.00849. They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are $n^{1+o(1)}$. Here we resolve this conjecture proving the stronger upper bound of $n2^{O(\sqrt{\log n})}$. This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions $Ω(n^c)$ for some $c>1$. However, our result is probably not the last word: here we conjecture that the even stronger upper bound of $n\log^{O(1)}n$ also holds for the same set of extremal functions.
△ Less
Submitted 17 May, 2023; v1 submitted 26 June, 2022;
originally announced June 2022.
-
Random necklaces require fewer cuts
Authors:
Noga Alon,
Dor Elboim,
János Pach,
Gábor Tardos
Abstract:
It is known that any open necklace with beads of $t$ types in which the number of beads of each type is divisible by $k$, can be partitioned by at most $(k-1)t$ cuts into intervals that can be distributed into $k$ collections, each containing the same number of beads of each type. This is tight for all values of $k$ and $t$.
Here, we consider the case of random necklaces, where the number of bea…
▽ More
It is known that any open necklace with beads of $t$ types in which the number of beads of each type is divisible by $k$, can be partitioned by at most $(k-1)t$ cuts into intervals that can be distributed into $k$ collections, each containing the same number of beads of each type. This is tight for all values of $k$ and $t$.
Here, we consider the case of random necklaces, where the number of beads of each type is $km$. Then the minimum number of cuts required for a ``fair'' partition with the above property is a random variable $X(k,t,m)$. We prove that for fixed $k,t,$ and large $m$, this random variable is at least $(k-1)(t+1)/2$ with high probability. For $k=2$, fixed $t$, and large $m$, we determine the asymptotic behavior of the probability that $X(2,t,m)=s$ for all values of $s\le t $. We show that this probability is polynomially small when $s<(t+1)/2$, it is bounded away from zero when $s>(t+1)/2$, and decays like $Θ( 1/\log m)$ when $s=(t+1)/2$.
We also show that for large $t$, $X(2,t,1)$ is at most $(0.4+o(1))t$ with high probability and that for large $t$ and large ratio $k/\log t$, $X(k,t,1)$ is $o(kt)$ with high probability.
△ Less
Submitted 29 December, 2021;
originally announced December 2021.
-
Disjointness graphs of short polygonal chains
Authors:
János Pach,
Gábor Tardos,
Géza Tóth
Abstract:
The {\em disjointness graph} of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is {\em $χ$-bounded}, that is, its chromatic number $χ(G)$ is upper bounded by a function of its clique number $ω(G)$.
Here we show that this statement does not rema…
▽ More
The {\em disjointness graph} of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is {\em $χ$-bounded}, that is, its chromatic number $χ(G)$ is upper bounded by a function of its clique number $ω(G)$.
Here we show that this statement does not remain true for systems of polygonal chains of length $2$. We also construct systems of polygonal chains of length $3$ such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) \emph{$2$-way infinite} polygonal chains of length $3$ is $χ$-bounded: for every such graph $G$, we have $χ(G)\le(ω(G))^3+ω(G).$
△ Less
Submitted 11 December, 2021;
originally announced December 2021.
-
Crossings between non-homotopic edges
Authors:
János Pach,
Gábor Tardos,
Géza Tóth
Abstract:
We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily many edges. We prove that…
▽ More
We call a multigraph {\em non-homotopic} if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with $n$ vertices and $m>4n$ edges is larger than $c\frac{m^2}{n}$ for some constant $c>0$, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as $n$ is fixed and $m$ tends to infinity.
△ Less
Submitted 19 September, 2020; v1 submitted 26 June, 2020;
originally announced June 2020.
-
Convergence and limits of finite trees
Authors:
Gábor Elek,
Gábor Tardos
Abstract:
Motivated by the work of Lovász and Szegedy on the convergence and limits of dense graph sequences, we investigate the convergence and limits of finite trees with respect to sampling in normalized distance. Based on separable real trees, we introduce the notion of a dendron and show that the limits of finite trees are exactly the dendrons. We also prove that the limit dendron is unique.
Motivated by the work of Lovász and Szegedy on the convergence and limits of dense graph sequences, we investigate the convergence and limits of finite trees with respect to sampling in normalized distance. Based on separable real trees, we introduce the notion of a dendron and show that the limits of finite trees are exactly the dendrons. We also prove that the limit dendron is unique.
△ Less
Submitted 15 October, 2021; v1 submitted 3 January, 2020;
originally announced January 2020.
-
Turán problems for Edge-ordered graphs
Authors:
Dániel Gerbner,
Abhishek Methuku,
Dániel T. Nagy,
Dömötör Pálvölgyi,
Gábor Tardos,
Máté Vizer
Abstract:
In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called $\textit{edge-ordered}$, if its edges are linearly ordered. An isomorphism between edge-ordered graphs must respect the edge-order. A subgraph of an edge-ordered graph is itself an edge-ordered graph with the induced edge-order. We say that an edge-ordered graph $G$…
▽ More
In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called $\textit{edge-ordered}$, if its edges are linearly ordered. An isomorphism between edge-ordered graphs must respect the edge-order. A subgraph of an edge-ordered graph is itself an edge-ordered graph with the induced edge-order. We say that an edge-ordered graph $G$ $\textit{avoids}$ another edge-ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$.
The $\textit{Turán number}$ of an edge-ordered graph $H$ is the maximum number of edges in an edge-ordered graph on $n$ vertices that avoids $H$. We study this problem in general, and establish an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs -- we discover that the relevant parameter for the Turán number of an edge-ordered graph is its $\textit{order chromatic number}$. We establish several important properties of this parameter.
We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in Discrete Geometry.
△ Less
Submitted 30 October, 2021; v1 submitted 3 January, 2020;
originally announced January 2020.
-
On $4$-chromatic Schrijver graphs: their structure, non-$3$-colorability, and critical edges
Authors:
Gábor Simonyi,
Gábor Tardos
Abstract:
We give an elementary proof for the non-$3$-colorability of $4$-chromatic Schrijver graphs thus providing such a proof also for $4$-chromatic Kneser graphs. To this end we use a complete description of the structure of $4$-chromatic Schrijver graphs that was already given by Braun and even earlier in an unpublished manuscript by Li. We also address connections to surface quadrangulations. In parti…
▽ More
We give an elementary proof for the non-$3$-colorability of $4$-chromatic Schrijver graphs thus providing such a proof also for $4$-chromatic Kneser graphs. To this end we use a complete description of the structure of $4$-chromatic Schrijver graphs that was already given by Braun and even earlier in an unpublished manuscript by Li. We also address connections to surface quadrangulations. In particular, we show that a spanning subgraph of $4$-chromatic Schrijver graphs quadrangulates the Klein bottle, while another spanning subgraph quadrangulates the projective plane. The latter is a special case of a result by Kaiser and Stehlík. We characterize the color-critical edges of $4$-chromatic Schrijver graphs and also present preliminary results toward the characterization of color-critical edges in Schrijver graphs of higher chromatic number. Finally, we show that (apart from two cases of small parameters) the subgraphs we present that quadrangulate the Klein bottle are edge-color-critical. The analogous result for the subgraphs quadrangulating the projective plane is an immediate consequence of earlier results by Gimbel and Thomassen and was already noted by Kaiser and Stehlík.
△ Less
Submitted 8 December, 2019;
originally announced December 2019.
-
Planar Point Sets Determine Many Pairwise Crossing Segments
Authors:
János Pach,
Natan Rubin,
Gábor Tardos
Abstract:
We show that any set of $n$ points in general position in the plane determines $n^{1-o(1)}$ pairwise crossing segments. The best previously known lower bound, $Ω\left(\sqrt n\right)$, was proved more than 25 years ago by Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.
We show that any set of $n$ points in general position in the plane determines $n^{1-o(1)}$ pairwise crossing segments. The best previously known lower bound, $Ω\left(\sqrt n\right)$, was proved more than 25 years ago by Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.
△ Less
Submitted 30 April, 2023; v1 submitted 18 April, 2019;
originally announced April 2019.
-
Unlabeled Compression Schemes Exceeding the VC-dimension
Authors:
Dömötör Pálvölgyi,
Gábor Tardos
Abstract:
In this note we disprove a conjecture of Kuzmin and Warmuth claiming that every family whose VC-dimension is at most d admits an unlabeled compression scheme to a sample of size at most d. We also study the unlabeled compression schemes of the joins of some families and conjecture that these give a larger gap between the VC-dimension and the size of the smallest unlabeled compression scheme for th…
▽ More
In this note we disprove a conjecture of Kuzmin and Warmuth claiming that every family whose VC-dimension is at most d admits an unlabeled compression scheme to a sample of size at most d. We also study the unlabeled compression schemes of the joins of some families and conjecture that these give a larger gap between the VC-dimension and the size of the smallest unlabeled compression scheme for them.
△ Less
Submitted 14 October, 2021; v1 submitted 29 November, 2018;
originally announced November 2018.
-
Partitioning transitive tournaments into isomorphic digraphs
Authors:
Attila Sali,
Gábor Simonyi,
Gábor Tardos
Abstract:
In an earlier paper the first two authors have shown that self-complementary graphs can always be oriented in such a way that the union of the oriented version and its isomorphically oriented complement gives a transitive tournament. We investigate the possibilities of generalizing this theorem to decompositions of the complete graph into three or more isomorphic graphs. We find that a complete ch…
▽ More
In an earlier paper the first two authors have shown that self-complementary graphs can always be oriented in such a way that the union of the oriented version and its isomorphically oriented complement gives a transitive tournament. We investigate the possibilities of generalizing this theorem to decompositions of the complete graph into three or more isomorphic graphs. We find that a complete characterization of when an orientation with similar properties is possible seems elusive. Nevertheless, we give sufficient conditions that generalize the earlier theorem and also imply that decompositions of odd vertex complete graphs to Hamiltonian cycles admit such an orientation. These conditions are further generalized and some necessary conditions are given as well.
△ Less
Submitted 2 June, 2018;
originally announced June 2018.
-
Tiling the plane with equilateral triangles
Authors:
Janos Pach,
Gabor Tardos
Abstract:
Let $\cal T$ be a tiling of the plane with equilateral triangles no two of which share a side. We prove that if the side lengths of the triangles are bounded from below by a positive constant, then $\cal T$ is periodic and it consists of translates of only at most three different triangles. As a corollary, we prove a theorem of Scherer and answer a question of Nandakumar. The same result has been…
▽ More
Let $\cal T$ be a tiling of the plane with equilateral triangles no two of which share a side. We prove that if the side lengths of the triangles are bounded from below by a positive constant, then $\cal T$ is periodic and it consists of translates of only at most three different triangles. As a corollary, we prove a theorem of Scherer and answer a question of Nandakumar. The same result has been obtained independently by Richter and Wirth.
△ Less
Submitted 22 May, 2018;
originally announced May 2018.
-
Tilings of the plane with unit area triangles of bounded diameter
Authors:
Andrey Kupavskii,
János Pach,
Gábor Tardos
Abstract:
There exist tilings of the plane with pairwise noncongruent triangles of equal area and bounded perimeter. Analogously, there exist tilings with triangles of equal perimeter, the areas of which are bounded from below by a positive constant. This solves a problem of Nandakumar.
There exist tilings of the plane with pairwise noncongruent triangles of equal area and bounded perimeter. Analogously, there exist tilings with triangles of equal perimeter, the areas of which are bounded from below by a positive constant. This solves a problem of Nandakumar.
△ Less
Submitted 5 February, 2018; v1 submitted 8 December, 2017;
originally announced December 2017.
-
On the Turán number of ordered forests
Authors:
Dániel Korándi,
Gábor Tardos,
István Tomon,
Craig Weidert
Abstract:
An ordered graph $H$ is a simple graph with a linear order on its vertex set. The corresponding Turán problem, first studied by Pach and Tardos, asks for the maximum number $\text{ex}_<(n,H)$ of edges in an ordered graph on $n$ vertices that does not contain $H$ as an ordered subgraph. It is known that $\text{ex}_<(n,H) > n^{1+\varepsilon}$ for some positive $\varepsilon=\varepsilon(H)$ unless…
▽ More
An ordered graph $H$ is a simple graph with a linear order on its vertex set. The corresponding Turán problem, first studied by Pach and Tardos, asks for the maximum number $\text{ex}_<(n,H)$ of edges in an ordered graph on $n$ vertices that does not contain $H$ as an ordered subgraph. It is known that $\text{ex}_<(n,H) > n^{1+\varepsilon}$ for some positive $\varepsilon=\varepsilon(H)$ unless $H$ is a forest that has a proper 2-coloring with one color class totally preceding the other one. Making progress towards a conjecture of Pach and Tardos, we prove that $\text{ex}_<(n,H) =n^{1+o(1)}$ holds for all such forests that are "degenerate" in a certain sense. This class includes every forest for which an $n^{1+o(1)}$ upper bound was previously known, as well as new examples. Our proof is based on a density-increment argument.
△ Less
Submitted 21 November, 2017;
originally announced November 2017.
-
Tilings with noncongruent triangles
Authors:
Andrey Kupavskii,
János Pach,
Gábor Tardos
Abstract:
We solve a problem of R. Nandakumar by proving that there is no tiling of the plane with pairwise noncongruent triangles of equal area and equal perimeter. We also show that no convex polygon with more than three sides can be tiled with finitely many triangles such that no pair of them share a full side.
We solve a problem of R. Nandakumar by proving that there is no tiling of the plane with pairwise noncongruent triangles of equal area and equal perimeter. We also show that no convex polygon with more than three sides can be tiled with finitely many triangles such that no pair of them share a full side.
△ Less
Submitted 11 April, 2018; v1 submitted 13 November, 2017;
originally announced November 2017.
-
Two extensions of the Erdős-Szekeres problem
Authors:
Andreas F. Holmsen,
Hossein Nassajian Mojarrad,
János Pach,
Gábor Tardos
Abstract:
According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\log n}\right)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, w…
▽ More
According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\log n}\right)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term.
A family of $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Toth and by Pach and Toth, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)\le c'(n)\leq 2^{n+O\left(\sqrt{n\log n}\right)}$.
△ Less
Submitted 2 August, 2020; v1 submitted 31 October, 2017;
originally announced October 2017.
-
A Crossing Lemma for Jordan Curves
Authors:
János Pach,
Natan Rubin,
Gábor Tardos
Abstract:
If two Jordan curves in the plane have precisely one point in common, and there they do not properly cross, then the common point is called a {\em touching point}. The main result of this paper is a Crossing Lemma for simple curves: Let $X$ and $T$ stand for the sets of intersection points and touching points, respectively, in a family of $n$ simple curves in the plane, no three of which pass thro…
▽ More
If two Jordan curves in the plane have precisely one point in common, and there they do not properly cross, then the common point is called a {\em touching point}. The main result of this paper is a Crossing Lemma for simple curves: Let $X$ and $T$ stand for the sets of intersection points and touching points, respectively, in a family of $n$ simple curves in the plane, no three of which pass through the same point. If $|T|>cn$, for some fixed constant $c>0$, then we prove that $|X|=Ω(|T|(\log\log(|T|/n))^{1/504})$. In particular, if $|T|/n\rightarrow\infty$, then the number of intersection points is much larger than the number of touching points.
As a corollary, we confirm the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between $n$ pairwise intersecting simple closed (i.e., Jordan) curves in the plane, no three of which pass through the same point, is at least $(1-o(1))n^2$.
△ Less
Submitted 7 August, 2017;
originally announced August 2017.
-
Controlling Lipschitz functions
Authors:
Andrey Kupavskii,
Janos Pach,
Gabor Tardos
Abstract:
Given any positive integers $m$ and $d$, we say the a sequence of points $(x_i)_{i\in I}$ in $\mathbb R^m$ is {\em Lipschitz-$d$-controlling} if one can select suitable values $y_i\; (i\in I)$ such that for every Lipschitz function $f:\mathbb R^m\rightarrow \mathbb R^d$ there exists $i$ with $|f(x_i)-y_i|<1$. We conjecture that for every $m\le d$, a sequence $(x_i)_{i\in I}\subset\mathbb R^m$ is…
▽ More
Given any positive integers $m$ and $d$, we say the a sequence of points $(x_i)_{i\in I}$ in $\mathbb R^m$ is {\em Lipschitz-$d$-controlling} if one can select suitable values $y_i\; (i\in I)$ such that for every Lipschitz function $f:\mathbb R^m\rightarrow \mathbb R^d$ there exists $i$ with $|f(x_i)-y_i|<1$. We conjecture that for every $m\le d$, a sequence $(x_i)_{i\in I}\subset\mathbb R^m$ is $d$-controlling if and only if $$\sup_{n\in\mathbb N}\frac{|\{i\in I\, :\, |x_i|\le n\}|}{n^d}=\infty.$$ We prove that this condition is necessary and a slightly stronger one is already sufficient for the sequence to be $d$-controlling. We also prove the conjecture for $m=1$.
△ Less
Submitted 11 April, 2018; v1 submitted 10 April, 2017;
originally announced April 2017.
-
Disjointness graphs of segments
Authors:
Janos Pach,
Gabor Tardos,
Geza Toth
Abstract:
The {\em disjointness graph} $G=G({\cal S})$ of a set of segments ${\cal S}$ in $R^d$, $d\ge 2,$ is a graph whose vertex set is ${\cal S}$ and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of $G$ satisfies $χ(G)\le(ω(G))^4+(ω(G))^3$, where $ω(G)$ denotes the clique number of $G$. It follows, that $\cal S$ has…
▽ More
The {\em disjointness graph} $G=G({\cal S})$ of a set of segments ${\cal S}$ in $R^d$, $d\ge 2,$ is a graph whose vertex set is ${\cal S}$ and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of $G$ satisfies $χ(G)\le(ω(G))^4+(ω(G))^3$, where $ω(G)$ denotes the clique number of $G$. It follows, that $\cal S$ has $Ω(n^{1/5})$ pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments.
We show that computing $ω(G)$ and $χ(G)$ for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of $G$ in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free ($ω(G)=2$), but whose chromatic numbers are arbitrarily large.
△ Less
Submitted 11 November, 2021; v1 submitted 6 April, 2017;
originally announced April 2017.
-
Improved bounds on the Hadwiger-Debrunner numbers
Authors:
Chaya Keller,
Shakhar Smorodinsky,
Gabor Tardos
Abstract:
Let $HD_d(p,q)$ denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in $\mathbb{R}^d$ which satisfy the $(p,q)$-property ($p \geq q \geq d+1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $HD_d(p,q)$ exists for all $p \geq q \geq d+1$. Specifically, they prove that $HD_d(p,d+1)$ is…
▽ More
Let $HD_d(p,q)$ denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in $\mathbb{R}^d$ which satisfy the $(p,q)$-property ($p \geq q \geq d+1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $HD_d(p,q)$ exists for all $p \geq q \geq d+1$. Specifically, they prove that $HD_d(p,d+1)$ is $\tilde{O}(p^{d^2+d})$.
We present several improved bounds:
(i) For any $q \geq d+1$, $HD_d(p,q) = \tilde{O}(p^{d \left(\frac{q-1}{q-d}\right)})$.
(ii) For $q \geq \log p$, $HD_d(p,q) = \tilde{O}(p+(p/q)^d)$.
(iii) For every $ε> 0$ there exists a $p_0 = p_0(ε)$ such that for every $p \geq p_0$ and for every $q \geq p^{\frac{d-1}{d}+ε}$ we have: $p-q+1 \leq HD_d(p,q) \leq p-q+2$.
The latter is the first near tight estimate of $HD_d(p,q)$ for an extended range of values of $(p,q)$ since the 1957 Hadwiger-Debrunner theorem.
We also prove a $(p,2)$-theorem for families in $\mathbb{R}^2$ with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property.
△ Less
Submitted 1 December, 2016; v1 submitted 13 December, 2015;
originally announced December 2015.
-
Separation with restricted families of sets
Authors:
Zsolt Lángi,
Márton Naszódi,
János Pach,
Gábor Tardos,
Géza Tóth
Abstract:
Given a finite $n$-element set $X$, a family of subsets ${\mathcal F}\subset 2^X$ is said to separate $X$ if any two elements of $X$ are separated by at least one member of $\mathcal F$. It is shown that if $|\mathcal F|>2^{n-1}$, then one can select $\lceil\log n\rceil+1$ members of $\mathcal F$ that separate $X$. If $|\mathcal F|\ge α2^n$ for some $0<α<1/2$, then…
▽ More
Given a finite $n$-element set $X$, a family of subsets ${\mathcal F}\subset 2^X$ is said to separate $X$ if any two elements of $X$ are separated by at least one member of $\mathcal F$. It is shown that if $|\mathcal F|>2^{n-1}$, then one can select $\lceil\log n\rceil+1$ members of $\mathcal F$ that separate $X$. If $|\mathcal F|\ge α2^n$ for some $0<α<1/2$, then $\log n+O(\log\frac1α\log\log\frac1α)$ members of $\mathcal F$ are always sufficient to separate all pairs of elements of $X$ that are separated by some member of $\mathcal F$. This result is generalized to simultaneous separation in several sets. Analogous questions on separation by families of bounded Vapnik-Chervonenkis dimension and separation of point sets in ${\mathbb{R}}^d$ by convex sets are also considered.
△ Less
Submitted 22 August, 2015;
originally announced August 2015.
-
Beyond the Richter-Thomassen Conjecture
Authors:
János Pach,
Natan Rubin,
Gábor Tardos
Abstract:
If two closed Jordan curves in the plane have precisely one point in common, then it is called a {\em touching point}. All other intersection points are called {\em crossing points}. The main result of this paper is a Crossing Lemma for closed curves: In any family of $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing…
▽ More
If two closed Jordan curves in the plane have precisely one point in common, then it is called a {\em touching point}. All other intersection points are called {\em crossing points}. The main result of this paper is a Crossing Lemma for closed curves: In any family of $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least $Ω((\log\log n)^{1/8})$.
As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least $(1-o(1))n^2$.
△ Less
Submitted 7 July, 2015; v1 submitted 30 April, 2015;
originally announced April 2015.
-
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves
Authors:
János Pach,
Natan Rubin,
Gábor Tardos
Abstract:
A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any $n$ simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least $(1-o(1))n^2$.
We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when t…
▽ More
A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any $n$ simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least $(1-o(1))n^2$.
We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class is touching every curve from the second class. (Two curves are said to be touching if they have precisely one point in common, at which they do not properly cross.)
An important ingredient of our proofs is the following statement: Let $S$ be a family of the graphs of $n$ continuous real functions defined on $\mathbb{R}$, no three of which pass through the same point. If there are $nt$ pairs of touching curves in $S$, then the number of crossing points is $Ω(nt\sqrt{\log t/\log\log t})$.
△ Less
Submitted 20 December, 2014;
originally announced December 2014.
-
Cross-intersecting families of vectors
Authors:
János Pach,
Gábor Tardos
Abstract:
Given a sequence of positive integers $p = (p_1, . . ., p_n)$, let $S_p$ denote the family of all sequences of positive integers $x = (x_1,...,x_n)$ such that $x_i \le p_i$ for all $i$. Two families of sequences (or vectors), $A,B \subseteq S_p$, are said to be $r$-cross-intersecting if no matter how we select $x \in A$ and $y \in B$, there are at least $r$ distinct indices $i$ such that…
▽ More
Given a sequence of positive integers $p = (p_1, . . ., p_n)$, let $S_p$ denote the family of all sequences of positive integers $x = (x_1,...,x_n)$ such that $x_i \le p_i$ for all $i$. Two families of sequences (or vectors), $A,B \subseteq S_p$, are said to be $r$-cross-intersecting if no matter how we select $x \in A$ and $y \in B$, there are at least $r$ distinct indices $i$ such that $x_i = y_i$. We determine the maximum value of $|A|\cdot|B|$ over all pairs of $r$- cross-intersecting families and characterize the extremal pairs for $r \ge 1$, provided that $\min p_i >r+1$. The case $\min p_i \le r+1$ is quite different. For this case, we have a conjecture, which we can verify under additional assumptions. Our results generalize and strengthen several previous results by Berge, Frankl, Füredi, Livingston, Moon, and Tokushige, and answers a question of Zhang.
△ Less
Submitted 30 January, 2015; v1 submitted 12 May, 2014;
originally announced May 2014.
-
Erdős-Pyber theorem for hypergraphs and secret sharing
Authors:
László Csirmaz,
Péter Ligeti,
Gábor Tardos
Abstract:
A new, constructive proof with a small explicit constant is given to the Erdős-Pyber theorem which says that the edges of a graph on $n$ vertices can be partitioned into complete bipartite subgraphs so that every vertex is covered at most $O(n/\log n)$ times. The theorem is generalized to uniform hypergraphs. Similar bounds with smaller constant value is provided for fractional partitioning both f…
▽ More
A new, constructive proof with a small explicit constant is given to the Erdős-Pyber theorem which says that the edges of a graph on $n$ vertices can be partitioned into complete bipartite subgraphs so that every vertex is covered at most $O(n/\log n)$ times. The theorem is generalized to uniform hypergraphs. Similar bounds with smaller constant value is provided for fractional partitioning both for graphs and for uniform hypergraphs. We show that these latter constants cannot be improved by more than a factor of 1.89 even for fractional covering by arbitrary complete multipartite subgraphs or subhypergraphs. In the case every vertex of the graph is connected to at least $n-m$ other vertices, we prove the existence of a fractional covering of the edges by complete bipartite graphs such that every vertex is covered at most $O(m/\log m)$ times, with only a slightly worse explicit constant. This result also generalizes to uniform hypergraphs. Our results give new improved bounds on the complexity of graph and uniform hypergraph based secret sharing schemes, and show the limits of the method at the same time.
△ Less
Submitted 20 November, 2013;
originally announced November 2013.
-
The range of a random walk on a comb
Authors:
János Pach,
Gábor Tardos
Abstract:
The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of v, each with probability 1/d(v), where d(v) denotes the degree of v. We answer a question of Csáki, Csörgö, Földes, Révész, and Tusnády by show…
▽ More
The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of v, each with probability 1/d(v), where d(v) denotes the degree of v. We answer a question of Csáki, Csörgö, Földes, Révész, and Tusnády by showing that the expected number of vertices visited by a random walk on the comb after n steps is (1/(2\sqrt{2π})+o(1))\sqrt n\log n. This contradicts a claim of Weiss and Havlin.
△ Less
Submitted 24 September, 2013;
originally announced September 2013.
-
Relations between the local chromatic number and its directed version
Authors:
Gábor Simonyi,
Gábor Tardos,
Ambrus Zsbán
Abstract:
The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here we…
▽ More
The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.
△ Less
Submitted 31 May, 2013;
originally announced May 2013.
-
Regular families of forests, antichains and duality pairs of relational structures
Authors:
Péter L. Erdős,
Dömötör Pálvölgyi,
Claude Tardif,
Gábor Tardos
Abstract:
Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this…
▽ More
Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forest on the left hand side. This work builds on our earlier papers that gave several examples of infinite-finite antichain duality pairs of directed graphs and a complete characterization for caterpillar dualities.
△ Less
Submitted 3 June, 2015; v1 submitted 18 July, 2012;
originally announced July 2012.
-
Caterpillar dualities and regular languages
Authors:
Péter L. Erdős,
Claude Tardif,
Gábor Tardos
Abstract:
We characterize obstruction sets in caterpillar dualities in terms of regular languages, and give a construction of the dual of a regular family of caterpillars. We show that these duals correspond to the constraint satisfaction problems definable by a monadic linear Datalog program with at most one EDB per rule.
We characterize obstruction sets in caterpillar dualities in terms of regular languages, and give a construction of the dual of a regular family of caterpillars. We show that these duals correspond to the constraint satisfaction problems definable by a monadic linear Datalog program with at most one EDB per rule.
△ Less
Submitted 6 March, 2012;
originally announced March 2012.
-
On infinite-finite duality pairs of directed graphs
Authors:
Péter L. Erdős,
Claude Tardif,
Gábor Tardos
Abstract:
The (A,D) duality pairs play crucial role in the theory of general relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In…
▽ More
The (A,D) duality pairs play crucial role in the theory of general relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper (which is the first one of a series) we start the detailed study of the infinite-finite case.
Here we concentrate on directed graphs. We prove some elementary properties of the infinite-finite duality pairs, including lower and upper bounds on the size of D, and show that the elements of A must be equivalent to forests if A is an antichain. Then we construct instructive examples, where the elements of A are paths or trees. Note that the existence of infinite-finite antichain dualities was not previously known.
△ Less
Submitted 6 March, 2012;
originally announced March 2012.
-
Conflict-free coloring of graphs
Authors:
Roman Glebov,
Tibor Szabó,
Gábor Tardos
Abstract:
We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős-Rényi random graph G(n,p) and give the asympto…
▽ More
We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős-Rényi random graph G(n,p) and give the asymptotics for p=omega(1/n). We also show that for p \geq 1/2 the conflict-free chromatic number differs from the domination number by at most 3.
△ Less
Submitted 19 September, 2013; v1 submitted 23 November, 2011;
originally announced November 2011.
-
Construction of locally plane graphs with many edges
Authors:
Gábor Tardos
Abstract:
A graph drawn in the plane with straight-line edges is called a geometric graph. If no path of length at most $k$ in a geometric graph $G$ is self-intersecting we call $G$ $k$-locally plane. The main result of this paper is a construction of $k$-locally plane graphs with a super-linear number of edges. For the proof we develop randomized thinning procedures for edge-colored bipartite (abstract) gr…
▽ More
A graph drawn in the plane with straight-line edges is called a geometric graph. If no path of length at most $k$ in a geometric graph $G$ is self-intersecting we call $G$ $k$-locally plane. The main result of this paper is a construction of $k$-locally plane graphs with a super-linear number of edges. For the proof we develop randomized thinning procedures for edge-colored bipartite (abstract) graphs that can be applied to other problems as well.
△ Less
Submitted 28 October, 2011;
originally announced October 2011.
-
Remarks on a Ramsey theory for trees
Authors:
János Pach,
József Solymosi,
Gábor Tardos
Abstract:
Extending Furstenberg's ergodic theoretic proof for Szemerédi's theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following qualitative result. For every d and k, there exists an integer N such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N such that (1) all vertices at the…
▽ More
Extending Furstenberg's ergodic theoretic proof for Szemerédi's theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following qualitative result. For every d and k, there exists an integer N such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N such that (1) all vertices at the same level in T_d are mapped into vertices at the same level in T_N; (2) if a vertex x of T_d is mapped into a vertex y in T_N, then the two children of x are mapped into descendants of the the two children of y in T_N, respectively; and 3 the levels occupied by this replica form an arithmetic progression. This result and its density versions imply van der Waerden's and Szemerédi's theorems, and laid the foundations of a new Ramsey theory for trees.
Using simple counting arguments and a randomized coloring algorithm called random split, we prove the following related result. Let N=N(d,k) denote the smallest positive integer such that no matter how we color the vertices of a complete binary tree T_N of depth N with k colors, we can find a monochromatic replica of T_d in T_N which satisfies properties (1) and (2) above. Then we have N(d,k)=Θ(dk\log k). We also prove a density version of this result, which, combined with Szemerédi's theorem, provides a very short combinatorial proof of a quantitative version of the Furstenberg-Weiss theorem.
△ Less
Submitted 26 July, 2011;
originally announced July 2011.
-
Local chromatic number of quadrangulations of surfaces
Authors:
Bojan Mohar,
Gábor Simonyi,
Gábor Tardos
Abstract:
The local chromatic number of a graph was introduced by Erdős et al. [4]. In [17] a connection to topological properties of (a box complex of) the graph was established and in [18] it was shown that if a graph is strongly topologically 4-chromatic then its local chromatic number is at least four. As a consequence one obtains a generalization of the following theorem of Youngs: If a quadrangulation…
▽ More
The local chromatic number of a graph was introduced by Erdős et al. [4]. In [17] a connection to topological properties of (a box complex of) the graph was established and in [18] it was shown that if a graph is strongly topologically 4-chromatic then its local chromatic number is at least four. As a consequence one obtains a generalization of the following theorem of Youngs: If a quadrangulation of the projective plane is not bipartite it has chromatic number four. The generalization states that in this case the local chromatic number is also four. Both papers [1] and [13] generalize Youngs's result to arbitrary non-orientable surfaces replacing the condition of the graph being not bipartite by a more technical condition of an odd quadrangulation. This paper investigates when these general results are true for the local chromatic number instead of the chromatic number. Surprisingly, we find out that (unlike in the case of the chromatic number) this depends on the genus of the surface. For the non-orientable surfaces of genus at most four, the local chromatic number of any odd quadrangulation is at least four, but this is not true for non-orientable surfaces of genus 5 or higher. We also prove that face subdivisions of odd quadrangulations and Fisk triangulations of arbitrary surfaces exhibit the same behavior for the local chromatic number as they do for the usual chromatic number.
△ Less
Submitted 1 October, 2010;
originally announced October 2010.
-
The Local Lemma is asymptotically tight for SAT
Authors:
Heidi Gebauer,
Tibor Szabo,
Gabor Tardos
Abstract:
The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. The main theme of our paper is to identify several of these problems, among them a couple of widely studied extremal functions related to certain restricted versions of the k-SAT problem, where the L…
▽ More
The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. The main theme of our paper is to identify several of these problems, among them a couple of widely studied extremal functions related to certain restricted versions of the k-SAT problem, where the Local Lemma does give essentially optimal answers.
As our main contribution, we construct unsatisfiable k-CNF formulas where every clause has k distinct literals and every variable appears in at most (2/e + o(1))*2^k/k clauses. The Lopsided Local Lemma shows that this is asymptotically best possible. The determination of this extremal function is particularly important as it represents the value where the corresponding k-SAT problem exhibits a complexity hardness jump: from having every instance being a YES-instance it becomes NP-hard just by allowing each variable to occur in one more clause.
The construction of our unsatisfiable CNF-formulas is based on the binary tree approach of [16] and thus the constructed formulas are in the class MU(1) of minimal unsatisfiable formulas having one more clauses than variables. The main novelty of our approach here comes in setting up an appropriate continuous approximation of the problem. This leads us to a differential equation, the solution of which we are able to estimate. The asymptotically optimal binary trees are then obtained through a discretization of this solution.
The importance of the binary trees constructed is also underlined by their appearance in many other scenarios. In particular, they give asymptotically precise answers for seemingly unrelated problems like the European Tenure Game introduced by Doerr [9] and a search problem allowing a limited number of consecutive lies.
△ Less
Submitted 19 April, 2016; v1 submitted 3 June, 2010;
originally announced June 2010.
-
On directed local chromatic number, shift graphs, and Borsuk-like graphs
Authors:
Gábor Simonyi,
Gábor Tardos
Abstract:
We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of ``topo…
▽ More
We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of ``topologically t-chromatic'' graphs. We show that this minimum for large enough t-chromatic Schrijver graphs and t-chromatic generalized Mycielski graphs of appropriate parameters is the upper integer part of t/4+1.
△ Less
Submitted 16 June, 2009;
originally announced June 2009.
-
Graph coloring with no large monochromatic components
Authors:
N. Linial,
J. Matousek,
O. Sheffet,
G. Tardos
Abstract:
For a graph G and an integer t we let mcc_t(G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having more than m vertices. Let F be any nontrivial minor-closed family of graphs. We show that \mcc_2(G) = O(n^{2/3}) for any n-vertex graph G \in F. This bound is asymptotically optimal and it is attained for planar graphs…
▽ More
For a graph G and an integer t we let mcc_t(G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having more than m vertices. Let F be any nontrivial minor-closed family of graphs. We show that \mcc_2(G) = O(n^{2/3}) for any n-vertex graph G \in F. This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such F and every fixed t we show that mcc_t(G)=O(n^{2/(t+1)}). On the other hand we have examples of graphs G with no K_{t+3} minor and with mcc_t(G)=Ω(n^{2/(2t-1)}).
It is also interesting to consider graphs of bounded degrees. Haxell, Szabo, and Tardos proved \mcc_2(G) \leq 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with \mcc_2(G)=Ω(n), and more sharply, for every ε>0 there exists c_ε>0 and n-vertex graphs of maximum degree 7, average degree at most 6+εfor all subgraphs, and with mcc_2(G)\ge c_\eps n. For 6-regular graphs it is known only that the maximum order of magnitude of \mcc_2 is between \sqrt n and n.
We also offer a Ramsey-theoretic perspective of the quantity \mcc_t(G).
△ Less
Submitted 12 March, 2007;
originally announced March 2007.
-
Deterministic Random Walks on the Integers
Authors:
Joshua Cooper,
Benjamin Doerr,
Joel Spencer,
Gabor Tardos
Abstract:
Jim Propp's P-machine, also known as the "rotor router model" is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.
We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration,…
▽ More
Jim Propp's P-machine, also known as the "rotor router model" is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.
We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c_1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L), for the L_2 average of a contiguous set of intervals even to O(sqrt{log L}). All these bounds are tight.
△ Less
Submitted 14 February, 2006;
originally announced February 2006.
-
Colorful subgraphs in Kneser-like graphs
Authors:
Gábor Simonyi,
Gábor Tardos
Abstract:
Combining Ky Fan's theorem with ideas of Greene and Matousek we prove a generalization of Dol'nikov's theorem. Using another variant of the Borsuk-Ulam theorem due to Bacon and Tucker, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a general…
▽ More
Combining Ky Fan's theorem with ideas of Greene and Matousek we prove a generalization of Dol'nikov's theorem. Using another variant of the Borsuk-Ulam theorem due to Bacon and Tucker, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F. E. Su.
△ Less
Submitted 1 December, 2005;
originally announced December 2005.
-
Local chromatic number and distinguishing the strength of topological obstructions
Authors:
Gábor Simonyi,
Gábor Tardos,
Siniša T. Vrećica
Abstract:
The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. We show that two specific topological obstructions that have the same implications for the chromatic number have different implications for the local chromatic number. These two obstructions can be formulated in terms of the homo…
▽ More
The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. We show that two specific topological obstructions that have the same implications for the chromatic number have different implications for the local chromatic number. These two obstructions can be formulated in terms of the homomorphism complex Hom(K_2,G) and its suspension, respectively.
These investigations follow the line of research initiated by Matousek and Ziegler who recognized a hierarchy of the different topological expressions that can serve as lower bounds for the chromatic number of a graph.
Our results imply that the local chromatic number of 4-chromatic Kneser, Schrijver, Borsuk, and generalized Mycielski graphs is 4, and more generally, that 2r-chromatic versions of these graphs have local chromatic number at least r+2. This lower bound is tight in several cases by results in an earlier paper of the first two authors.
△ Less
Submitted 19 April, 2007; v1 submitted 22 February, 2005;
originally announced February 2005.
-
Local chromatic number, Ky Fan's theorem, and circular colorings
Authors:
Gabor Simonyi,
Gabor Tardos
Abstract:
The local chromatic number of a graph was introduced by Erdos et al. in 1986. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their gener…
▽ More
The local chromatic number of a graph was introduced by Erdos et al. in 1986. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs.
We use an old topological result of Ky Fan which generalizes the Borsuk-Ulam theorem. It implies the existence of a multicolored copy of the balanced complete bipartite graph on t points in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan.) This yields a lower bound of t/2+1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases.
As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme.
△ Less
Submitted 26 November, 2004; v1 submitted 6 July, 2004;
originally announced July 2004.
-
Waiting for a bat to fly by (in polynomial time)
Authors:
Itai Benjamini,
Gady Kozma,
Laszlo Lovasz,
Dan Romik,
Gabor Tardos
Abstract:
We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the eigenvalues can be recovered under fairly general conditions, e.g. when the graph has a node-transitive automorphism group. The main result is that by obs…
▽ More
We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the eigenvalues can be recovered under fairly general conditions, e.g. when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.
△ Less
Submitted 28 October, 2003;
originally announced October 2003.
-
Covering lattice points by subspaces
Authors:
Imre Bárány,
Gergely Harcos,
János Pach,
Gábor Tardos
Abstract:
We find tight estimates for the minimum number of proper subspaces needed to cover all lattice points in an n-dimensional convex body symmetric about the origin. We also find the order of magnitude of the number of (n-1)-dimensional subspaces induced by the lattice points in a large n-dimensional ball centered at the origin.
We find tight estimates for the minimum number of proper subspaces needed to cover all lattice points in an n-dimensional convex body symmetric about the origin. We also find the order of magnitude of the number of (n-1)-dimensional subspaces induced by the lattice points in a large n-dimensional ball centered at the origin.
△ Less
Submitted 2 March, 2001; v1 submitted 4 February, 2001;
originally announced February 2001.
-
On quasi-transitive amenable graphs
Authors:
Gabor Elek,
Gabor Tardos
Abstract:
The existence of nonconstant harmonic Dirichlet functions on a Cayley graph of a discrete group is equivalent to the nonvanishing of the first L2-cohomology of the given group. It was first proven by Cheeger and Gromov that such functions do not exists on the Cayley-graph of an amenable group. The result was extended using Foster's averaging formula to transitive amenable graphs by Medolla and S…
▽ More
The existence of nonconstant harmonic Dirichlet functions on a Cayley graph of a discrete group is equivalent to the nonvanishing of the first L2-cohomology of the given group. It was first proven by Cheeger and Gromov that such functions do not exists on the Cayley-graph of an amenable group. The result was extended using Foster's averaging formula to transitive amenable graphs by Medolla and Soardi. In this paper we extend this result further for amenable graphs which are transitive in the category of quasi-isometries. Such graphs are usually not quasi-isometric to transitive graphs. The extension includes nets of amenable unimodular Lie-groups and geometrically amenable homogeneous spaces.
△ Less
Submitted 23 June, 1998;
originally announced June 1998.
