For graphs
Ramsey, Paper, Scissors
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on
- Award ID(s):
- 1855635
- PAR ID:
- 10173272
- 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. 1157-1173
- 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
Let
denote the power set of [ n ], ordered by inclusion, and letdenote the random poset obtained from by retaining each element from independently at random with probability p and discarding it otherwise. Givenany fixed posetF we determine the threshold for the property thatcontains F as an induced subposet. We also asymptotically determine the number of copies of a fixed posetF in. Finally, we obtain a number of results on the Ramsey properties of the random poset . -
more » « less
Abstract Given a graph
, its auxiliary square‐graph is the graph whose vertices are the non‐edges of and whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in . We determine the threshold edge‐probability at which the Erdős–Rényi random graph begins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of . We show , a polylogarithmic improvement on earlier bounds on due to Hagen and the authors. As a corollary, we determine the threshold at which the random right‐angled Coxeter group a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence. -
more » « less
Abstract If
G is a graph andis a set of subgraphs of G , then an edge‐coloring ofG is called‐polychromatic if every graph from gets all colors present in G . The‐polychromatic number of G , denoted, is the largest number of colors such that G has an‐polychromatic coloring. In this article, is determined exactly when G is a complete graph andis the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph andis the family of all 2‐factors, or the family of all Hamiltonian cycles. -
more » « less
Abstract Let
be the random directed graph on n vertices where each of thepossible arcs is present independently with probability p . A celebrated result of Frieze shows that ifthen typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in is typically . We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typically directed Hamilton cycles.
