Source author record

Ian M. Wanless

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

ResearcherUnclaimed source record

Catalog footprint

Research overview

23works
5topics
4close collaborators

Published work

23 publications

preprint2021arXiv

Existence results for cyclotomic orthomorphisms

An {\em orthomorphism} over a finite field F\mathbb{F} is a permutation θ:F↦Fθ:\mathbb{F}\mapsto\mathbb{F} such that the map x↦θ(x)−xx\mapstoθ(x)-x is also a permutation of F\mathbb{F}. The orthomorphism θθ is {\em cyclotomic of index kk} if θ(0)=0θ(0)=0 and θ(x)/xθ(x)/x is constant on the cosets of a subgroup of index kk in the multiplicative group F∗\mathbb{F}^*. We say that θθ has {\em least index} kk if it is cyclotomic of index kk and not of any smaller index. We answer an open problem due to Evans by establishing for which pairs (q,k)(q,k) there exists an orthomorphism over Fq\mathbb{F}_q that is cyclotomic of least index kk. Two orthomorphisms over Fq\mathbb{F}_q are orthogonal if their difference is a permutation of Fq\mathbb{F}_q. For any list [b1,…,bn][b_1,\dots,b_n] of indices we show that if qq is large enough then Fq\mathbb{F}_q has pairwise orthogonal orthomorphisms of least indices b1,…,bnb_1,\dots,b_n. This provides a partial answer to another open problem due to Evans. For some pairs of small indices we establish exactly which fields have orthogonal orthomorphisms of those indices. We also find the number of linear orthomorphisms that are orthogonal to certain cyclotomic orthomorphisms of higher index.

preprint2021arXiv

Zero-sum flows for Steiner systems

Given a tt-(v,k,λ)(v, k, λ) design, D=(X,B)\mathcal{D}=(X,\mathcal{B}), a zero-sum nn-flow of D\mathcal{D} is a map f:B⟶{±1,…,±(n−1)}f : \mathcal{B}\longrightarrow \{\pm1,\ldots, \pm(n-1)\} such that for any point x∈Xx\in X, the sum of ff over all blocks incident with xx is zero. For a positive integer kk, we find a zero-sum kk-flow for an STS(uw)(u w) and for an STS(2v+7)(2v+7) for v≡1 (mod 4)v\equiv 1~(\mathrm{mod}~4), if there are STS(u)(u), STS(w)(w) and STS(v)(v) such that the STS(u)(u) and STS(v)(v) both have a zero-sum kk-flow. In 2015, it was conjectured that for v>7v>7 every STS(v)(v) admits a zero-sum 33-flow. Here, it is shown that many cyclic STS(v)(v) have a zero-sum 33-flow. Also, we investigate the existence of zero-sum flows for some Steiner quadruple systems.

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

preprint2020arXiv

Most binary matrices have no small defining set

Consider a matrix MM chosen uniformly at random from a class of m×nm \times n matrices of zeros and ones with prescribed row and column sums. A partially filled matrix DD is a defining\mathit{defining} set\mathit{set} for MM if MM is the unique member of its class that contains the entries in DD. The size\mathit{size} of a defining set is the number of filled entries. A critical\mathit{critical} set\mathit{set} is a defining set for which the removal of any entry stops it being a defining set. For some small fixed ε>0ε>0, we assume that n≤m=o(n1+ε)n\le m=o(n^{1+ε}), and that λ≤1/2λ\le1/2, where λλ is the proportion of entries of MM that equal 11. We also assume that the row sums of MM do not vary by more than O(n1/2+ε)\mathcal{O}(n^{1/2+ε}), and that the column sums do not vary by more than O(m1/2+ε)\mathcal{O}(m^{1/2+ε}). Under these assumptions we show that MM almost surely has no defining set of size less than λmn−O(m7/4+ε)λmn-\mathcal{O}(m^{7/4+ε}). It follows that MM almost surely has no critical set of size more than (1−λ)mn+O(m7/4+ε)(1-λ)mn+\mathcal{O}(m^{7/4+ε}). Our results generalise a theorem of Cavenagh and Ramadurai, who examined the case when λ=1/2λ=1/2 and n=m=2kn=m=2^k for an integer kk.

preprint2020arXiv

Multidimensional permanents of polystochastic matrices

