BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Andrew Suk

Andrew Suk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COComputational GeometryDiscrete Mathematicsmath.MG

Catalog footprint

What is connected

33works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

33 published item(s)

preprint2026arXiv

Enumeration of intersection graphs of $x$-monotone curves

A curve in the plane is $x$-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct $2^{Ω(n^{4/3})}$ families, each consisting of $n$ labelled $x$-monotone pseudo-segments such that their intersection graphs are different. On the other hand, we show that the number of such intersection graphs is at most $2^{O(n^{4/3}\log^2n)}$. Our proof uses a new upper bound on the number of set systems of size $m$ on a ground set of size $n$, with VC-dimension at most $d$. Much better upper bounds are obtained if we only count bipartite intersection graphs, or, in general, intersection graphs with bounded chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

On higher dimensional point sets in general position

A finite point set in $\mathbb{R}^d$ is in general position if no $d + 1$ points lie on a common hyperplane. Let $α_d(N)$ be the largest integer such that any set of $N$ points in $\mathbb{R}^d$, with no $d + 2$ members on a common hyperplane, contains a subset of size $α_d(N)$ in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that $α_2(N) < N^{5/6 + o(1)}$. In this paper, we also use the container method to obtain new upper bounds for $α_d(N)$ when $d \geq 3$. More precisely, we show that if $d$ is odd, then $α_d(N) < N^{\frac{1}{2} + \frac{1}{2d} + o(1)}$, and if $d$ is even, we have $α_d(N) < N^{\frac{1}{2} + \frac{1}{d-1} + o(1)}$. We also study the classical problem of determining $a(d,k,n)$, the maximum number of points selected from the grid $[n]^d$ such that no $k + 2$ members lie on a $k$-flat, and improve the previously best known bound for $a(d,k,n)$, due to Lefmann in 2008, by a polynomial factor when $k$ = 2 or 3 (mod 4).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A note on visible islands

Given a finite point set $P$ in the plane, a subset $S \subseteq P$ is called an island in $P$ if $conv(S) \cap P = S$. We say that $S\subset P$ is a visible island if the points in $S$ are pairwise visible and $S$ is an island in $P$. The famous Big-line Big-clique Conjecture states that for any $k \geq 3$ and $\ell \geq 4$, there is an integer $n = n(k,\ell)$, such that every finite set of at least $n$ points in the plane contains $\ell$ collinear points or $k$ pairwise visible points. In this paper, we show that this conjecture is false for visible islands, by replacing each point in a Horton set by a triple of collinear points. Hence, there are arbitrarily large finite point sets in the plane with no 4 collinear members and no visible island of size $13$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the number of edges of separated multigraphs

