Brendan McKay

Surge: a fast open-source chemical graph generator

Publisher: Springer Science and Business Media LLC

Date: 23-04-2022

DOI: 10.1186/S13321-022-00604-9

Abstract: Chemical structure generators are used in cheminformatics to produce or enumerate virtual molecules based on a set of boundary conditions. The result can then be tested for properties of interest, such as adherence to measured data or for their suitability as drugs. The starting point can be a potentially fuzzy set of fragments or a molecular formula. In the latter case, the generator produces the set of constitutional isomers of the given input formula. Here we present the novel constitutional isomer generator based on the canonical generation path method. uses the package to compute automorphism groups of graphs. We outline the working principles of and present benchmarking results which show that is currently the fastest structure generator. is available under a liberal open-source license.

Enumeration of Latin squares with conjugate symmetry

Publisher: Wiley

Date: 16-11-2022

DOI: 10.1002/JCD.21814

Abstract: A Latin square has six conjugate Latin squares obtained by uniformly permuting its (row, column, symbol) triples. We say that a Latin square has conjugate symmetry if at least two of its six conjugates are equal. We enumerate Latin squares with conjugate symmetry and classify them according to several common notions of equivalence. We also do similar enumerations under additional hypotheses, such as assuming the Latin square is reduced, diagonal, idempotent or unipotent. Our data corrected an error in earlier literature and suggested several patterns that we then found proofs for, including (1) the number of isomorphism classes of semisymmetric idempotent Latin squares of order equals the number of isomorphism classes of semisymmetric unipotent Latin squares of order , and (2) suppose and are totally symmetric Latin squares of order . If and are paratopic then and are isomorphic.

Degree sequences of sufficiently dense random uniform hypergraphs

Publisher: Cambridge University Press (CUP)

Date: 15-08-2022

DOI: 10.1017/S0963548322000190

Abstract: We find an asymptotic enumeration formula for the number of simple $r$ -uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$ -uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$ -uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.

The r-switching-stable graphs

Publisher: Elsevier BV

Date: 08-2019

DOI: 10.1016/J.DAM.2018.12.013

Asymptotic enumeration of non-uniform linear hypergraphs

Publisher: University of Zielona Góra, Poland

Date: 2019

DOI: 10.7151/DMGT.2246

R(5,5)≤48

Publisher: Wiley

Date: 05-02-2018

DOI: 10.1002/JGT.22235

Sandwiching dense random regular graphs between binomial random graphs

Publisher: Springer Science and Business Media LLC

Date: 06-08-2022

DOI: 10.1007/S00440-022-01157-6

Abstract: Kim and Vu made the following conjecture ( Advances in Mathematics , 2004): if $$d\\gg \\log n$$ d ≫ log n , then the random d -regular graph $${\\mathscr {G}}(n,d)$$ G ( n , d ) can asymptotically almost surely be “sandwiched” between $${\\mathscr {G}}(n,p_1)$$ G ( n , p 1 ) and $${\\mathscr {G}}(n,p_2)$$ G ( n , p 2 ) where $$p_1$$ p 1 and $$p_2$$ p 2 are both $$(1+o(1))d/n$$ ( 1 + o ( 1 ) ) d / n . They proved this conjecture for $$\\log n\\ll d\\leqslant n^{1/3-o(1)}$$ log n ≪ d ⩽ n 1 / 3 - o ( 1 ) , with a defect in the sandwiching: $${\\mathscr {G}}(n,d)$$ G ( n , d ) contains $${\\mathscr {G}}(n,p_1)$$ G ( n , p 1 ) perfectly, but is not completely contained in $${\\mathscr {G}}(n,p_2)$$ G ( n , p 2 ) . The embedding $${\\mathscr {G}}(n,p_1) \\subseteq {\\mathscr {G}}(n,d)$$ G ( n , p 1 ) ⊆ G ( n , d ) was improved by Dudek, Frieze, Ruciński and Šileikis to $$d=o(n)$$ d = o ( n ) . In this paper, we prove Kim–Vu’s sandwich conjecture, with perfect containment on both sides, for all d where $$\\min \\{d, n-d\\}\\gg n/\\sqrt{\\log n}$$ min { d , n - d } ≫ n / log n . The sandwich theorem allows translation of many results from $${\\mathscr {G}}(n,p)$$ G ( n , p ) to $${\\mathscr {G}}(n,d)$$ G ( n , d ) such as Hamiltonicity, the chromatic number, the diameter, etc. It also allows translation of threshold functions of phase transitions from $${\\mathscr {G}}(n,p)$$ G ( n , p ) to bond percolation of $${\\mathscr {G}}(n,d)$$ G ( n , d ) . In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability of small subgraph appearances in a random factor of a pseudorandom graph, which is of independent interest.

Correction: Sandwiching dense random regular graphs between binomial random graphs

Publisher: Springer Science and Business Media LLC

Date: 08-2023

DOI: 10.1007/S00440-023-01221-9

Australian National University

Location: Australia

View Organisation

Discovery Projects - Grant ID: DP0450294

Start Date: 07-2004

End Date: 07-2008

Amount: $250,743.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP190100977

Start Date: 05-2019

End Date: 06-2023

Amount: $420,000.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP140101519

Start Date: 02-2014

End Date: 12-2018

Amount: $385,000.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP210102273

Start Date: 2022

End Date: 12-2024

Amount: $407,167.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP0986827

Start Date: 2009

End Date: 06-2014

Amount: $270,000.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP1093320

Start Date: 2010

End Date: 12-2013

Amount: $150,000.00

Funder: Australian Research Council

Discovery Projects - Grant ID: DP0208238

Start Date: 2002

End Date: 12-2007

Amount: $515,667.00

Funder: Australian Research Council