We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension d. One of our results is that if an intersection graph of n spheres in ℝ^d has m edges, then it contains a balanced separator of size O_d(m^{1/d}n^{1-2/d}). This bound is best possible in terms of the parameters involved. The same result holds if the balls and spheres are replaced by fat convex bodies and their boundaries.

We prove that if a graph can be drawn in the plane such that each edge crosses at most k other edges, then it can be redrawn so that each edge participates in at most k³+O(k²) crossings. This improves the previous exponential bound that follows from a result of Schaefer and Štefankovič and answers a question of Ackerman and Schaefer.

We prove a far-reaching strengthening of Szemerédi's regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such a graph can be partitioned into a bounded number of parts of roughly the same size such that almost all bipartite graphs between different pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every $n$-vertex simple topological graph with no $k$ pairwise disjoint edges has at most $n(\log n)^{O(\log k)}$ edges.

For positive integersn, r, swithr>s, the setcoloring Ramsey numberR(n; r, s) is the minimumNsuch that if every edge of the complete graphKNreceives a set ofscolors from a palette ofrcolors, then there is a subset ofnvertices where all of the edges between them receive a common color. Ifnis fixed ands/ris less than and bounded away from 1 - 1/n-1, thenR(n; r, s) is known to grow exponentially in r, while ifs/ris greater than and bounded away from 1 - 1/n-1, thenR(n; r, s) is bounded. Here we prove bounds forR(n; r, s) in the intermediate range wheres/ris close to 1 - 1/n-1 by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

An r-quasiplanar graph is a graph drawn in the plane with no r pairwise crossing edges. Let s≥3 be an integer and r=2s. We prove that there is a constant C such that every r-quasiplanar graph with n≥r vertices has at most nCs−1logn2s−4 edges. A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every ϵ>0, there exists δ>0 such that every string graph with n vertices whose chromatic number is at least nϵ contains a clique of size at least nδ. A clique of this size or a coloring using fewer than nϵ colors can be found by a polynomial time algorithm in terms of the size of the geometric representation of the set of strings. In the process, we use, generalize, and strengthen previous results of Lee, Tomon, and others. All of our theorems are related to geometric variants of the following classical graph-theoretic problem of Erdős, Gallai, and Rogers. Given a Kr-free graph on n vertices and an integer s

Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

We present two short proofs giving the best known asymptotic lower bound for the maximum element in a set of $n$ positive integers with distinct subset sums.

Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \le k!(k-1)^{n-k}$ for all connected graphs $G$ on $n$ vertices with chromatic number $k\geq 4$. In this paper, we study the same problem with the additional constraint that $G$ is $\ell$-connected. For $2$-connected graphs $G$, we prove a tight bound $P_G(k) \le (k-1)!((k-1)^{n-k+1} + (-1)^{n-k})$ and show that equality is only achieved if $G$ is a $k$-clique with an ear attached. For $\ell \ge 3$, we prove an asymptotically tight upper bound $ P_G(k) \le k!(k-1)^{n-\ell - k + 1} + O((k-2)^n)$ and provide a matching lower bound construction. For the ranges $k \geq \ell$ or $\ell \geq (k-2)(k-1)+1$ we further find the unique graph maximizing $P_G(k)$. We also consider generalizing $\ell$-connected graphs to connected graphs with minimum degree $\delta$.

We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure---the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a $c$-closed graph, where for every pair of vertices $u,v$ with at least $c$ common neighbors, $u$ and $v$ are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to $c$ on $c$-closed graphs. Our results carry over to weakly $c$-closed graphs, which only require a vertex deletion ordering that avoids pairs of nonadjacent vertices with $c$ common neighbors. Numerical experiments show that well-studied social networks with thousands of vertices tend to be weakly $c$-closed for modest values of $c$.

A celebrated result of Mantel shows that every graph on n vertices with $\lfloor n^2/4 \rfloor + 1$ edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least $\lfloor n/2 \rfloor$ triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with Erdös, says that any such graph must have an edge which is contained in at least $n/6$ triangles. Following Mubayi, we study the interplay between these two results, that is, between the number of triangles in such graphs and their book number, the largest number of triangles sharing an edge. Among other results, Mubayi showed that for any $1/6 \leq \beta < 1/4$ there is $\gamma > 0$ such that any graph on $n$ vertices with at least $\lfloor n^2/4\rfloor + 1$ edges and book number at most $\beta n$ contains at least $(\gamma -o(1))n^3$ triangles. He also asked for a more precise estimate for $\gamma$ in terms of $\beta$. We make a conjecture about this dependency and prove this conjecture for $\beta = 1/6$ and for $0.2495 \leq \beta < 1/4$, thereby answering Mubayi's question in these ranges.

