Displacement convexity of entropy and related inequalities on graphs

We introduce the notion of an interpolating path on the set of probability measures on finite graphs. Using this notion, we first prove a displacement convexity property of entropy along such a path and derive Prékopa-Leindler type inequalities, a Talagrand transport-entropy inequality, certain HWI type as well as log-Sobolev type inequalities in discrete settings. To illustrate through examples, we apply our results to the complete graph and to the hypercube for which our results are optimal—by passing to the limit, we recover the classical log-Sobolev inequality for the standard Gaussian measure with the optimal constant.     

Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of disjoint copies of K_d,d. This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.     

Finding cliques using few probes

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (and hence is likely to have a clique of size roughly ), then for every δ<2 and constant ?, there is an α<2 (that may depend on δ and ?) such that no algorithm that makes n^δ probes in ? rounds is likely (over the choice of the random graph) to output a clique of size larger than .     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The Number of Linear Extensions of the Boolean Lattice

Let L(Q ^t ) denote the number of linear extensions of the t-dimensional Boolean lattice Q ^t . We use the entropy method of Kahn to show that

Isoperimetric Invariants For Product Markov Chains and Graph Products

Bounds on some isoperimetric constants of the Cartesian product of Markov chains are obtained in terms of related isoperimetric quantities of the individual chains.* Research supported in part by NSF Grants. Research supported by NSF Grant No. CCR-9503952 and DMS-9800351.     

On the chromatic number of set systems

An (r, l)‐system is an r‐uniform hypergraph in which every set of l vertices lies in at most one edge. Let m_k(r, l) be the minimum number of edges in an (r, l)‐system that is not k‐colorable. Using probabilistic techniques, we prove that where b_{r, l} is explicitly defined and a_{r, l} is sufficiently small. We also give a different argument proving (for even k) where a′_{r, l}=(r?l+1)/r(2^r?1re)^?l/(l?1). Our results complement earlier results of Erd?s and Lovász [10] who mainly focused on the case l=2, k fixed, and r large. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 87–98, 2001     

Entropy and set cardinality inequalities for partition‐determined functions

A new notion of partition‐determined functions is introduced, and several basic inequalities are developed for the entropies of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition‐determined functions imply entropic analogues of general inequalities of Plünnecke‐Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information‐theoretic inequalities. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 399–424, 2012     

Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point

We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice ${\mathbb{Z}^{d}}$ —heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L ^d-1. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L/(log L)².     

Simple Markov‐chain algorithms for generating bipartite graphs and tournaments

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in general, but in the near‐regular case, i.e., when all the degrees are almost equal, we give a proof of rapid mixing. Our methods also apply to the corresponding problem for general (nonbipartite) regular graphs, which was studied earlier by several researchers. One significant difference in our approach is that our chain has one state for every graph (or bipartite graph) with the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. For the problem of generating tournaments, we are able to prove that our Markov chain on tournaments is rapidly mixing, if the score sequence is near‐regular. The proof techniques we use for the two problems are similar. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 293–308, 1999