We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
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 ). -
Abstract Let
be the maximum possible number off s ,k (n )s ‐term arithmetic progressions in a set ofn integers which contains nok ‐term arithmetic progression. For all fixed integers , we prove thatk >s ≥ 3 , which answers an old question of Erdős. In fact, we prove upper and lower bounds forf s ,k (n ) =n 2 −o (1) which show that its growth is closely related to the bounds in Szemerédi's theorem.f s ,k (n ) -
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs are
equivalent if there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number r edge(H ;q ) of an edge‐ordered graphH is the smallestN such that there exists an edge‐ordered graphG onN vertices such that, for everyq ‐coloring of the edges ofG , there is a monochromatic subgraph ofG equivalent toH . Recently, Balko and Vizer proved thatr edge(H ;q ) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantc such thatfor every edge‐ordered graph H onn vertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering. -
Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $\Theta (n^{1/4})$ . We study the analogous problem in the $\mathbb {Z}_n$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $\mathbb {Z}_n$ for all positive integer $n$ . We further determine up to a constant factor the discrepancy of arithmetic progressions in $\mathbb {Z}_n$ for many $n$ . For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $\mathbb {Z}_n$ is $\Theta (n^{1/3+r_k/(6k)})$ , where $r_k \in \{0,1,2\}$ is the remainder when $k$ is divided by $3$ . This solves a problem of Hebbinghaus and Srivastav.more » « less
-
Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $G = {\mathbb{F}}_2^n$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.more » « less