How many cliques can a graph on $n$ vertices have with a forbidden substructure? Extremal problems of this sort have been studied for a long time. This paper studies the maximum possible number of cliques in a graph on $n$ vertices with a forbidden clique subdivision or immersion. We prove for $t$ sufficiently large that every graph on $n \geq t$ vertices with no $K_t$-immersion has at most $n2^{t+\log_2^2 t}$ cliques, which is sharp apart from the $2^{O(\log^2 t)}$ factor. We also prove that the maximum number of cliques in an $n$-vertex graph with no $K_t$-subdivision is at most $2^{1.817t }n$ for sufficiently large $t$. This improves on the best known exponential constant by Lee and Oum. We conjecture that the optimal bound is $3^{2t/3 +o(t)}n$, as we proved for minors in place of subdivision in earlier work.

We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.

Let $$\ell _m$$ be a sequence of m points on a line with consecutive points of distance one. For every natural number n, we prove the existence of a red/blue-coloring of $${\mathbb {E}}^n$$ containing no red copy of $$\ell _2$$ and no blue copy of $$\ell _m$$ for any $$m \ge 2^{cn}$$ . This is best possible up to the constant c in the exponent. It also answers a question of Erdős et al. (J Comb Theory Ser A 14:341–363, 1973). They asked if, for every natural number n, there is a set $$K \subset {\mathbb {E}}^1$$ and a red/blue-coloring of $${\mathbb {E}}^n$$ containing no red copy of $$\ell _2$$ and no blue copy of K.

The Vapnik–Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $$e^{(\log n)^{1 - o(1)}}$$ . The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, $$e^{c\sqrt{\log n}}$$ , due to Erdős and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdős–Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $$e^{\Omega (\log n)}$$ . Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász–Szegedy and Alon–Fischer–Newman, which is called the “ultra-strong regularity lemma” for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $$(1/\varepsilon )^{O(d)}$$ , improving the original bound of $$(1/\varepsilon )^{O(d^2)}$$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $$O(n^k)$$ -time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey–Turán numbers for graphs with bounded VC-dimension.

Let p be a fixed prime. A triangle in is an ordered triple (x, y, z) of points satisfying x+y+ z = 0. Let Green proved an arithmetic triangle removal lemma which says that for every ∊ > 0 and prime p, there is a δ > 0 such that if and the number of triangles in X × Y × Z is at most δN2, then we can delete ∊N elements from X, Y, and Z and remove all triangles. Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. Despite considerable attention, prior to this paper, the best known bound, due to the first author, showed that 1/δ can be taken to be an exponential tower of twos of height logarithmic in 1/∊. We solve Green's problem, proving an essentially tight bound for Green's arithmetic triangle removal lemma in We show that a polynomial bound holds, and further determine the best possible exponent. Namely, there is a computable number Cp such that we may take and we must have In particular, C2 = 1 + 1/(5/3 - log2 3) ≈ 13.239, and C3 = 1 + 1/c3 with and which gives C3 ≈ 13.901. The proof uses Kleinberg, Sawin, and Speyer's essentially sharp bound on multicolored sum- free sets, which builds on the recent breakthrough on the cap set problem by Croot-Lev-Pach, and the subsequent work by Ellenberg-Gijswijt, Blasiak-Church-Cohn-Grochow- Naslund-Sawin-Umans, and Alon.

The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are ε-far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with “constant” query complexity, depending only on ε and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques are often enormous and impractical. It remains a major open problem if better bounds hold. Hoppen, Kohayakawa, Moreira, and Sampaio conjectured and Klimosová and Král’ proved that hereditary permutation properties are strongly testable, i.e., can be tested with respect to Kendall's tau distance. The query complexity bound coming from this proof is huge. Even for testing a single forbidden subpermutation it is of Ackermann-type in 1 /ε. We give a new proof which gives a polynomial bound in 1/ε for testing a single forbidden subpermutation. Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1/ε query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden sub- permutation for the property. Finally, we show that several different permutation metrics of interest are related to the rectangular distance, yielding similar results for testing with respect to these metrics.

