Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903686 | Journal of Combinatorial Theory, Series A | 2018 | 30 Pages |
Abstract
As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of q-colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least 5.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts,