Source author record

Nicholas J. Cavenagh

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Mutually orthogonal cycle systems

An ${\ell}$ -cycle system ${\mathcal F}$ of a graph $Γ$ is a set of ${\ell}$ -cycles which partition the edge set of $Γ$ . Two such cycle systems ${\mathcal F}$ and ${\mathcal F}'$ are said to be {\em orthogonal} if no two distinct cycles from ${\mathcal F}\cup {\mathcal F}'$ share more than one edge. Orthogonal cycle systems naturally arise from face $2$ -colourable polyehdra and in higher genus from Heffter arrays with certain orderings. A set of pairwise orthogonal $\ell$ -cycle systems of $Γ$ is said to be a set of mutually orthogonal cycle systems of $Γ$ . Let $μ(\ell,n)$ (respectively, $μ'(\ell,n)$ ) be the maximum integer $μ$ such that there exists a set of $μ$ mutually orthogonal (cyclic) $\ell$ -cycle systems of the complete graph $K_n$ . We show that if $\ell\geq 4$ is even and $n\equiv 1\pmod{2\ell}$ , then $μ'(\ell,n)$ , and hence $μ(\ell,n)$ , is bounded below by a constant multiple of $n/\ell^2$ . In contrast, we obtain the following upper bounds: $μ(\ell,n)\leq n-2$ ; $μ(\ell,n)\leq (n-2)(n-3)/(2(\ell-3))$ when $\ell \geq 4$ ; $μ(\ell,n)\leq 1$ when $\ell>n/\sqrt{2}$ ; and $μ'(\ell,n)\leq n-3$ when $n \geq 4$ . We also obtain computational results for small values of $n$ and $\ell$ .

preprint2020arXiv

Maximal sets of mutually orthogonal frequency squares

A frequency square is a square matrix in which each row and column is a permutation of the same multiset of symbols. A frequency square is of type $(n;λ)$ if it contains $n/λ$ symbols, each of which occurs $λ$ times per row and $λ$ times per column. In the case when $λ=n/2$ we refer to the frequency square as binary. A set of $k$ -MOFS $(n;λ)$ is a set of $k$ frequency squares of type $(n;λ)$ such that when any two of the frequency squares are superimposed, each possible ordered pair occurs equally often. A set of $k$ -maxMOFS $(n;λ)$ is a set of $k$ -MOFS $(n;λ)$ that is not contained in any set of $(k+1)$ -MOFS $(n;λ)$ . For even $n$ , let $μ(n)$ be the smallest $k$ such that there exists a set of $k$ -maxMOFS $(n;n/2)$ . It was shown in [Electron. J. Combin. 27(3) (2020), P3.7] that $μ(n)=1$ if $n/2$ is odd and $μ(n)>1$ if $n/2$ is even. Extending this result, we show that if $n/2$ is even, then $μ(n)>2$ . Also, we show that whenever $n$ is divisible by a particular function of $k$ , there does not exist a set of $k'$ -maxMOFS $(n;n/2)$ for any $k'\le k$ . In particular, this means that $\limsup μ(n)$ is unbounded. Nevertheless we can construct infinite families of maximal binary MOFS of fixed cardinality. More generally, let $q=p^u$ be a prime power and let $p^v$ be the highest power of $p$ that divides $n$ . If $0\le v-uh<u/2$ for $h\ge1$ then we show that there exists a set of $(q^h-1)^2/(q-1)$ -maxMOFS $(n;n/q)$ .

preprint2019arXiv

Mutually orthogonal binary frequency squares

A \emph{frequency square} is a matrix in which each row and column is a permutation of the same multiset of symbols. We consider only {\em binary} frequency squares of order $n$ with $n/2$ zeroes and $n/2$ ones in each row and column. Two such frequency squares are \emph{orthogonal} if, when superimposed, each of the 4 possible ordered pairs of entries occurs equally often. In this context we say that a $k$ -MOFS $(n)$ is a set of $k$ binary frequency squares of order $n$ in which each pair of squares is orthogonal. A $k$ -MOFS $(n)$ must satisfy $k\le(n-1)^2$ , and any MOFS achieving this bound are said to be \emph{complete}. For any $n$ for which there exists a Hadamard matrix of order $n$ we show that there exists at least $2^{n^2/4-O(n\log n)}$ isomorphism classes of complete MOFS $(n)$ . For $2<n\equiv2\pmod4$ we show that there exists a $17$ -MOFS $(n)$ but no complete MOFS $(n)$ . A $k$ -maxMOFS $(n)$ is a $k$ -MOFS $(n)$ that is not contained in any $(k+1)$ -MOFS $(n)$ . By computer enumeration, we establish that there exists a $k$ -maxMOFS $(6)$ if and only if $k\in\{1,17\}$ or $5\le k\le 15$ . We show that up to isomorphism there is a unique $1$ -maxMOFS $(n)$ if $n\equiv2\pmod4$ , whereas no $1$ -maxMOFS $(n)$ exists for $n\equiv0\pmod4$ . We also prove that there exists a $5$ -maxMOFS $(n)$ for each order $n\equiv 2\pmod{4}$ where $n\geq 6$ .

preprint2016arXiv

Orthogonal trades in complete sets of MOLS

Let $B_p$ be the Latin square given by the addition table for the integers modulo an odd prime $p$ . Here we consider the properties of Latin trades in $B_p$ which preserve orthogonality with one of the $p-1$ MOLS given by the finite field construction. We show that for certain choices of the orthogonal mate, there is a lower bound logarithmic in $p$ for the number of times each symbol occurs in such a trade, with an overall lower bound of $(\log{p})^2/\log\log{p}$ for the size of such a trade. Such trades imply the existence of orthomorphisms of the cyclic group which differ from a linear orthomorphism by a small amount. We also show that any transversal in $B_p$ hits the main diagonal either $p$ or at most $p-\log_2{p}-1$ times. Finally, if $p\equiv 1\mod{6}$ we show the existence of Latin square containing a $2\times 2$ subsquare which is orthogonal to $B_p$ .

preprint2016arXiv

There are asymptotically the same number of Latin squares of each parity

A Latin square is reduced if its first row and column are in natural order. For Latin squares of a particular order $n$ there are four possible different parities. We confirm a conjecture of Stones and Wanless by showing asymptotic equality between the numbers of reduced Latin squares of each possible parity as the order $n\rightarrow\infty$ .

preprint2009arXiv

Latin trades in groups defined on planar triangulations

For a finite triangulation of the plane with faces properly coloured white and black, let A be the abelian group constructed by labelling the vertices with commuting indeterminates and adding relations which say that the labels around each white triangle add to the identity. We show that A has free rank exactly two. Let A* be the torsion subgroup of A, and B* the corresponding group for the black triangles. We show that A* and B* have the same order, and conjecture that they are isomorphic. For each spherical latin trade W, we show there is a unique disjoint mate B such that (W,B) is a connected and separated bitrade. The bitrade (W,B) is associated with a two-colourable planar triangulation and we show that W can be embedded in A*, thereby proving a conjecture due to Cavenagh and Drapal. The proof involves constructing a (0,1) presentation matrix whose permanent and determinant agree up to sign. The Smith Normal Form of this matrix determines A*, so there is an efficient algorithm to construct the embedding. Contrasting with the spherical case, for each genus g>0 we construct a latin trade which is not embeddable in any group and another that is embeddable in a cyclic group. We construct a sequence of spherical latin trades which cannot be embedded in any family of abelian groups whose torsion ranks are bounded. Also, we show that any trade that can be embedded in a finitely generated abelian group can be embedded in a finite abelian group. As a corollary, no trade can be embedded in a free abelian group.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.