Search

For natural numbers d and t there exists a positive C such that if F is a family of n[superscript C] semi-algebraic sets in R[superscript d] 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 4[superscript n] 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., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS 1069197), NEC Corporation (MIT Award), National Science Foundation (U.S.) (Postdoctoral Fellowship), Swiss National Science Foundation (Grant 200021-125287/1)

An immersion of a graph H into a graph G is a one-to-one mapping f: V (H) → V (G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P [subscript uv] corresponding to edge uv has endpoints f(u) and f(v). The immersion is strong if the paths P [subscript uv] are internally disjoint from f(V (H)). It is proved that for every positive integer Ht, every simple graph of minimum degree at least 200t contains a strong immersion of the complete graph K [subscript t]. For dense graphs one can say even more. If the graph has order n and has 2cn [superscript 2] edges, then there is a strong immersion of the complete graph on at least c [superscript 2] n vertices in G in which each path P [subscript uv] is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree d has a clique minor of order at least cd [superscript 3/2], where c>0 is an absolute constant. For small values of t, 1≤t≤7, every simple graph of minimum degree at least t−1 contains an immersion of K [subscript t] (Lescure and Meyniel [13], DeVos et al. [6]). We provide a general class of examples showing that this does not hold when t is large., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), NEC Corporation (MIT Award)

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemer\'edi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers., Comment: 17 pages

Let G be a geometric graph on n vertices in general position in the plane. We say that G is k-light if no edge e of G has the property that each of the two open half-planes bounded by the line through e contains more than k edges of G. We extend the previous result in Ackerman and Pinchasi (2012) [1] and with a shorter argument show that every k-light geometric graph on n vertices has at most O(n√k) edges. This bound is best possible., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), NEC Corporation (MIT Award)

Szemeredi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rodl proved an analogue of Szemeredi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemeredi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and Rodl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdos–Stone–Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work., Simons Foundation (Fellowship), David & Lucile Packard Foundation (Fellowship), Alfred P. Sloan Foundation (Fellowship), NEC Corporation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), Akamai Foundation (Presidential Fellowship), Microsoft Research (PhD Fellowship)

Ramsey’s theorem, in the version of Erdos and Szekeres, states that every 2-coloring of the edges of the complete graph on {1,2,…,n} contains a monochromatic clique of order (1/2)logn. In this article, we consider two well-studied extensions of Ramsey’s theorem. Improving a result of Rodl, we show that there is a constant c > 0 such that every 2-coloring of the edges of the complete graph on {2,3,…,n} contains a monochromatic clique S for which the sum of 1/logi over all vertices i ∈ S is at least clogloglogn. This is tight up to the constant factor c and answers a question of Erdos from 1981. Motivated by a problem in model theory, Vaananen asked whether for every k there is an n such that the following holds: for every permutation π of 1,…,k − 1, every 2-coloring of the edges of the complete graph on {1,2,…,n} contains a monochromatic clique a[subscript 1] a[subscript π(2)+1] − a[subscript π(2) >⋯> a[subscript π(k−1)+1] − a[subscript π(k−1)]. That is, not only do we want a monochromatic clique, but the differences between consecutive vertices must satisfy a prescribed order. Alon and, independently, Erdős, Hajnal, and Pach answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in k. We make progress towards this conjecture, obtaining an upper bound on n which is exponential in a power of k. This improves a result of Shelah, who showed that n is at most double-exponential in k., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), Alfred P. Sloan Foundation (Fellowship), NEC Corporation (MIT Award)

