Extremal regular graphs: independent sets and graph homomorphisms

DOI10.4169/AMER.MATH.MONTHLY.124.9.827zbMATH Open1391.05142arXiv1610.09210OpenAlexW2545735748MaRDI QIDQ4575432FDOQ4575432

Authors: Yufei Zhao 

Publication date: 13 July 2018

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Abstract: This survey concerns regular graphs that are extremal with respect to the number of independent sets, and more generally, graph homomorphisms. More precisely, in the family of of $d$-regular graphs, which graph $G$ maximizes/minimizes the quantity $i(G{)}^{1/v(G)}$, the number of independent sets in $G$ normalized exponentially by the size of $G$? What if $i(G)$ is replaced by some other graph parameter? We review existing techniques, highlight some exciting recent developments, and discuss open problems and conjectures for future research.

Full work available at URL: https://arxiv.org/abs/1610.09210

Recommendations

• Extremal problems for independent set enumeration
• The number of independent sets in a regular graph
• Extremal graphs for homomorphisms
• Maximum independent sets on random regular graphs
• Counting independent sets in regular hypergraphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• An inequality related to the isoperimetric inequality
• Some intersection theorems for ordered sets and graphs
• An entropy approach to the hard-core model on bipartite graphs
• The number of independent sets in a regular graph
• Hypergraphs, entropy, and inequalities
• On weighted graph homomorphisms
• Graph homomorphisms and phase transitions
• The maximum number of complete subgraphs in a graph with given maximum degree
• On replica symmetry of large deviations in random graphs
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Independent sets in regular graphs and sum-free subsets of finite groups
• Counting in two-spin models on \(d\)-regular graphs
• Best constants in Young's inequality, its converse, and its generalization to more than three functions
• The number of independent sets in a graph with small maximum degree
• Nonmonotonic behavior in hard-core and Widom-Rowlinson models
• A generalization of Hölder's inequality and some probability inequalities
• Independent sets, matchings, and occupancy fractions
• Sidorenko's conjecture, colorings and independent sets
• On the Widom–Rowlinson Occupancy Fraction in Regular Graphs
• The bipartite swapping trick on graph homomorphisms
• Maximizing \(H\)-colorings of a regular graph
• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• Bounding the partition function of spin-systems
• Counting independent sets in cubic graphs of given girth
• On the average size of independent sets in triangle-free graphs
• Graph operations and upper bounds on graph homomorphism counts
• Extremes of the internal energy of the Potts model on cubic graphs

Cited In (19)

• Counting proper colourings in 4-regular graphs via the Potts model
• The number of independent sets in an irregular graph
• Maximizing and minimizing the number of generalized colorings of trees
• Minimizing the number of independent sets in triangle-free regular graphs
• Extremal colorings and independent sets
• A proof of the upper matching conjecture for large graphs
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Extremal problems for independent set enumeration
• Counting independent sets in regular hypergraphs
• On the number of independent sets in uniform, regular, linear hypergraphs
• Toward a Nordhaus-Gaddum inequality for the number of dominating sets
• Maximizing the number of \(H\)-colorings of graphs with a fixed minimum degree
• Tight bounds on the coefficients of partition functions via stability
• A reverse Sidorenko inequality
• Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs
• Homomorphisms into loop-threshold graphs
• Extremal graphs for homomorphisms
• Diagonal Ramsey via effective quasirandomness
• Counting independent sets in cubic graphs of given girth

This page was built for publication: Extremal regular graphs: independent sets and graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575432)