We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of the results of Kahn, Galvin and Tet ali, and Zhao showing that a union of copies of @math maximizes the number of independent sets and the independence polynomial of a d-regular graph. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of @math . Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstr "om. In probabilistic language, our main theorems state that for all d-regular graphs and all @math , the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity @math are maximized by @math . Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case.
The technique of writing the expected size of an independent set in two ways (as we do here) was used by Shearer @cite_9 in proving lower bounds on the average size of an independent set in @math -free graphs and then by Alon @cite_29 for graphs in which all vertex neighborhoods are @math -colorable. The idea of bounding the occupancy fraction instead of the partition function comes in part from work of the third author @cite_24 in improving, at low densities, the bounds on matchings of a given size in Ilinca and Kahn @cite_5 and independent sets of a given size in Carroll, Galvin, and Tet ali @cite_12 . The use of linear programming for counting graph homomorphisms appears in Kopparty and Rossman @cite_11 , where they use a combination of entropy and linear programming to compute a related quantity, the homomorphism domination exponent, in chordal and series-parallel graphs.
@cite_9 @cite_29 @cite_24 @cite_5 @cite_12 @cite_11
2162218992 2078604563 2963560773 2032529651 2083618772 2062088877
Let G be a regular graph of degree d on n points which contains no Kr (r ≥ 4). Let α be the independence number of G. Then we show for large d that α ≥ c(r)n ***image***. © 1995 John Wiley & Sons, Inc. Let G = (V,E) be a graph on n vertices with average degree t ≥ 1 in which for every vertex v ∈ V the induced subgraph on the set of all neighbors of v is r-colorable. We show that the independence number of G is at least c log (r+1) n t log t, for some absolute positive constant c. This strengthens a well known result of Ajtai, Komlos and Szemeredi. Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem, conjectured by Erdos in 1979. There exists an absolute constant c′ > 0 so that in every graph on n vertices in which any set of b √ nc vertices contains at least one edge, there is some set of b √ nc vertices that contains at least c′ √ n log n edges. We give upper bounds for the number @F"@?(G) of matchings of size @? in (i) bipartite graphs G=(X@?Y,E) with specified degrees d"x (x@?X), and (ii) general graphs G=(V,E) with all degrees specified. In particular, for d-regular, N-vertex graphs, our bound is best possible up to an error factor of the form exp[o"d(1)N], where o"d(1)->0 as d-> . This represents the best progress to date on the ''Upper Matching Conjecture'' of Friedland, Krop, Lundow and Markstrom. Some further possibilities are also suggested. 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 [email protected]?N 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 N2d disjoint copies of K"d","d. This provides asymptotic evidence for a conjecture of S. 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. We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)|>=|Hom(G,T)|^c for every graph T. The problem of determining whether HDE(F,G)>=1 is known as the homomorphism domination problem, and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs F and G for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case, where F is chordal and G is series-parallel.