For graphs
On edge‐ordered Ramsey numbers
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs are
- Award ID(s):
- 1855635
- PAR ID:
- 10260102
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 4
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 1174-1204
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract G andF , writeif any coloring of the edges of G withcolors yields a monochromatic copy of the graph F . Supposeis obtained from a graph S withs vertices and maximum degreed by subdividing its edgesh times (that is, by replacing the edges ofS by paths of lengthh + 1). We prove that there exists a graphG with no more thanedges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degreed onq vertices with the property that every pair of vertices of degree greater than 2 are distance at leasth + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs. -
more » « less
Abstract For a given graph
H , we say that a graphG onn vertices isH ‐saturated ifH is not a subgraph ofG , but for any edgethe graph contains a subgraph isomorphic to H . The set of all valuesm for which there exists anH ‐saturated graph onn vertices andm edges is called the edge spectrum forH ‐saturated graphs. In the present article, we study the edge spectrum forH ‐saturated graphs whenH is a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number. -
null (Ed.)We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars.more » « less
-
more » « less
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on
n vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at leasts . We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants 0 <A <B such that (under optimal play) Proposer wins with high probability if, while Decider wins with high probability if . This is a factor of larger than the lower bound coming from the off‐diagonal Ramsey number r (3,s ). -
more » « less
The triangle‐free process begins with an empty graph on
n vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle‐free graph at which the triangle‐free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on the Ramsey numbersR (3,t ): we show, which is within a 4 + o (1) factor of the best known upper bound. Our improvement on previous analyses of this process exploits the self‐correcting nature of key statistics of the process. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle‐free graph produced by the triangle‐free process: they are precisely those triangle‐free graphs with density at most 2.
