On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments

DOI10.1002/RSA.20751zbMATH Open1394.05033arXiv1603.04044OpenAlexW2962925181MaRDI QIDQ4584909FDOQ4584909

Gal Kronenberg, Michael Krivelevich, Lior Gishboliner

Publication date: 5 September 2018

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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 $GsimGleft(n,frac1+varepsilonnight)$ in terms of $varepsilon$. We then apply this result to prove the following conjecture by Frieze and Pegden. For every $varepsilon>0$ there exists $el{l}_{v}arepsilon$ such that whp $GsimG(n,frac1+varepsilonn)$ is not homomorphic to the cycle on $2el{l}_{v}arepsilon+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=Theta(frac1n)$ 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=frac1+varepsilonn$ we use the aforementioned result on MAXCUT.

Full work available at URL: https://arxiv.org/abs/1603.04044

zbMATH Keywords

random graphchromatic numbergraph coloringrandom tournamentMAX-cut

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584909)