Ramsey numbers of ordered graphs (Q5919338): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Ramsey numbers of ordered graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4830805 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey numbers for cycles in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4044600 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the existence of specified cycles in complementary graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordered Ramsey numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generalized Ramsey Theory for Graphs. II. Small Diagonal Numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Ramsey number of a graph with bounded maximum degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum Size of Reverse-Free Sets of Permutations / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the geometric Ramsey number of outerplanar graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new upper bound for diagonal Ramsey numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordered Ramsey numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey numbers of sparse hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recent developments in graph Ramsey theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Higher-order Erdős-Szekeres theorems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some remarks on the theory of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: All Ramsey numbers for cycles in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Erdős-Szekeres-type theorems for monotone paths and convex bodies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Davenport-Schinzel theory of matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5548200 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4410013 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3257129 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey-type results for geometric graphs. I / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey-type results for geometric graphs. II / rank
 
Normal rank
Property / cites work
 
Property / cites work: Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Extremal problems for ordered hypergraphs: small patterns and some enumeration / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a problem of K. Zarankiewicz / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordered Ramsey theory and track representations of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Forbidden paths and cycles in ordered graphs and matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Ramsey-type problem of J. A. Bondy and P. Erdős. II / rank
 
Normal rank

Latest revision as of 11:17, 21 July 2024

scientific article; zbMATH DE number 7152778
Language Label Description Also known as
English
Ramsey numbers of ordered graphs
scientific article; zbMATH DE number 7152778

    Statements

    Ramsey numbers of ordered graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    17 January 2020
    0 references
    Summary: An ordered graph is a pair \(\mathcal{G}=(G,\prec)\) where \(G\) is a graph and \(\prec\) is a total ordering of its vertices. The ordered Ramsey number \(\overline{R}(\mathcal{G})\) is the minimum number \(N\) such that every ordered complete graph with \(N\) vertices and with edges colored by two colors contains a monochromatic copy of \(\mathcal{G} \). In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings \(\mathcal{M}_n\) on \(n\) vertices for which \(\overline{R}(\mathcal{M}_n)\) is superpolynomial in \(n\). This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering. We also prove that the ordered Ramsey number \(\overline{R}(\mathcal{G})\) is polynomial in the number of vertices of \(\mathcal{G}\) if the bandwidth of \(\mathcal{G}\) is constant or if \(\mathcal{G}\) is an ordered graph of constant degeneracy and constant interval chromatic number. The first result gives a positive answer to a question of \textit{D. Conlon} et al. [J. Comb. Theory, Ser. B 122, 353--383 (2017; Zbl 1350.05085)]. For a few special classes of ordered paths, stars or matchings, we give asymptotically tight bounds on their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly. This result implies exact formulas for geometric Ramsey numbers of cycles introduced by \textit{G. Károlyi} et al. [Discrete Comput. Geom. 20, No. 3, 375--388 (1998; Zbl 0912.05046)].
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers