7 papers · 1 filter
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…
Sharp thresholds for higher powers of Hamilton cycles in random graphs
Tamás Makai, Matija Pasch, Kalina Petrova +1
For , we establish that is a sharp threshold for the existence of the -th power of a Hamilton cycle in the binomial random graph model. Our proof…
Enumeration of regular multipartite hypergraphs
Mikhail Isaev, Tamás Makai, Brendan D. McKay
We determine the asymptotic number of regular multipartite hypergraphs, also known as multidimensional binary contingency tables, for all values of the parameters.
Enumeration of dihypergraphs with specified degrees and edge types
Catherine Greenhill, Tamás Makai
A directed hypergraph (dihypergraph) consists of a set of vertices and a set of hyperarcs, where each hyperarc is partitioned into a head and a tail. Directed hypergraphs are usefu…
Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs
Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai
We study majority dynamics on the binomial random graph with and , for some large . In this process, each vertex has a state in a…
The Size of the Giant Joint Component in a Binomial Random Double Graph
Mark Jerrum, Tamás Makai
We study the joint components in a random `double graph' that is obtained by superposing red and blue binomial random graphs on ~vertices. A joint component is a maximal set of…