Extremal regular graphs: independent sets and graph homomorphisms

DOI10.4169/AMER.MATH.MONTHLY.124.9.827MaRDI QIDQ4575432zbMATH OpenOpenAlexFDO

Authors Yufei Zhao

Publication date 13 July 2018

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

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

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)

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.

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

Cites work

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

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
• A reverse Sidorenko inequality
• Tight bounds on the coefficients of partition functions via stability
• Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs
• Homomorphisms into loop-threshold graphs
• Extremal graphs for homomorphisms
• Counting independent sets in cubic graphs of given girth
• Diagonal Ramsey via effective quasirandomness

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)