An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(√m log m). In the present note, this bound is combined with a result of the authors, according to which every dense string graph contains a large complete balanced bipartite graph. Three applications are given concerning string graphs G with n vertices: (i) if K[subscript t] ⊈ G for some t, then the chromatic number of G is at most (log n) [superscript O(log t)]; (ii) if K[subscript t,t] ⊈ G, then G has at most t(log t) [superscript O(1)] n edges; and (iii) a lopsided Ramsey-type result, which shows that the Erdos–Hajnal conjecture almost holds for string graphs., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), Alfred P. Sloan Foundation (Fellowship), NEC Corporation (MIT Award)

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H′ are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H′. In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K[subscript k]. A famous theorem of Nešetřil and Rödl implies that any graph H which is Ramsey-equivalent to K[subscript k] must contain K[subscript k]. We prove that the only connected graph which is Ramsey-equivalent to K[subscript k] is itself. This gives a negative answer to the question of Szabó, Zumstein, and Zürcher on whether K[subscript k] is Ramsey-equivalent to K[subscript k]⋅K[subscript 2], the graph on k+1 vertices consisting of K[subscript k] with a pendent edge. In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s(H) be the smallest minimum degree over all Ramsey minimal graphs for H . The study of s(H) was introduced by Burr, Erdős, and Lovász, where they show that s(K[subscript k])=(k−1)[superscript 2]. We prove that s(K[subscript k]⋅K[subscript 2])=k−1, and hence K[subscript k] and K[subscript k]⋅K[subscript 2] are not Ramsey-equivalent. We also address the question of which non-connected graphs are Ramsey-equivalent to K[subscript k]. Let f(k,t) be the maximum f such that the graph H=K[subscript k]+fK[subscript t], consisting of K[subscript k] and f disjoint copies of K[subscript t], is Ramsey-equivalent to K[subscript k]. Szabó, Zumstein, and Zürcher gave a lower bound on f(k,t). We prove an upper bound on f(k,t) which is roughly within a factor 2 of the lower bound., David & Lucile Packard Foundation (Fellowship), Alfred P. Sloan Foundation (Fellowship), Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), NEC Corporation (MIT Award)

A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a tournament H a hero); for instance, all tournaments with at most four vertices are heroes. In this paper we explicitly describe all heroes., Simons Foundation (Fellowship)

In the 1960s, Erdős and Gallai conjectured that the edge set of every graph on n vertices can be partitioned into O(n) cycles and edges. They observed that one can easily get an O(nlogn) upper bound by repeatedly removing the edges of the longest cycle. We make the first progress on this problem, showing that O(nloglogn) cycles and edges suffice. We also prove the Erdős-Gallai conjecture for random graphs and for graphs with linear minimum degree., Royal Society (Great Britain) (University Research Fellowship), Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant NSF-DMS-1069197), Alfred P. Sloan Foundation (Fellowship), NEC Corporation (MIT NEC Corp. award), Swiss National Science Foundation (SNSF grant 200021-149111), United States-Israel Binational Science Foundation (grant)

Ramsey-Turán result proved by Szemerédi in 1972: any K [subscript 4-]free graph on n vertices with independence number o(n) has at most (1[over]8+o(1))n[superscript 2] edges. Four years later, Bollobás and Erdős gave a surprising geometric construction, utilizing the isoperimetric inequality for the high dimensional sphere, of a K 4-free graph on n vertices with independence number o(n) and (1[over]8−o(1))n[superscript 2] edges. Starting with Bollobás and Erdős in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about n[superscript 2]/8. These problems have received considerable attention and remained one of the main open problems in this area. In this paper, we give nearly best-possible bounds, solving the various open problems concerning this critical window., Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant NSF-DMS-1069197), NEC Corporation (MIT NEC Research Corporation Fund), National Science Foundation (U.S.) (Grant NSF-DMS-1201380), United States. National Security Agency (NSA Young Investigators Grant), United States-Israel Binational Science Foundation (grant), Akamai Technologies, Inc. (Akamai Presidential Fellowship at MIT)

