Extremal Regular Graphs: Independent Sets and Graph Homomorphisms

DOI10.4169/amer.math.monthly.124.9.827zbMath1391.05142arXiv1610.09210OpenAlexW2545735748MaRDI QIDQ4575432

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

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

Related Items (16)

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

Cites Work

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

This page was built for publication: Extremal Regular Graphs: Independent Sets and Graph Homomorphisms