Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let H_d(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
We investigate the problem of colouring random graphs G ? G(n; p)
in polynomial expected time. For the case p ? 1.01/n, we present an algorithm
that finds an optimal colouring in linear expected time. For
p ?? ln6(n)/n, we give algorithms which approximate the chromatic
number within a factor of O(? np). We also obtain an O(?
np/ ln(np))-
approximation algorithm for the independence number. As an application,
we propose an algorithm for deciding satisfiability of random 2k-
SAT formulas (with sufficiently many clauses) in
polynomial expected time.
We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
We consider instances of the maximum independent set problem that are constructed
according to the following semirandom model. Let Gn,p be a random graph, and let
S be a set of k vertices, chosen uniformly at random. Then, let G0 be the graph
obtained by deleting all edges connecting two vertices in S. Finally, an adversary may
add edges to G0 that do not connect two vertices in S, thereby producing the instance
G = G ∗ n,p,k . We present an algorithm that on input G = G ∗ n,p,k finds an independent
set of size ≥ k within polynomial expected time, provided that k ≥ C(n/p)1/2 for a
certain constant C > 0. Moreover, we prove that in the case k ≤ (1 − ε) ln(n)/p this
problem is hard.
We study semirandom k-colorable graphs made up as follows. Partition the vertex set
V = {1, ... , n} randomly into k classes V1, ... , Vk of equal size and include each Vi-Vj -edge
with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may
add further Vi-Vj -edges (i 6= j) to G0, thereby completing the semirandom graph G = G ∗ n,p,k.
We show that if np ≥ max{(1 + ε)k ln n,C0k2} for a certain constant C0 > 0 and an arbitrarily
small but constant ε > 0, an optimal coloring of G ∗ n,p,k can be found in polynomial time with high
probability. Furthermore, if np ≥ C0 max{k ln n, k2}, a k-coloring of G ∗ n,p,k can be computed in
polynomial expected time. Moreover, an optimal coloring of G ∗ n,p,k can be computed in expected
polynomial time if k ≤ ln1/3 n and np ≥ C0k ln n. By contrast, it is NP-hard to k-color G ∗ n,p,k
w.h.p. if np ≤ (1/2 − ε)k ln(n/k).