2019/05/15 by Borbényi, Márton, Csikvári, Péter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1905.06215
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 (\frac\binomdd/22d/2)n. We also show that a d--regular graph with even d has always at least as many Eulerian orientations as (d/2)--regular subgraphs.