A dd-dimensional matrix is called \emph{11-polystochastic} if it is non-negative and the sum over each line equals~11. Such a matrix that has a single 11 in each line and zeros elsewhere is called a \emph{11-permutation} matrix. A \emph{diagonal} of a dd-dimensional matrix of order nn is a choice of nn elements, no two in the same hyperplane. The \emph{permanent} of a dd-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order nn and dimension dd, the set of 11-polystochastic matrices forms a convex polytope that includes the 11-permutation matrices within its set of vertices. For even nn and odd dd, we give a construction for a class of 11-permutation matrices with zero permanent. Consequently, we show that the set of 11-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1))n^{n^{3/2}(1/2-o(1))} 11-permutation matrices and contains a polytope of dimension at least cn3/2cn^{3/2} for fixed c,dc,d and even n→∞n\to\infty. We also provide counterexamples to a conjecture by Taranenko about the location of local extrema of the permanent. For odd dd, we give a construction of 11-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko to provide counterexamples to a conjecture by Dow and Gibson generalising van der Waerden's conjecture to higher dimensions.

preprint2019arXiv

Covering radius in the Hamming permutation space

Let Sn\mathcal{S}_n denote the set of permutations of {1,2,…,n}\{1,2,\dots,n\}. The function f(n,s)f(n,s) is defined to be the minimum size of a subset S⊆SnS\subseteq \mathcal{S}_n with the property that for any ρ∈Snρ\in \mathcal{S}_n there exists some σ∈Sσ\in S such that the Hamming distance between ρρ and σσ is at most n−sn-s. The value of f(n,2)f(n,2) is the subject of a conjecture by Kézdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd nn case of the Kézdy-Snevily Conjecture implies the whole conjecture. We also show that f(n,2)>3n/4f(n,2)>3n/4 for all nn, that s!<f(n,s)<3s!(n−s)log⁡ns!< f(n,s)< 3s!(n-s)\log n for 1≤s≤n−21\leq s\leq n-2 and that f(n,s)>⌊2+2s−22⌋n2f(n,s)>\left\lfloor \frac{2+\sqrt{2s-2}}{2}\right\rfloor \frac{n}{2} if s≥3s\geq 3.

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 nn with n/2n/2 zeroes and n/2n/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 kk-MOFS(n)(n) is a set of kk binary frequency squares of order nn in which each pair of squares is orthogonal. A kk-MOFS(n)(n) must satisfy k≤(n−1)2k\le(n-1)^2, and any MOFS achieving this bound are said to be \emph{complete}. For any nn for which there exists a Hadamard matrix of order nn we show that there exists at least 2n2/4−O(nlog⁡n)2^{n^2/4-O(n\log n)} isomorphism classes of complete MOFS(n)(n). For 2<n≡2(mod4)2<n\equiv2\pmod4 we show that there exists a 1717-MOFS(n)(n) but no complete MOFS(n)(n). A kk-maxMOFS(n)(n) is a kk-MOFS(n)(n) that is not contained in any (k+1)(k+1)-MOFS(n)(n). By computer enumeration, we establish that there exists a kk-maxMOFS(6)(6) if and only if k∈{1,17}k\in\{1,17\} or 5≤k≤155\le k\le 15. We show that up to isomorphism there is a unique 11-maxMOFS(n)(n) if n≡2(mod4)n\equiv2\pmod4, whereas no 11-maxMOFS(n)(n) exists for n≡0(mod4)n\equiv0\pmod4. We also prove that there exists a 55-maxMOFS(n)(n) for each order n≡2(mod4)n\equiv 2\pmod{4} where n≥6n\geq 6.

preprint2019arXiv

Parity of transversals of Latin squares

We introduce a notion of parity for transversals, and use it to show that in Latin squares of order 2 mod 42 \bmod 4, the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving E1,…,EnE_1,\dots, E_n, where EiE_i is the number of diagonals of a given Latin square that contain exactly ii different symbols. Let A(i∣j)A(i\mid j) denote the matrix obtained by deleting row ii and column jj from a parent matrix AA. Define tijt_{ij} to be the number of transversals in L(i∣j)L(i\mid j), for some fixed Latin square LL. We show that tab≡tcd mod 2t_{ab}\equiv t_{cd}\bmod2 for all a,b,c,da,b,c,d and LL. Also, if LL has odd order then the number of transversals of LL equals tabt_{ab} mod 2. We conjecture that tac+tbc+tad+tbd≡0 mod 4t_{ac} + t_{bc} + t_{ad} + t_{bd} \equiv 0 \bmod 4 for all a,b,c,da,b,c,d. In the course of our investigations we prove several results that could be of interest in other contexts. For example, we show that the number of perfect matchings in a kk-regular bipartite graph on 2n2n vertices is divisible by 44 when nn is odd and k≡0 mod 4k\equiv0\bmod 4. We also show that per A(a∣c)+per A(b∣c)+per A(a∣d)+per A(b∣d)≡0 mod 4{\rm per}\, A(a \mid c)+{\rm per}\, A(b \mid c)+{\rm per}\, A(a \mid d)+{\rm per}\, A(b \mid d) \equiv 0 \bmod 4 for all a,b,c,da,b,c,d, when AA is an integer matrix of odd order with all row and columns sums equal to k≡2 mod 4k\equiv2\bmod4.

