Let Ω_{q}=Ω_{q}(
 NSFPAR ID:
 10133767
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 56
 Issue:
 4
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 988997
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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

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

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 ],m edges and minimum degree at least 3. Our ultimate goal is to prove that ifm =cn andc > 3/2 is constant thenG is 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. 
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Let
n ≥ 2. Suppose a subset Ω ofn ‐dimensional Euclidean spacesatisfies −Ω = Ω^{c}and Ω + v = Ω^{c}(up to measure zero sets) for every standard basis vector. For any and for any q ≥ 1, letand let . For any x ∈∂ Ω, letN (x ) denote the exterior normal vector atx such that ‖N (x )‖_{2} = 1. Let. Our main result shows that B has 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^{−9}would 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. 
Abstract Given a
k ‐vertex graphH and 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 ofH are the balanced iterated blow‐ups ofH . In this article, we consider the case where the graphH is obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely all n ‐vertex graphs maximizing the number of induced copies ofH are balanced iterated blow‐ups of.