Path coupling without contraction

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in Ω×Ω, where Ω is the state space of the Markov chain, analysis is done on a smaller set SΩ×Ω. If the coefficient of contraction β is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if β=1 then analysis (of the variance) is still required for all pairs in Ω×Ω. In this paper we present a new approach which shows rapid mixing in the case β=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved. We also present a technique applicable when β=1 and our condition is not met.     

Fast mixing for independent sets,colorings, and other models on trees

We study the mixing time of the Glauber dynamics for general spin systems on the regular tree, including the Ising model, the hard‐core model (independent sets), and the antiferromagnetic Potts model at zero temperature (colorings). We generalize a framework, developed in our recent paper (Martinelli, Sinclair, and Weitz, Tech. Report UCB//CSD‐03‐1256, Dept. of EECS, UC Berkeley, July 2003) in the context of the Ising model, for establishing mixing time O(nlog n), which ties this property closely to phase transitions in the underlying model. We use this framework to obtain rapid mixing results for several models over a significantly wider range of parameter values than previously known, including situations in which the mixing time is strongly dependent on the boundary condition. We also discuss applications of our framework to reconstruction problems on trees. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the connectivity of proper colorings of random graphs and hypergraphs

Let Ω_q=Ω_q(H) denote the set of proper [q]‐colorings of the hypergraph H. Let Γ_q be the graph with vertex set Ω_q where two colorings σ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_n,m;k, k ≥ 2, the random k‐uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Γ_q is connected if d is sufficiently large and . This is optimal up to the first order in d. Furthermore, with a few more colors, we find that the diameter of Γ_q is O(n) w.h.p., where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber dynamics Markov Chain on Ω_q is ergodic w.h.p.     

Future independent times and Markov chains

Summary A random timeT is a future independent time for a Markov chain (X _n ) ₀ ifT is independent of (X _T+n ) _n ^/ =0 and if (X _T+n ) _n ^/ =0 is a Markov chain with initial distribution and the same transition probabilities as (X _n ) ₀ . This concept is used (with the conditional stationary measure) to give a new and short proof of the basic limit theorem of Markov chains, improving somewhat the result in the null-recurrent case.This work was supported by the Swedish Natural Science Research Council and done while the author was visiting the Department of Statistics, Stanford University     

On independent sets in hypergraphs

The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if H_n is an n‐vertex ‐uniform hypergraph in which every r‐element set is contained in at most d edges, where , then where satisfies as . The value of c_r improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each and all values of , there are infinitely many H_n such that where depends only on r. In addition, for many values of d we show as , so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014     

Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, together with integers s_i and t_i (1≤s_i≤t_i≤|E_i|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge E_i satisfies s_i≤|φ(E_i)|≤t_i, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge E_i induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (s_i,t_i)=(2,|E_i|), while ‘C-edge’ assumes (s_i,t_i)=(1,|E_i|−1)-the differences are rather significant.     

Variable length path coupling

We present a new technique for constructing and analyzing couplings to bound the convergence rate of finite Markov chains. Our main theorem is a generalization of the path coupling theorem of Bubley and Dyer, allowing the defining partial couplings to have length determined by a random stopping time. Unlike the original path coupling theorem, our version can produce multistep (non‐Markovian) couplings. Using our variable length path coupling theorem, we improve the upper bound on the mixing time of the Glauber dynamics for randomly sampling colorings. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

Independent sets in bounded-degree hypergraphs

In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter Δ. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ+1)/2. It also allows us to apply results on local search algorithms on graphs to obtain a (Δ+1)/2 approximation for the weighted MIS and (Δ+3)/5−? approximation for the unweighted case. We improve the bound in the weighted case to ⌈(Δ+1)/3⌉ using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of Δ−1, significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of Δ.     

On the number of minimal transversals in 3-uniform hypergraphs

We prove that the number of minimal transversals (and also the number of maximal independent sets) in a 3-uniform hypergraph with n vertices is at most cⁿ, where c≈1.6702. The best known lower bound for this number, due to Tomescu, is adⁿ, where d=10^1/5≈1.5849 and a is a constant.     

Another note on cliques and independent sets

Entringer, Goddard, and Henning studied graphs in which every vertex belongs to both an (m + 1)‐clique and an independent (n + 1)‐set; they proved that there is such a graph of order p if and only if . We give an alternative and slightly easier proof of this fact, relating it to combinatorial matrix theory. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 173–175, 2000     

Maximal independent sets in minimum colorings

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

On distance -dominating and -independent sets in sparse graphs

Dvořák [European J. Combin. 34 (2013), pp. 833–840] gave a bound on the minimum size of a distance -dominating set in terms of the maximum size of a distance -independent set and generalized coloring numbers, thus obtaining a constant-factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using a linear programming (LP)-based argument inspired by the work of Bansal and Umboh [Inform. Process. Lett. 122 (2017), pp. 21–24].     

Essential independent sets and long cycles

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. For SV(G) with S≠, let Δ(S)=max{d_G(x)|xS}. We prove the following theorem. Let k2 and let G be a k-connected graph. Suppose that Δ(S)d for every essential independent set S of order k. Then G has a cycle of length at least min{|G|,2d}. This generalizes a result of Fan.     

On scrambled sets and a theorem of Kuratowski on independent sets

The measure of scrambled sets of interval self-maps was studied by many authors, including Smítal, Misiurewicz, Bruckner and Hu, and Xiong and Yang. In this note, first we introduce the notion of ``-chaos" which is related to chaos in the sense of Li-Yorke, and we prove a general theorem which is an improvement of a theorem of Kuratowski on independent sets. Second, we apply the result to scrambled sets of higher dimensional cases. In particular, we show that if a map of the unit -cube is -chaotic on , then for any there is a map such that and are topologically conjugate, and has a scrambled set which has Lebesgue measure 1, and hence if , then there is a homeomorphism with a scrambled set satisfying that is an -set in and has Lebesgue measure 1.

     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.     

Bounds on regeneration times and convergence rates for Markov chains

In many applications of Markov chains, and especially in Markov chain Monte Carlo algorithms, the rate of convergence of the chain is of critical importance. Most techniques to establish such rates require bounds on the distribution of the random regeneration time T that can be constructed, via splitting techniques, at times of return to a “small set” C satisfying a minorisation condition P(x,·)(·), xC. Typically, however, it is much easier to get bounds on the time τ_C of return to the small set itself, usually based on a geometric drift function , where . We develop a new relationship between T and τ_C, and this gives a bound on the tail of T, based on ,λ and b, which is a strict improvement on existing results. When evaluating rates of convergence we see that our bound usually gives considerable numerical improvement on previous expressions.     

The Spectrum of the Independent Metropolis–Hastings Algorithm

In this paper we perform a spectral analysis for the kernel operator associated with the transition kernel for the Metropolis–Hastings algorithm that uses a fixed, location independent proposal distribution. Our main result is to establish the spectrum of the kernel operator T in the continuous case, thereby generalizing the results obtained by Liu in (Statist. Comput. 6, 113–119 1996) for the finite case.