preprint2019arXiv

Perfect 1-factorisations of K16K_{16}

We report the results of a computer enumeration that found that there are 3155 perfect 1-factorisations (P1Fs) of the complete graph K16K_{16}. Of these, 89 have a non-trivial automorphism group (correcting an earlier claim of 88 by Meszka and Rosa). We also (i) describe a new invariant which distinguishes between the P1Fs of K16K_{16}, (ii) observe that the new P1Fs produce no atomic Latin squares of order 15 and (iii) record P1Fs for a number of large orders that exceed prime powers by one.

preprint2017arXiv

Covers and partial transversals of Latin squares

We define a cover of a Latin square to be a set of entries that includes at least one representative of each row, column and symbol. A cover is minimal if it does not contain any smaller cover. A partial transversal is a set of entries that includes at most one representative of each row, column and symbol. A partial transversal is maximal if it is not contained in any larger partial transversal. We explore the relationship between covers and partial transversals. We prove the following: (1) The minimum size of a cover in a Latin square of order nn is n+an+a if and only if the maximum size of a partial transversal is either n−2an-2a or n−2a+1n-2a+1. (2) A minimal cover in a Latin square of order nn has size at most μn=3(n+1/2−n+1/4)μ_n=3(n+1/2-\sqrt{n+1/4}). (3) There are infinitely many orders nn for which there exists a Latin square having a minimal cover of every size from nn to μnμ_n. (4) Every Latin square of order nn has a minimal cover of a size which is asymptotically equal to μnμ_n. (5) If 1≤k≤n/21\le k\le n/2 and n≥5n\ge5 then there is a Latin square of order nn with a maximal partial transversal of size n−kn-k. (6) For any ε>0ε>0, asymptotically almost all Latin squares have no maximal partial transversal of size less than n−n2/3+εn-n^{2/3+ε}.

preprint2015arXiv

Cycle structure of autotopisms of quasigroups and Latin squares

An autotopism of a Latin square is a triple (α,β,γ)(α,β,γ) of permutations such that the Latin square is mapped to itself by permuting its rows by αα, columns by ββ, and symbols by γγ. Let Atp(n)\mathrm{Atp}(n) be the set of all autotopisms of Latin squares of order nn. Whether a triple (α,β,γ)(α,β,γ) of permutations belongs to Atp(n)\mathrm{Atp}(n) depends only on the cycle structures of αα, ββ and γγ. We establish a number of necessary conditions for (α,β,γ)(α,β,γ) to be in Atp(n)\mathrm{Atp}(n), and use them to determine Atp(n)\mathrm{Atp}(n) for n≤17n\le17. For general nn we determine if (α,α,α)∈Atp(n)(α,α,α)\in\mathrm{Atp}(n) (that is, if αα is an automorphism of some quasigroup of order nn), provided that either αα has at most three cycles other than fixed points or that the non-fixed points of αα are in cycles of the same length.

preprint2015arXiv

Multipartite hypergraphs achieving equality in Ryser's conjecture

A famous conjecture of Ryser is that in an rr-partite hypergraph the covering number is at most r−1r-1 times the matching number. If true, this is known to be sharp for rr for which there exists a projective plane of order r−1r-1. We show that the conjecture, if true, is also sharp for the smallest previously open value, namely r=7r=7. For r∈{6,7}r\in\{6,7\}, we find the minimal number f(r)f(r) of edges in an intersecting rr-partite hypergraph that has covering number at least r−1r-1. We find that f(r)f(r) is achieved only by linear hypergraphs for r≤5r\le5, but that this is not the case for r∈{6,7}r\in\{6,7\}. We also improve the general lower bound on f(r)f(r), showing that f(r)≥3.052r+O(1)f(r)\ge 3.052r+O(1). We show that a stronger form of Ryser's conjecture that was used to prove the r=3r=3 case fails for all r>3r>3. We also prove a fractional version of the following stronger form of Ryser's conjecture: in an rr-partite hypergraph there exists a set SS of size at most r−1r-1, contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.

preprint2015arXiv

On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs

Ryser conjectured that τ≤(r−1)ντ\le(r-1)ν for rr-partite hypergraphs, where ττ is the covering number and νν is the matching number. We prove this conjecture for r≤9r\le9 in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each rr-partite hypergraph should have a cover of size (r−1)ν(r-1)ν of a particular form. We provide a counterexample to Aharoni's conjecture with r=13r=13 and ν=1ν=1. We also report a number of computational results. For r=7r=7, we find that there is no linear intersecting hypergraph that achieves the equality τ=r−1τ=r-1 in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for r∈{9,13,17}r\in\{9,13,17\}. Also, we find that r=8r=8 is the smallest value of rr for which there exists a linear intersecting rr-partite hypergraph that achieves τ=r−1τ=r-1 and is not isomorphic to a subhypergraph of a projective plane.