Many problems in discrete and computational geometry can be viewed as finding patterns in graphs or hypergraphs which arise from geometry or algebra. Famous Ramsey, Turán, and Szemerédi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra. We further discuss whether the stronger results in these settings are due to geometric, algebraic, combinatorial, or topological properties of the graphs.

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in $k$, on the best constant $\delta>0$ such that the vertex classes $P_1,\ldots,P_k$ of every $k$-partite $k$-uniform semialgebraic hypergraph $H=(P_1\cup\cdots\cup P_k, E)$ with $|E|\ge\varepsilon\Pi_{j=1}^k|P_i|$ have, for $1 \leq i \leq k$, $\delta|P_i|$-element subsets $P'_i\subseteq P_i$ satisfying $P_{1}'\times\cdots\times P_{k}'\subseteq E$. The best previously known lower bound on $\delta$ due to Bukh and Hubard decreased triple exponentially fast in $k$. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets $P_1,\ldots,P_k\subset \mathbb{R}^d\; (k>d)$ have, for $1 \leq i \leq k$, subsets $P'_i$ of size at least $2^{-O(d^3k\log k)}|P_i|$ with the property that every $k$-tuple formed by taking one point from each $P'_i$ has the same order type. We also improve a result of Fox, Gromov, Lafforgue, Naor, and Pach, who established a regularity lemma for semialgebraic $k$-uniform hypergraphs of bounded complexity, showing that for each $\varepsilon>0$ the vertex set can be equitably partitioned into a bounded number of parts (in terms of $\varepsilon$ and the complexity) so that all but an $\varepsilon$-fraction of the $k$-tuples of parts are homogeneous. Here, we prove that the number of parts can be taken to be polynomial in $1/\varepsilon$. Our improved regularity lemma can be applied to geometric problems and to the following general question on property testing: is it possible to decide, with query complexity polynomial in the reciprocal of the approximation parameter, whether a hypergraph has a given hereditary property? We give an affirmative answer for testing typical hereditary properties for semialgebraic hypergraphs of bounded complexity.

A k-uniform semi-algebraic hypergraph H is a pair (P, E), where P is a subset of ℝd and E is a collection of k-tuples {p1, …, pk} ⊂ P such that (p1, …, pk) ∊ E if and only if the kd coordinates of the pi-s satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semi-algebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following “polynomial regularity lemma”: For any 0 < ε < 1/2, the vertex set of every k-uniform semi-algebraic hypergraph H = (P, E) can be partitioned into at most (1/ε)c parts P1, P2, …, as equal as possible, such that all but at most an ε-fraction of the k-tuples of parts (Pi1, …, Pik) are homogeneous in the sense that either every k-tuple (pi1, …, pik) ∊ Pi1 × … × Pik belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant δ > 0 such that the vertex classes P1, …, Pk of every k-partite k-uniform semi-algebraic hypergraph H = (P1 ∪ … ∪ Pk, E) with |E| ≥ εΠkj=1|Pi| have, for 1 ≤ i ≤ k, δ|Pi|-element subsets P′i ⊆ Pi satisfying P′1 × … × P′k ⊆ E. The best previously known lower bound on δ due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets P1, …, Pk ⊂ ℝd (k > d) have for 1 ≤ i ≤ k subsets P′i of size at least 2−O(d3k log k)|Pi| with the property that every k-tuple formed by taking one point from each P′i has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property , there is a randomized algorithm with query complexity ) to determine (with probability at least .99) whether a k-uniform semi-algebraic hypergraph H = (P,E) with constant description complexity is ε-near to having property , that is, whether one can change at most ε|P|k hyperedges of H in order to obtain a hypergraph that has the property. The testability of such properties for general k-uniform hypergraphs was first shown by Alon and Shapira (for graphs) and by Rödl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function.

Suppose that $a$ and $d$ are positive integers with $a \geq 2$. Let $h_{a,d}(n)$ be the largest integer $t$ such that any set of $n$ points in $\mathbb{R}^d$ contains a subset of $t$ points for which all the nonzero volumes of the ${t \choose a}$ subsets of order $a$ are distinct. Beginning with Erdös in 1957, the function $h_{2,d}(n)$ has been closely studied and is known to be at least a power of $n$. We improve the best known bound for $h_{2,d}(n)$ and show that $h_{a,d}(n)$ is at least a power of $n$ for all $a$ and $d$.

