Premium
On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments
Author(s) -
Gishboliner Lior,
Krivelevich Michael,
Kronenberg Gal
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20751
Subject(s) - tournament , mathematics , combinatorics , random graph , discrete mathematics , enhanced data rates for gsm evolution , conjecture , graph coloring , giant component , graph , computer science , telecommunications
We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of G ∼ G ( n , 1 + ɛ n )in terms of ɛ . We then apply this result to prove the following conjecture by Frieze and Pegden. For every ɛ > 0 , there existsℓ ɛsuch that w.h.p. G ∼ G ( n , 1 + ɛ n ) is not homomorphic to the cycle on 2 ℓ ɛ + 1 vertices. We also consider the coloring properties of biased random tournaments. A p ‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p . We show that for p = Θ ( 1 n ) the chromatic number of a p ‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case p = 1 + ɛ nwe use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse Θ ( ɛ 3 ) n edges to make it 2‐colorable.