A proof of the upper matching conjecture for large graphs
| Autor: | Will Perkins, Ewan Davies, Matthew Jenssen |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Canonical ensemble
Conjecture Matching (graph theory) Degree (graph theory) 010102 general mathematics 0102 computer and information sciences Function (mathematics) Girth (graph theory) 01 natural sciences Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics Bipartite graph Matching polynomial Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series B. 151:393-416 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/j.jctb.2021.07.005 |
| Popis: | We prove that the ‘Upper Matching Conjecture’ of Friedland, Krop, and Markstrom and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every d and every large enough n divisible by 2d, a union of n / ( 2 d ) copies of the complete d -regular bipartite graph maximizes the number of independent sets and matchings of size k for each k over all d-regular graphs on n vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect