On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments. Issue 4 (29th December 2017)

• Record Type: Journal Article
• Authors: Gishboliner, Lior; Krivelevich, Michael; Kronenberg, Gal
• Is Part Of: Random structures & algorithms. Volume 52:Issue 4(2018)
• Page Start: 545
• Page End: 559
• Publication Date: 2017-12-29
• Subjects: chromatic number -- graph coloring -- max‐cut -- random graph -- random tournament; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20751
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 + ɛ n we 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.