2016/03/13 by Lior Gishboliner, Michael Krivelevich, Gishboliner, Lior +3
Computer Science · Mathematics · #05C15 #05C20 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1603.04044
openalex publication_date 2016/03/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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,\frac 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 \whp G∼ G(n,\frac 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=Θ(\frac 1n) 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=\frac 1+εn we use the aforementioned result on MAXCUT.