2013/05/11 by Alexander Barvinok, Barvinok, Alexander
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1305.2533
Given a complete graph with positive weights on its edges, we define the\nweight of a subset of edges as the product of weights of the edges in the\nsubset and consider sums (partition functions) of weights over subsets of\nvarious kinds: cycle covers, closed walks, spanning trees. We show that if the\nweights of the edges of the graph are within a constant factor, fixed in\nadvance, of each other then the bulk of the partition function is concentrated\non the subsets of a particularly simple structure: cycle covers with few\ncycles, walks that visit every vertex only few times, and spanning trees with\nsmall degree of every vertex. This allows us to construct a polynomial time\nalgorithm to separate graphs with many Hamiltonian cycles from graphs that are\nsufficiently far from Hamiltonian.\n