The cube graph Q[subscript n] is the skeleton of the n-dimensional cube. It is an n-regular graph on 2[superscript n] vertices. The Ramsey number r(Q[subscript n] ;K[subscript s]) is the minimum N such that every graph of order N contains the cube graph Q[subscript n] or an independent set of order s. In 1983, Burr and Erdős asked whether the simple lower bound r(Q[subscript n] ;K[subscript s] )≥(s−1)(2[superscript n] −1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound., Swiss National Science Foundation (SNSF grant 200021-149111), United States-Israel Binational Science Foundation, Samsung (Firm) (Scholarship), Royal Society (Great Britain) (University Research Fellowship), David & Lucile Packard Foundation (Fellowship), Simons Foundation (Fellowship), NEC Corporation (MIT NEC Corp. award), National Science Foundation (U.S.) (NSF grant DMS-1069197)

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 ℝ[superscript d], there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. Motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, we address the question whether or not there exists a sequence of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree for which . 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 h, s and any ɛ > 0, there exists K = K(ɛ, h, s) satisfying the following condition. For any k ≧ K and for any semi-algebraic relation R on h-tuples of points in a Euclidean space ℝ[superscript d] with description complexity at most s, every finite set P ⫅ ℝ[superscript d] has a partition P = P[subscript 1] ∪ ⋯ ∪ P[subscript k] into k parts of sizes as equal as possible such that all but at most an ɛ-fraction of the h-tuples (P[subscript i1], … , P[subscript ih]) have the property that either all h-tuples of points with one element in each Pij are related with respect to R or none of them are., National Science Foundation (U.S.). Graduate Research Fellowship Program, Princeton University (Centennial Fellowship)

We prove several results from different areas of extremal combinatorics, giving complete or partial solutions to a number of open problems. These results, coming from areas such as extremal graph theory, Ramsey theory and additive combinatorics, have been collected together because in each case the relevant proofs are quite short., Royal Society (Great Britain) (University Research Fellowship), Simons Foundation (Fellowship), National Science Foundation (U.S.) (Grant DMS-1069197), National Science Foundation (U.S.) (Grant DMS-1101185), United States. Army Research Office. Multidisciplinary University Research Initiative (grant FA9550-10-1-0569), United States-Israel Binational Science Foundation (grant)

Dedicated to the 75th anniversary of the publication of the Happy Ending Theorem, 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., National Science Foundation (U.S.) (NSF-CAREER Award (DMS-0812005), Massachusetts Institute of Technology (Simons Fellowship), United States-Israel Binational Science Foundation (grant)

We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck [superscript 2]/log* k pairs of parts which are not ϵ -regular, where c,ϵ>0 are absolute constants. This bound is tight up to the constant c and addresses a question of Gowers on the number of irregular pairs in Szemerédi’s regularity lemma. In order to gain some control over irregular pairs, another regularity lemma, known as the strong regularity lemma, was developed by Alon, Fischer, Krivelevich, and Szegedy. For this lemma, we prove a lower bound of wowzer-type, which is one level higher in the Ackermann hierarchy than the tower function, on the number of parts in the strong regularity lemma, essentially matching the upper bound. On the other hand, for the induced graph removal lemma, the standard application of the strong regularity lemma, we find a different proof which yields a tower-type bound. We also discuss bounds on several related regularity lemmas, including the weak regularity lemma of Frieze and Kannan and the recently established regular approximation theorem. In particular, we show that a weak partition with approximation parameter ϵ may require as many as 2[superscript Ω](ϵ[superscript −2]) parts. This is tight up to the implied constant and solves a problem studied by Lovász and Szegedy., National Science Foundation (U.S.) (Grant DMS-1069197), Simons Fellowship, Royal Society (Great Britain) (Research Fellowship)

For a graph G, let (G) denote its chromatic number and (G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of (G)= (G) over all n-vertex graphs G. A famous conjecture of Haj os from 1961 states that (G) (G) for every graph G. That is, H(n) 1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd}os and Fajtlowicz further showed by considering a random graph that H(n) cn1=2= log n for some absolute constant c > 0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that (G)= (G) Cn1=2= log n for all n-vertex graphs G. In this paper we prove the Erd}os-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can nd in every graph on n vertices with independence number ., National Science Foundation (U.S.) (NSF grant DMS-110118), National Science Foundation (U.S.) (CAREER award DMS-0812005), United States-Israel Binational Science Foundation

Erdos and Rothschild asked to estimate the maximum number, denoted by h(n, c), such that every n-vertex graph with at least cn2 edges, each of which is contained in at least one triangle, must contain an edge that is in at least h(n, c) triangles. In particular, Erdos asked in 1987 to determine whether for every c > 0 there is ϵ > 0 such that h(n,c) > nϵ for all sufficiently large n. We prove that h(n, c) = n O(1/ log log n) for every fixed c < 1/4. This gives a negative answer to the question of Erdos, and is best possible in terms of the range for c, as it is known that every n-vertex graph with more than n 2/4 edges contains an edge that is in at least n/6 triangles.

An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? A family of sets is called union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. We show that every family of m sets contains a union-free subfamily of size at least [[sqrt 4m+1]] - 1 that this bound is tight. This solves Moser’s problem and proves a conjecture of Erdos and Shelah from 1972. More generally, a family of sets is a-union-free if there are no alpha + 1 distinct sets in the family such that one of them is equal to the union of a others. We determine up to an absolute multiplicative constant factor the size of the largest guaranteed a-union-free subfamily of a family of m sets. Our result verifies in a strong form a conjecture of Barat, Füredi, Kantor, Kim and Patkos., National Science Foundation (U.S.) (NSF grant DMS-1101185), National Science Foundation (U.S.) (NSF-CAREER Award (DMS-0812005), United States-Israel Binational Science Foundation, Samsung Scholarship Foundation, Simons Foundation, National Science Foundation (U.S.) (NSF grant DMS-1069197)

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of H. A famous result of Chv\'atal, R\"{o}dl, Szemer\'edi and Trotter states that there exists a constant c(\Delta) such that r(H) \leq c(\Delta) n for every graph H with n vertices and maximum degree \Delta. The important open question is to determine the constant c(\Delta). The best results, both due to Graham, R\"{o}dl and Ruci\'nski, state that there are constants c and c' such that 2^{c' \Delta} \leq c(\Delta) \leq 2^{c \Delta \log^2 \Delta}. We improve this upper bound, showing that there is a constant c for which c(\Delta) \leq 2^{c \Delta \log \Delta}. The induced Ramsey number r_{ind}(H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd\H{o}s conjectured the existence of a constant c such that, for any graph H on n vertices, r_{ind}(H) \leq 2^{c n}. We move a step closer to proving this conjecture, showing that r_{ind} (H) \leq 2^{c n \log n}. This improves upon an earlier result of Kohayakawa, Pr\"{o}mel and R\"{o}dl by a factor of \log n in the exponent., Comment: 18 pages

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,0 there exists δ>0 with the property that if C is a collection of curves whose string graph has at least ε|C|[superscript 2] edges, then one can select a subcurve γ′ of each γ∈C such that the string graph of the collection {γ′:γ∈C} has at least δ|C|[superscript 2] edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs., National Science Foundation (U.S.). Graduate Research Fellowship, Princeton University (Centennial Fellowship), Simons Foundation, National Science Foundation (U.S.) (Grant DMS-1069197)

The Erdos-Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n^{d(H)}, where d(H) > 0 depends only on the graph H. Except for a few special cases, this conjecture remains wide open. However, it is known that a H-free graph must contain a complete or empty bipartite graph with parts of polynomial size. We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on n vertices is H-free, for any given H, then it must contain a complete or empty tripartite subgraph with parts of order c(log n)^{1/2 + d(H)}, where d(H) > 0 depends only on H. This improves on the bound of c(log n)^{1/2}, which holds in all 3-uniform hypergraphs, and, up to the value of the constant d(H), is best possible. We also prove that, for k > 3, no analogue of the standard Erdos-Hajnal conjecture can hold in k-uniform hypergraphs. That is, there are k-uniform hypergraphs H and sequences of H-free hypergraphs which do not contain cliques or independent sets of size appreciably larger than one would normally expect., 15 pages

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. 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 every n-vertex topological graph with no k-grid has O-k(n) edges. We conjecture that the number of edges of every n-vertex topological graph with no k-grid such that all of its 2k edges have distinct endpoints is 0 k(n). This conjecture is shown to be true apart from an iterated logarithmic factor log* n. A k-grid is natural if its edges have distinct endpoints, and the arcs representing each of its edge subsets are pairwise disjoint. We also conjecture that every n-vertex geometric graph with no natural k-grid has Ok(n) edges, but we can establish only an O-k(n log(2) n) upper bound. We verify the above conjectures in several special cases. (C) 2014 Elsevier B.V. All rights reserved.