10 papers
Jaeger-type orientations of random regular graphs
Catherine Greenhill, Mikhail Isaev, Charles Lewis
We consider -orientations, which are defined to be orientations of -regular graphs such that every vertex either has in-degree or out-degree . These generalise the ori…
Canonical labelling of random regular graphs
Mikhail Isaev, Tamás Makai, Brendan McKay +3
We prove that whenever and as , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…
On Pauling's residual entropy estimate for regular graphs with growing degree
M. Hasheminezhad, M. Isaev, B. D. McKay +1
In 1935, Pauling proposed an estimate for the number of Eulerian orientations of a graph in the context of the theoretical behaviour of water ice. The logarithm of the number of Eu…
Sandwiching between random regular graphs and ErdÅs-Rényi graphs: configuration model and unions of perfect matchings
Pu Gao, Mikhail Isaev, Xavier Perez-Gimenez
We establish new couplings among several random graph and multigraph models related to the random regular graph , including the configuration model and unions of random per…
A tail bound for cumulant series for complex functions of independent random variables
Mikhail Isaev
We obtain explicit bounds on the truncation error of the cumulant series of a bounded complex function of a random vector with independent components. The bounds are based on multi…
Asymptotic enumeration of graph factors by cumulant expansion
Mikhail Isaev, Brendan D. McKay
Let be a dense graph with good expansion properties and not too close to being bipartite. Let be a graphical degree sequence. Under very weak conditions, we fin…