Counting degree-constrained subgraphs and orientations

DOI10.1016/J.DISC.2020.111842MaRDI QIDQ2174586zbMATH OpenOpenAlexFDO

Authors Márton Borbényi, Péter Csikvári

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Eulerian orientationsgauge transformationshalf graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Eulerian and Hamiltonian graphs (05C45)

Abstract: The goal of this short paper to advertise the method of gauge transformations (aka holographic reduction, reparametrization) that is well-known in statistical physics and computer science, but less known in combinatorics. As an application of it we give a new proof of a theorem of A. Schrijver asserting that the number of Eulerian orientations of a $d$--regular graph on $n$ vertices with even $d$ is at least $$. We also show that a $d$--regular graph with even $d$ has always at least as many Eulerian orientations as $(d/2)$--regular subgraphs.

Recommendations

• On the number of Eulerian orientations of a graph
• scientific article; zbMATH DE number 742958
• Counting planar Eulerian orientations
• A short survey on stable polynomials, orientations and matchings
• scientific article; zbMATH DE number 691480

Cites work

• Basis collapse in holographic algorithms
• Bounds on the number of Eulerian orientations
• Complexity Dichotomies for Counting Problems
• Expressiveness of matchgates.
• Holographic Algorithms
• Holographic algorithms without matchgates
• Holographic algorithms: from art to science
• Holographic Algorithms: The Power of Dimensionality Resolved
• scientific article; zbMATH DE number 2163508 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• scientific article; zbMATH DE number 742958 (Why is no real title available?)
• Loop calculus in statistical physics and information science
• Loop series for discrete statistical models on graphs
• On Symmetric Signatures in Holographic Algorithms
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Tree-based reparameterization framework for analysis of sum-product and related algorithms

Cited in

(6)

• A short survey on stable polynomials, orientations and matchings
• Random cluster model on regular graphs
• Counting restricted orientations of random graphs
• A Gaussian integral that counts regular graphs
• Counting degree-constrained orientations
• Covers, orientations and factors

This page was built for publication: Counting degree-constrained subgraphs and orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174586)