For natural numbers d and t there exists a positive C such that if F is a family of nC semi-algebraic sets in Rd of description complexity at most t, then there is a subset F' of F of size $n$ such that either every pair of elements in F' intersect or the elements of F' are pairwise disjoint. This result, which also holds if the intersection relation is replaced by any semi-algebraic relation of bounded description complexity, was proved by Alon, Pach, Pinchasi, Radoicic, and Sharir and improves on a bound of 4n for the family F which follows from a straightforward application of Ramsey's theorem. We extend this semi-algebraic version of Ramsey's theorem to k-ary relations and give matching upper and lower bounds for the corresponding Ramsey function, showing that it grows as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential. We apply this result to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.

A graph drawn in the plane is called $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. It has been conjectured for a long time that for every fixed $k$, the maximum number of edges of a $k$-quasi-planar graph with $n$ vertices is $O(n)$. The best known upper bound is $n(\log n)^{O(\log k)}$. In the present paper, we improve this bound to $(n\log n )2^{\alpha(n)^{c_k}}$ in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here $\alpha(n)$ denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for $k$-quasi-planar graphs in which every edge is drawn as an $x$-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most $2^{ck^6}n\log n$.

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,<), its incomparability graph is the graph with vertex set P, in which two elements of P are adjacent if and only if they are incomparable.

The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∊ (0, 1] such that no matter how we map the vertices of H into ℝd, there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. In [18], motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence {Hn}n=1∞ of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree, for which infn ≥1 c(Hn) > 0. Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → • ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any d and any ε > 0, there exists K = K(ε,d) ≥ d + 1 satisfying the following condition. For any k ≥ K, for any point q ∊ ℝd and for any finite Borel measure μ on ℝd with respect to which every hyperplane has measure 0, there is a partition ℝ = A1 U … U Ak into k measurable parts of equal measure such that all but at most an ε-fraction of the (d + 1)-tuples Ai1, …, Aid+1 have the property that either all simplices with one vertex in each Aij contain q or none of these simplices contain q.

Computing the maximum number of disjoint elements in a collection C of geometric objects is a classical problem in computational geometry with applications ranging from frequency assignment in cellular networks to map labeling in computational cartography. The problem is equivalent to finding the independence number, α(GC), of the intersection graph GC of C, obtained by connecting two elements of C with an edge if and only if their intersection is nonempty. This is known to be an NP-hard task even for systems of segments in the plane with at most two different slopes. The best known polynomial time approximation algorithm for systems of arbitrary segments is due to Agarwal and Mustafa, and returns in the worst case an n1/2 + o(1)-approximation for α. Using extensions of the Lipton-Tarjan separator theorem, we improve this result and present, for every ε > 0, a polynomial time algorithm for computing α(GC) with approximation ratio at most nε. In contrast, for general graphs, for any ε > 0 it is NP-hard to approximate the independence number within a factor of n1–ε. We also give a subexponential time exact algorithm for computing the independence number of intersection graphs of arcwise connected sets in the plane.

Let G be a graph with n vertices and independence number $\alpha$. Hadwiger's conjecture implies that G contains a clique minor of order at least $n/\alpha$. In 1982, Duchet and Meyniel proved that this bound holds within a factor 2. Our main result gives the first improvement on their bound by an absolute constant factor. We show that G contains a clique minor of order larger than $.504n/\alpha$. We also prove related results giving lower bounds on the order of the largest clique minor.

A topological graph is a graph drawn in the plane with vertices represented by points and edges as arcs connecting its vertices. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that for a fixed constant k, every n-vertex topological graph with no k-grid has O(n) edges.

The intersection graph of a collection C of sets is a graph on the vertex set C, in which C1,C2 ∈ C are joined by an edge if and only if C1 ∩ C2 ≠ Ø. Erdös conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every Kk-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ct log n/log k)c log k, where c is an absolute constant and ct only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.

In this short note we prove that there is a constant c such that every k-edge-coloring of the complete graph $K_n$ with $n \geq 2^{ck}$ contains a $K_4$ whose edges receive at most two colors. This improves on a result of Kostochka and Mubayi, and is the first exponential bound for this problem.