1,721,119 research outputs found
Applications of a New Separator Theorem for String Graphs
Full text linkAn 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
String graphs and incomparability graphs
Full text linkGiven 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.
It is known that every incomparability graph is a string graph. For “dense” string graphs, we establish a partial converse of this statement. We prove that for every ε>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 FellowshipPrinceton University (Centennial Fellowship)Simons FoundationNational Science Foundation (U.S.) (Grant DMS-1069197
A new proof of the graph removal lemma
No full textLet H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n[superscript h]) copies of H can be made H-free by removing o(n[superscript 2]) edges. We give a new proof which avoids Szemerédi’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
Maximum union-free subfamilies
No full textAn 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 FoundationSamsung Scholarship FoundationSimons FoundationNational Science Foundation (U.S.) (NSF grant DMS-1069197
A note on light geometric graphs
Full text linkLet 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
On a problem of Erdos and Rothschild on edges in triangles
Full text linkErdos 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 epsilon > 0 such that h(n; c) > n epsilon for all su ciently large n. We prove that h(n; c) = nO(1= log log n) for every xed 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 n2=4 edges contains an edge that is in at least n=6 triangles
On two problems in graph Ramsey theory
Full text linkWe 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 twocoloring
of the edges of the complete graph KN contains a monochromatic copy of H. A famous
result of Chv atal, Rodl, Szemer edi and Trotter states that there exists a constant c( Delta) such that
r(H) c(Delta )n for every graph H with n vertices and maximum degree . The important open
question is to determine the constant c(Delta ). The best results, both due to Graham, Rodl and
Ruci nski, state that there are constants c and c0 such that 2c0 Delta[less than or equal to] c( Delta) 2c Deltalog2Delta . We improve this upper bound, showing that there is a constant c for which c(Delta )[less than or equal to] 2cDelta log Delta.
The induced Ramsey number rind(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. Erdos conjectured the existence of a constant c such that,
for any graph H on n vertices, rind(H) 2cn. We move a step closer to proving this conjecture,
showing that rind(H)[less than or equal to] 2cn log n. This improves upon an earlier result of Kohayakawa, Promel and Rodl by a factor of log n in the exponent
Dependent Random Choice
No full textWe describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them.National Science Foundation (U.S.). Graduate Research Fellowship ProgramPrinceton University (Centennial Fellowship)National Science Foundation (U.S.). (CAREER award DMS-0812005)U.S.-Israel Binational Science Foundation (BSF
The critical window for the classical Ramsey-Turán problem
Full text linkRamsey-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
- …
