The Bipartite Swapping Trick on Graph Homomorphisms

Abstract

We provide an upper bound to the number of graph homomorphisms from $G$ to $H$, where $H$ is a fixed graph with certain properties, and $G$ varies over all $N$-vertex, $d$-regular graphs. This result generalizes a recently resolved conjecture of Alon and Kahn on the number of independent sets. We build on the work of Galvin and Tetali, who studied the number of graph homomorphisms from $G$ to $H$ when $H$ is bipartite. We also apply our techniques to graph colorings and stable set polytopes.

22 pages. To appear in SIAM J. Discrete Math

References in corpus (4)

• The Number of Independent Sets in a Regular Graph
• Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics
• Maximizing the number of q-colorings
• Counting MSTD Sets in Finite Abelian Groups

Cited by in corpus (14)

• On replica symmetry of large deviations in random graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Three tutorial lectures on entropy and counting
• Independent Sets, Matchings, and Occupancy Fractions
• Extremes of the internal energy of the Potts model on cubic graphs
• The number of independent sets in an irregular graph
• Extremal regular graphs: the case of the infinite regular tree
• Maximizing the number of $x$-colorings of $4$-chromatic graphs
• Sub-Fibonacci behavior in numerical semigroup enumeration
• Counting colorings of a regular graph
• Maximizing $H$-colorings of connected graphs with fixed minimum degree
• Extremal H-colorings of graphs with fixed minimum degree
• Counting numerical semigroups by Frobenius number, multiplicity, and depth
• Maximizing H-colorings of a regular graph