|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor)
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by K'arolyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor)
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by K'arolyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...
|
|
|
Erdos-Szekeres type theorems
Eliáš, Marek ; Matoušek, Jiří (advisor) ; Cibulka, Josef (referee)
Let P = (p1, p2, . . . , pN ) be a sequence of points in the plane, where pi = (xi, yi) and x1 < x2 < · · · < xN . A famous 1935 Erdős-Szekeres theorem asserts that every such P contains a monotone subsequence S of √ N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log N) points. First we define a (k + 1)-tuple K ⊆ P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S ⊆ P is kth-order monotone if its (k + 1)- tuples are all positive or all negative. In this thesis we investigate quantitative bound for the corresponding Ramsey-type result. We obtain an Ω(log(k−1) N) lower bound ((k − 1)-times iterated logarithm). We also improve bounds for related problems: Order types and One-sided sets of hyperplanes. 1
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor) ; Conlon, David (referee) ; Nešetřil, Jaroslav (referee)
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by Károlyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...
|
guest ::