We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^2\log n)$, provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in $G$ contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, if $G$ has $e \geq 4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $Ω\left(\frac{e^3}{n^2\log(e/n)}\right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Set-coloring Ramsey numbers via codes

For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Unavoidable patterns in complete simple topological graphs

We show that every complete $n$-vertex simple topological graph contains a topological subgraph on at least $(\log n)^{1/4 - o(1)}$ vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound $Ω(\log^{1/8}n)$ obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete $n$-vertex simple topological graph contains a plane path of length at least $(\log n)^{1 -o(1)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A note on the Erdős-Hajnal hypergraph Ramsey problem

We show that there is an absolute constant $c>0$ such that the following holds. For every $n > 1$, there is a 5-uniform hypergraph on at least $2^{2^{cn^{1/4}}}$ vertices with independence number at most $n$, where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for $k$-uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A positive fraction mutually avoiding sets theorem

Two sets $A$ and $B$ of points in the plane are \emph{mutually avoiding} if no line generated by any two points in $A$ intersects the convex hull of $B$, and vice versa. In 1994, Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman showed that every set of $n$ points in the plane in general position contains a pair of mutually avoiding sets each of size at least $\sqrt{n/12}$. As a corollary, their result implies that for every set of $n$ points in the plane in general position one can find at least $\sqrt{n/12}$ segments, each joining two of the points, such that these segments are pairwise crossing. In this note, we prove a fractional version of their theorem: for every $k > 0$ there is a constant $\varepsilon_k > 0$ such that any sufficiently large point set $P$ in the plane contains $2k$ subsets $A_1,\ldots, A_{k},B_1,\ldots, B_k$, each of size at least $\varepsilon_k|P|$, such that every pair of sets $A = \{a_1,\ldots, a_k\}$ and $B = \{b_1,\ldots, b_k\}$, with $a_i \in A_i$ and $b_i \in B_i$, are mutually avoiding. Moreover, we show that $\varepsilon_k = Ω(1/k^4)$. Similar results are obtained in higher dimensions

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Cliques with many colors in triple systems

Erdős and Hajnal constructed a 4-coloring of the triples of an $N$-element set such that every $n$-element subset contains 2 triples with distinct colors, and $N$ is double exponential in $n$. Conlon, Fox and Rödl asked whether there is some integer $q\ge 3$ and a $q$-coloring of the triples of an $N$-element set such that every $n$-element subset has 3 triples with distinct colors, and $N$ is double exponential in $n$. We make the first nontrivial progress on this problem by providing a $q$-coloring with this property for all $q\geq 9$, where $N$ is exponential in $n^{2+cq}$ and $c>0$ is an absolute constant.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hasse diagrams with large chromatic number

For every positive integer $n$, we construct a Hasse diagram with $n$ vertices and chromatic number $Ω(n^{1/4})$, which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number $Θ(\log n)$. In addition, if we also require that our Hasse diagram has girth at least $k\geq 5$, we can achieve a chromatic number of at least $n^{\frac{1}{2k-3}+o(1)}$. These results have the following surprising geometric consequence. They imply the existence of a family $\mathcal{C}$ of $n$ curves in the plane such that the disjointness graph $G$ of $\mathcal{C}$ is triangle-free (or have high girth), but the chromatic number of $G$ is polynomial in $n$. Again, the previously known best construction, due to Pach, Tardos and Tóth, had only logarithmic chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On grids in point-line arrangements in the plane

The famous Szemerédi-Trotter theorem states that any arrangement of $n$ points and $n$ lines in the plane determines $O(n^{4/3})$ incidences, and this bound is tight. In this paper, we prove the following Turán-type result for point-line incidence. Let $\mathcal{L}_1$ and $\mathcal{L}_2$ be two sets of $t$ lines in the plane and let $P=\{\ell_1 \cap \ell_2 : \ell_1 \in \mathcal{L}_1, \ell_2 \in \mathcal{L}_2\}$ be the set of intersection points between $\mathcal{L}_1$ and $\mathcal{L}_2$. We say that $(P, \mathcal{L}_1 \cup \mathcal{L}_2)$ forms a \emph{natural $t\times t$ grid} if $|P| =t^2$, and $conv(P)$ does not contain the intersection point of some two lines in $\mathcal{L}_i,$ for $i = 1,2.$ For fixed $t > 1$, we show that any arrangement of $n$ points and $n$ lines in the plane that does not contain a natural $t\times t$ grid determines $O(n^{\frac{4}{3}- \varepsilon})$ incidences, where $\varepsilon = \varepsilon(t)$. We also provide a construction of $n$ points and $n$ lines in the plane that does not contain a natural $2 \times 2$ grid and determines at least $Ω({n^{1+\frac{1}{14}}})$ incidences.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing

Fox, Gromov, Lafforgue, Naor, and Pach proved a regularity lemma for semi-algebraic $k$-uniform hypergraphs of bounded complexity, showing that for each $ε>0$ the vertex set can be equitably partitioned into a bounded number of parts (in terms of $ε$ and the complexity) so that all but an $ε$-fraction of the $k$-tuples of parts are homogeneous. We prove that the number of parts can be taken to be polynomial in $1/ε$. 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 semi-algebraic hypergraphs of bounded complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximating the rectilinear crossing number

A straight-line drawing of a graph $G$ is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph $G$, $\overline{cr}(G)$, is the minimum number of crossing edges in any straight-line drawing of $G$. Determining or estimating $\overline{cr}(G)$ appears to be a difficult problem, and deciding if $\overline{cr}(G)\leq k$ is known to be NP-hard. In fact, the asymptotic behavior of $\overline{cr}(K_n)$ is still unknown. In this paper, we present a deterministic $n^{2+o(1)}$-time algorithm that finds a straight-line drawing of any $n$-vertex graph $G$ with $\overline{cr}(G) + o(n^4)$ crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense $n$-vertex graph $G$, one can efficiently find a straight-line drawing of $G$ with $(1 + o(1))\overline{cr}(G)$ crossing edges.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New bounds on the maximum number of edges in $k$-quasi-planar graphs

A topological graph is $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed $k$, the maximum number of edges in a $k$-quasi-planar graph on $n$ vertices is $O(n)$. Fox and Pach showed that every $k$-quasi-planar graph with $n$ vertices has at most $n(\log n)^{O(\log k)}$ edges. We improve this upper bound to $2^{α(n)^c}n\log n$, where $α(n)$ denotes the inverse Ackermann function and $c$ depends only on $k$, for $k$-quasi-planar graphs in which any two edges intersect in a bounded number of points. We also show that every $k$-quasi-planar graph with $n$ vertices in which any two edges have at most one point in common has at most $O(n\log n)$ edges. This improves the previously known upper bound of $2^{α(n)^c}n\log n$ obtained by Fox, Pach, and Suk.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Erdos-Szekeres convex polygon problem

Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdos-Szekeres conjecture by showing that $ES(n) =2^{n +o(n)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Erdős-Hajnal hypergraph Ramsey problem

Given integers $2\le t \le k+1 \le n$, let $g_k(t,n)$ be the minimum $N$ such that every red/blue coloring of the $k$-subsets of $\{1, \ldots, N\}$ yields either a $(k+1)$-set containing $t$ red $k$-subsets, or an $n$-set with all of its $k$-subsets blue. Erdős and Hajnal proved in 1972 that for fixed $2\le t \le k$, there are positive constants $c_1$ and $c_2$ such that $$ 2^{c_1 n} < g_k(t, n) < twr_{t-1} (n^{c_2}),$$ where $twr_{t-1}$ is a tower of 2's of height $t-2$. They conjectured that the tower growth rate in the upper bound is correct. Despite decades of work on closely related and special cases of this problem by many researchers, there have been no improvements of the lower bound for $2<t<k$. Here we settle the Erdős-Hajnal conjecture in almost all cases in a strong form, by determining the correct tower growth rate, and in half of the cases we also determine the correct power of $n$ within the tower. Specifically, we prove that if $2<t<k-1$ and $k - t$ is even, then $$g_k(t, n) = twr_{t-1} (n^{k-t+1 + o(1)}).$$ Similar results are proved for $k - t$ odd.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A semi-algebraic version of Zarankiewicz's problem

A bipartite graph $G$ is semi-algebraic in $\mathbb{R}^d$ if its vertices are represented by point sets $P,Q \subset \mathbb{R}^d$ and its edges are defined as pairs of points $(p,q) \in P\times Q$ that satisfy a Boolean combination of a fixed number of polynomial equations and inequalities in $2d$ coordinates. We show that for fixed $k$, the maximum number of edges in a $K_{k,k}$-free semi-algebraic bipartite graph $G = (P,Q,E)$ in $\mathbb{R}^2$ with $|P| = m$ and $|Q| = n$ is at most $O((mn)^{2/3} + m + n)$, and this bound is tight. In dimensions $d \geq 3$, we show that all such semi-algebraic graphs have at most $C\left((mn)^{ \frac{d}{d+1} + \varepsilon} + m + n\right)$ edges, where here $\varepsilon$ is an arbitrarily small constant and $C = C(d,k,t,\varepsilon)$. This result is a far-reaching generalization of the classical Szemerédi-Trotter incidence theorem. The proof combines tools from several fields: VC-dimension and shatter functions, polynomial partitioning, and Hilbert polynomials. We also present various applications of our theorem. For example, a general point-variety incidence bound in $\mathbb{R}^d$, an improved bound for a $d$-dimensional variant of the Erdős unit distances problem, and more.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Disjoint edges in topological graphs and the tangled-thrackle conjecture

It is shown that for a constant $t\in \mathbb{N}$, every simple topological graph on $n$ vertices has $O(n)$ edges if it has no two sets of $t$ edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is $K_{t,t}$-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoičić, and Tóth: Every $n$-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most $O(n)$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Off-diagonal hypergraph Ramsey numbers

The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-subsets of $\{1, \ldots, N\}$ contains a red set of size $s$ or a blue set of size $n$, where a set is red (blue) if all of its $k$-subsets are red (blue). A $k$-uniform \emph{tight path} of size $s$, denoted by $P_{s}$, is a set of $s$ vertices $v_1 < \cdots < v_{s}$ in $\mathbb{Z}$, and all $s-k+1$ edges of the form $\{v_j,v_{j+1},\ldots, v_{j + k -1}\}$. Let $r_k(P_s, n)$ be the minimum $N$ such that every red-blue coloring of the $k$-subsets of $\{1, \ldots, N\}$ results in a red $P_{s}$ or a blue set of size $n$. The problem of estimating both $r_k(s,n)$ and $r_k(P_s, n)$ for $k=2$ goes back to the seminal work of Erdos and Szekeres from 1935, while the case $k\ge 3$ was first investigated by Erdos and Rado in 1952. In this paper, we deduce a quantitative relationship between multicolor variants of $r_k(P_s, n)$ and $r_k(n, n)$. This yields several consequences including the following: (1) We determine the correct tower growth rate for both $r_k(s,n)$ and $r_k(P_s, n)$ for $s \ge k+3$. The question of determining the tower growth rate of $r_k(s,n)$ for all $s \ge k+1$ was posed by Erdos and Hajnal in 1972. (2) We show that determining the tower growth rate of $r_k(P_{k+1}, n)$ is equivalent to determining the tower growth rate of $r_k(n,n)$, which is a notorious conjecture of Erdos, Hajnal and Rado from 1965 that remains open. Some related off-diagonal hypergraph Ramsey problems are also explored.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Semi-algebraic Ramsey numbers

Given a finite point set $P \subset \mathbb{R}^d$, a $k$-ary semi-algebraic relation $E$ on $P$ is the set of $k$-tuples of points in $P$, which is determined by a finite number of polynomial equations and inequalities in $kd$ real variables. The description complexity of such a relation is at most $t$ if the number of polynomials and their degrees are all bounded by $t$. The Ramsey number $R^{d,t}_k(s,n)$ is the minimum $N$ such that any $N$-element point set $P$ in $\mathbb{R}^d$ equipped with a $k$-ary semi-algebraic relation $E$, such that $E$ has complexity at most $t$, contains $s$ members such that every $k$-tuple induced by them is in $E$, or $n$ members such that every $k$-tuple induced by them is not in $E$. We give a new upper bound for $R^{d,t}_k(s,n)$ for $k\geq 3$ and $s$ fixed. In particular, we show that for fixed integers $d,t,s$, $R^{d,t}_3(s,n) \leq 2^{n^{o(1)}},$ establishing a subexponential upper bound on $R^{d,t}_3(s,n)$. This improves the previous bound of $2^{n^C}$ due to Conlon, Fox, Pach, Sudakov, and Suk, where $C$ is a very large constant depending on $d,t,$ and $s$. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in $\mathbb{R}^d$. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Ramsey-type result for geometric l-hypergraphs

Let n \geq l \geq 2 and q \geq 2. We consider the minimum N such that whenever we have N points in the plane in general position and the l-subsets of these points are colored with q colors, there is a subset S of n points all of whose l-subsets have the same color and furthermore S is in convex position. This combines two classical areas of intense study over the last 75 years: the Ramsey problem for hypergraphs and the Erd\H os-Szekeres theorem on convex configurations in the plane. For the special case l = 2, we establish a single exponential bound on the minimum N, such that every complete $N$-vertex geometric graph whose edges are colored with q colors, yields a monochromatic convex geometric graph on n vertices. For fixed l \geq 2 and q \geq 4, our results determine the correct exponential tower growth rate for N as a function of n, similar to the usual hypergraph Ramsey problem, even though we require our monochromatic set to be in convex position. Our results also apply to the case of l=3 and q=2 by using a geometric variation of the stepping up lemma of Erd\H os and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3-uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A note on order-type homogeneous point sets

Let OT_d(n) be the smallest integer N such that every N-element point sequence in R^d in general position contains an order-type homogeneous subset of size n, where a set is order-type homogeneous if all (d+1)-tuples from this set have the same orientation. It is known that a point sequence in R^d that is order-type homogeneous forms the vertex set of a convex polytope that is combinatorially equivalent to a cyclic polytope in R^d. Two famous theorems of Erdos and Szekeres from 1935 imply that OT_1(n) = Theta(n^2) and OT_2(n) = 2^(Theta(n)). For d \geq 3, we give new bounds for OT_d(n). In particular: 1. We show that OT_3(n) = 2^(2^(Theta(n))), answering a question of Eliáš and Matoušek. 2. For d \geq 4, we show that OT_d(n) is bounded above by an exponential tower of height d with O(n) in the topmost exponent.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Coloring intersection graphs of x-monotone curves in the plane

A class of graphs G is chi-bounded if the chromatic number of the graphs in G is bounded by some function of their clique number. We show that the class of intersection graphs of simple x-monotone curves in the plane intersecting a vertical line is chi-bounded. As a corollary we show that the class of intersection graphs of rays in the plane is chi-bounded, and the class of intersection graphs of unit segments in the plane is chi-bounded

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Density theorems for intersection graphs of t-monotone curves

A curve γin the plane is t-monotone if its interior has at most t-1 vertical tangent points. A family of t-monotone curves F is \emph{simple} if any two members intersect at most once. It is shown that if F is a simple family of n t-monotone curves with at least εn^2 intersecting pairs (disjoint pairs), then there exists two subfamilies F_1,F_2 \subset F of size δn each, such that every curve in F_1 intersects (is disjoint to) every curve in F_2, where δdepends only on ε. We apply these results to find pairwise disjoint edges in simple topological graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ramsey-type results for semi-algebraic relations

A k-ary semi-algebraic relation E on R^d is a subset of R^{kd}, the set of k-tuples of points in R^d, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. A subset A of R^d is called homogeneous if all or none of the k-tuples from A satisfy E. A large number of geometric Ramsey-type problems and results can be formulated as questions about finding large homogeneous subsets of sets in R^d equipped with semi-algebraic relations. In this paper we study Ramsey numbers for k-ary semi-algebraic relations of bounded complexity and give matching upper and lower bounds, showing that they grow as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential and extends a result of Alon, Pach, Pinchasi, Radoičić, and Sharir, who proved this for k=2. We apply our results 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

$k$-quasi planar graphs

A topological graph is \emph{$k$-quasi-planar} if it does not contain $k$ pairwise crossing edges. A topological graph is \emph{simple} if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi, and Szegedy \cite{pach} showed that every $n$-vertex simple $k$-quasi-planar graph contains at most $O(n(\log n)^{2k-4})$ edges. This upper bound was recently improved (for large $k$) by Fox and Pach \cite{fox} to $n(\log n)^{O(\log k)}$. In this note, we show that all such graphs contain at most $(n\log^2n)2^{α^{c_k}(n)}$ edges, where $α(n)$ denotes the inverse Ackermann function and $c_k$ is a constant that depends only on $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A note on geometric 3-hypergraphs

In this note, we prove several Turán-type results on geometric hypergraphs. The two main theorems are 1) Every $n$-vertex geometric 3-hypergraph in 2-space with no three strongly crossing edges has at most $O(n^2)$ edges, 2) Every $n$-vertex geometric 3-hypergraph in 3-space with no two disjoint edges has at most $O(n^2)$ edges. These results support two conjectures that were raised by Dey and Pach, and by Akiyama and Alon.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Erdos-Szekeres-type theorems for monotone paths and convex bodies

For any sequence of positive integers j_1 < j_2 < ... < j_n, the k-tuples (j_i,j_{i + 1},...,j_{i + k-1}), i=1, 2,..., n - k+1, are said to form a monotone path of length n. Given any integers n\ge k\ge 2 and q\ge 2, what is the smallest integer N with the property that no matter how we color all k-element subsets of [N]=\{1,2,..., N\} with q colors, we can always find a monochromatic monotone path of length n? Denoting this minimum by N_k(q,n), it follows from the seminal 1935 paper of Erd\H os and Szekeres that N_2(q,n)=(n-1)^q+1 and N_3(2,n) = {2n -4\choose n-2} + 1. Determining the other values of these functions appears to be a difficult task. Here we show that 2^{(n/q)^{q-1}} \leq N_3(q,n) \leq 2^{n^{q-1}\log n}, for q \geq 2 and n \geq q+2. Using a stepping-up approach that goes back to Erdos and Hajnal, we prove analogous bounds on N_k(q,n) for larger values of k, which are towers of height k-1 in n^{q-1}. As a geometric application, we prove the following extension of the Happy Ending Theorem. Every family of at least M(n)=2^{n^2 \log n} plane convex bodies in general position, any pair of which share at most two boundary points, has n members in convex position, that is, it has n members such that each of them contributes a point to the boundary of the convex hull of their union.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On disjoint crossing families in geometric graphs

A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. A geometric graph contains a (k,l)-crossing family if there is a pair of edge subsets E_1,E_2 such that |E_1| = k and |E_2| = l, the edges in E_1 are pairwise crossing, the edges in E_2 are pairwise crossing, and every edges in E_1 is disjoint to every edge in E_2. We conjecture that for any fixed k,l, every n-vertex geometric graph with no (k,l)-crossing family has at most c_{k,l}n edges, where c_{k,l} is a constant that depends only on k and l. In this note, we show that every n-vertex geometric graph with no (k,k)-crossing family has at most c_kn\log n edges, where c_k is a constant that depends only on k, by proving a more general result which relates extremal function of a geometric graph F with extremal function of two completely disjoint copies of F. We also settle the conjecture for geometric graphs with no (2,1)-crossing family. As a direct application, this implies that for any circle graph F on 3 vertices, every n-vertex geometric graph that does not contain a matching whose intersection graph is F has at most O(n) edges.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The number of edges in k-quasi-planar graphs

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 note, we improve this bound to (n\log n)2^{α^{c_k}(n)} in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here α(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.

0 citations0 reviewsNo code linkedOpen access