skip to main content


Title: On the connectivity of proper colorings of random graphs and hypergraphs

Let Ωqq(H) denote the set of proper [q]‐colorings of the hypergraphH. Let Γqbe the graph with vertex set Ωqwhere two coloringsσ,τare adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH=Hn,m;k, k ≥ 2, the randomk‐uniform hypergraph withV=[n] andm=dn/khyperedges then w.h.p. Γqis connected ifdis sufficiently large and. This is optimal up to the first order ind. Furthermore, with a few more colors, we find that the diameter of ΓqisO(n) w.h.p., where the hidden constant depends ond. So, with this choice ofd,q, the natural Glauber dynamics Markov Chain on Ωqis ergodic w.h.p.

 
more » « less
NSF-PAR ID:
10133767
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
56
Issue:
4
ISSN:
1042-9832
Page Range / eLocation ID:
p. 988-997
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$. 
    more » « less
  2. Let Ωq denote the set of proper [q]-colorings of the random graph Gn,m,m=dn/2 and let Hq be the graph with vertex set Ωq and an edge {σ,τ} where σ,τ are mappings [n]→[q] iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance |{v∈[n]:σ(v)≠τ(v)}|. We show that w.h.p. Hq contains a single giant component containing almost all colorings in Ωq if d is sufficiently large and q≥cdlogd for a constant c>3/2. 
    more » « less
  3. In this paper we consider the existence of Hamilton cycles in the random graph. This random graph is chosen uniformly from, the set of graphs with vertex set [n],medges and minimum degree at least 3. Our ultimate goal is to prove that ifm = cnandc > 3/2 is constant thenGis Hamiltonian w.h.p. In Frieze (2014), the second author showed thatc ≥ 10 is sufficient for this and in this paper we reduce the lower bound toc > 2.662…. This new lower bound is the same lower bound found in Frieze and Pittel (2013) for the expansion of so‐called Pósa sets.

     
    more » « less
  4. We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn ≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean spacesatisfies −Ω = Ωcand Ω + v = Ωc(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖2 = 1. Let. Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular,Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10−9would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.

     
    more » « less
  5. Abstract

    Given ak‐vertex graphHand an integern, what are then‐vertex graphs with the maximum number of induced copies ofH? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction ofk‐vertex subsets of ann‐vertex graph that induce a copy ofH. Huang, Lee, and the first author proved that for a randomk‐vertex graphH, almost surely then‐vertex graphs maximizing the number of induced copies ofHare the balanced iterated blow‐ups ofH. In this article, we consider the case where the graphHis obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely alln‐vertex graphs maximizing the number of induced copies ofHare balanced iterated blow‐ups of.

     
    more » « less