preprint2015arXiv

Overlapping latin subsquares and full products

We derive necessary and sufficient conditions for there to exist a latin square of order nn containing two subsquares of order aa and bb that intersect in a subsquare of order cc. We also solve the case of two disjoint subsquares. We use these results to show that: (a) A latin square of order nn cannot have more than nm(nh)/(mh)\frac nm{n \choose h}/{m\choose h} subsquares of order mm, where h=⌈(m+1)/2⌉h=\lceil(m+1)/2\rceil. Indeed, the number of subsquares of order mm is bounded by a polynomial of degree at most 2m+2\sqrt{2m}+2 in nn. (b) For all n≥5n\ge5 there exists a loop of order nn in which every element can be obtained as a product of all nn elements in some order and with some bracketing.

preprint2015arXiv

Trades in complex Hadamard matrices

A trade in a complex Hadamard matrix is a set of entries which can be changed to obtain a different complex Hadamard matrix. We show that in a real Hadamard matrix of order nn all trades contain at least nn entries. We call a trade rectangular if it consists of a submatrix that can be multiplied by some scalar c≠1c \neq 1 to obtain another complex Hadamard matrix. We give a characterisation of rectangular trades in complex Hadamard matrices of order nn and show that they all contain at least nn entries. We conjecture that all trades in complex Hadamard matrices contain at least nn entries.

preprint2014arXiv

Enumeration of MOLS of small order

We report the results of a computer investigation of sets of mutually orthogonal latin squares (MOLS) of small order. For n≤9n\le9 we 1. Determine the number of orthogonal mates for each species of latin square of order nn. 2. Calculate the proportion of latin squares of order nn that have an orthogonal mate, and the expected number of mates when a square is chosen uniformly at random. 3. Classify all sets of MOLS of order nn up to various different notions of equivalence. We also provide a triple of latin squares of order 10 that is the closest to being a set of MOLS so far found.

preprint2014arXiv

Loops with exponent three in all isotopes

It was shown by van Rees \cite{vR} that a latin square of order nn has at most n2(n−1)/18n^2(n-1)/18 latin subsquares of order 33. He conjectured that this bound is only achieved if nn is a power of 33. We show that it can only be achieved if n≡3 mod 6n\equiv3\bmod6. We also state several conditions that are equivalent to achieving the van Rees bound. One of these is that the Cayley table of a loop achieves the van Rees bound if and only if every loop isotope has exponent 33. We call such loops \emph{van Rees loops} and show that they form an equationally defined variety. We also show that (1) In a van Rees loop, any subloop of index 3 is normal, (2) There are exactly 6 nonassociative van Rees loops of order 2727 with a non-trivial nucleus and at least 1 with all nuclei trivial, (3) Every commutative van Rees loop has the weak inverse property and (4) For each van Rees loop there is an associated family of Steiner quasigroups.

preprint2012arXiv

On the Existence of Retransmission Permutation Arrays

We investigate retransmission permutation arrays (RPAs) that are motivated by applications in overlapping channel transmissions. An RPA is an n×nn\times n array in which each row is a permutation of 1,...,n{1, ..., n}, and for 1≤i≤n1\leq i\leq n, all nn symbols occur in each i×⌈ni⌉i\times\lceil\frac{n}{i}\rceil rectangle in specified corners of the array. The array has types 1, 2, 3 and 4 if the stated property holds in the top left, top right, bottom left and bottom right corners, respectively. It is called latin if it is a latin square. We show that for all positive integers nn, there exists a type-1,2,3,41,2,3,4 $\RPA(n)$ and a type-1,2 latin $\RPA(n)$.

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.

preprint2009arXiv

Transversals in Latin Squares

A latin square of order nn is an n×nn\times n array of nn symbols in which each symbol occurs exactly once in each row and column. A transversal of such a square is a set of nn entries such that no two entries share the same row, column or symbol. Transversals are closely related to the notions of complete mappings and orthomorphisms in (quasi)groups, and are fundamental to the concept of mutually orthogonal latin squares. Here we provide a brief survey of the literature on transversals. We cover (1) existence and enumeration results, (2) generalisations of transversals including partial transversals and plexes, (3) the special case when the latin square is a group table, (4) a connection with covering radii of sets of permutations. The survey includes a number of conjectures and open problems.

Research graph

See the researcher in context

Open full explorer

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.