An official website of the United States government
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph onnvertices, 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 < Bsuch that (under optimal play) Proposer wins with high probability if, while Decider wins with high probability if. This is a factor oflarger than the lower bound coming from the off‐diagonal Ramsey numberr(3,s).
more »
« less
Nucleation and growth in two dimensions
We consider a dynamical process on a graphG, in which vertices are infected (randomly) at a rate which depends on the number of their neighbors that are already infected. This model includes bootstrap percolation and first‐passage percolation as its extreme points. We give a precise description of the evolution of this process on the graph, significantly sharpening results of Dehghanpour and Schonmann. In particular, we determine the typical infection time up to a constant factor for almost all natural values of the parameters, and in a large range we obtain a stronger, sharp threshold.
more »
« less
- Award ID(s):
- 1855745
- PAR ID:
- 10121819
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 56
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 63-96
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from(and hence is likely to have a clique of size roughly), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesnδprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than.more » « less
-
We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of verticesn. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low asin the sparse graph regime (with the average degree smaller than) andin the dense graph regime, for a small positive constant. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.more » « less
-
Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm.more » « less
-
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graphGn,1/2typically admits a covering of a constant fraction of its edges by edge‐disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: forandA1,…,Atchosen uniformly and independently from thek‐subsets of {1,…,n}, what can one say aboutOur main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently.more » « less
