80 results on '"05B15"'
Search Results
2. Diagonal groups and arcs over groups
- Author
-
Michael Kinyon, Cheryl E. Praeger, Peter J. Cameron, R. A. Bailey, University of St Andrews. Centre for Interdisciplinary Research in Computational Algebra, University of St Andrews. Statistics, and University of St Andrews. Pure Mathematics
- Subjects
Diagonal group ,T-NDAS ,Diagonal ,Mathematics - Statistics Theory ,Group Theory (math.GR) ,Statistics Theory (math.ST) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,QA Mathematics ,Diagonal semilattice ,QA ,Frobenius group ,Mathematics ,Applied Mathematics ,Foundation (engineering) ,020206 networking & telecommunications ,Arc ,language.human_language ,Computer Science Applications ,Algebra ,05B15 ,010201 computation theory & mathematics ,Research council ,Orthogonal array ,language ,Combinatorics (math.CO) ,Portuguese ,Mathematics - Group Theory - Abstract
In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for $$m\ge 2$$ m ≥ 2 , a set of $$m+1$$ m + 1 partitions of a set $$\Omega $$ Ω , any m of which are the minimal non-trivial elements of a Cartesian lattice, either form a Latin square (if $$m=2$$ m = 2 ), or generate a join-semilattice of dimension m associated with a diagonal group over a base group G. In this paper we investigate what happens if we have $$m+r$$ m + r partitions with $$r\ge 2$$ r ≥ 2 , any m of which are minimal elements of a Cartesian lattice. If $$m=2$$ m = 2 , this is just a set of mutually orthogonal Latin squares. We consider the case where all these squares are isotopic to Cayley tables of groups, and give an example to show the groups need not be all isomorphic. For $$m>2$$ m > 2 , things are more restricted. Any $$m+1$$ m + 1 of the partitions generate a join-semilattice admitting a diagonal group over a group G. It may be that the groups are all isomorphic, though we cannot prove this. Under an extra hypothesis, we show that G must be abelian and must have three fixed-point-free automorphisms whose product is the identity. (We describe explicitly all abelian groups having such automorphisms.) Under this hypothesis, the structure gives an orthogonal array, and conversely in some cases. If the group is cyclic of prime order p, then the structure corresponds exactly to an arc of cardinality $$m+r$$ m + r in the $$(m-1)$$ ( m - 1 ) -dimensional projective space over the field with p elements, so all known results about arcs are applicable. More generally, arcs over a finite field of order q give examples where G is the elementary abelian group of order q. These examples can be lifted to non-elementary abelian groups using p-adic techniques.
- Published
- 2021
3. Construction of the mutually orthogonal extraordinary supersquares
- Author
-
Ghiu Cristian and Ghiu Iulia
- Subjects
05b15 ,12e20 ,latin squares ,finite fields ,Mathematics ,QA1-939 - Published
- 2014
- Full Text
- View/download PDF
4. On Computing the Number of Latin Rectangles.
- Author
-
Stones, Rebecca, Lin, Sheng, Liu, Xiaoguang, and Wang, Gang
- Subjects
- *
RECTANGLES , *COMPUTER systems , *PARALLELOGRAMS , *SMALL divisors , *MATHEMATICS - Abstract
Doyle (circa 1980) found a formula for the number of $$k \times n$$ Latin rectangles $$L_{k,n}$$ . This formula remained dormant until it was recently used for counting $$k \times n$$ Latin rectangles, where $$k \in \{4,5,6\}$$ . We give a formal proof of Doyle's formula for arbitrary k. We also improve a previous implementation of this formula, which we use to find $$L_{k,n}$$ when $$k=4$$ and $$n \le 150$$ , when $$k=5$$ and $$n \le 40$$ and when $$k=6$$ and $$n \le 15$$ . Motivated by computational data for $$3 \le k \le 6$$ , some research problems and conjectures about the divisors of $$L_{k,n}$$ are presented. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
5. Maximal sets of mutually orthogonal frequency squares
- Author
-
Nicholas J. Cavenagh, Adam Mammoliti, and Ian M. Wanless
- Subjects
Applied Mathematics ,0102 computer and information sciences ,Function (mathematics) ,Type (model theory) ,Lambda ,01 natural sciences ,Square matrix ,Square (algebra) ,Computer Science Applications ,Combinatorics ,010104 statistics & probability ,Permutation ,05B15 ,010201 computation theory & mathematics ,Ordered pair ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Prime power ,Mathematics - Abstract
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;\lambda )$$ if it contains $$n/\lambda $$ symbols, each of which occurs $$\lambda $$ times per row and $$\lambda $$ times per column. In the case when $$\lambda =n/2$$ we refer to the frequency square as binary. A set of k-MOFS $$(n;\lambda )$$ is a set of k frequency squares of type $$(n;\lambda )$$ such that when any two of the frequency squares are superimposed, each possible ordered pair occurs equally often. A set of k-maxMOFS $$(n;\lambda )$$ is a set of k-MOFS $$(n;\lambda )$$ that is not contained in any set of $$(k+1)$$ -MOFS $$(n;\lambda )$$ . For even n, let $$\mu (n)$$ be the smallest k such that there exists a set of k-maxMOFS(n; n/2). It was shown in Britz et al. (Electron. J. Combin. 27(3):#P3.7, 26 pp, 2020) that $$\mu (n)=1$$ if n/2 is odd and $$\mu (n)>1$$ if n/2 is even. Extending this result, we show that if n/2 is even, then $$\mu (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'\leqslant k$$ . In particular, this means that $$\limsup \mu (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\leqslant v-uh
- Published
- 2020
- Full Text
- View/download PDF
6. A lower bound on HMOLS with equal sized holes
- Author
-
Michael Bailey, Peter J. Dukes, and Coen del Valle
- Subjects
Matrix difference equation ,Algebra and Number Theory ,Applied Mathematics ,010102 general mathematics ,General Engineering ,0102 computer and information sciences ,Graeco-Latin square ,01 natural sciences ,Upper and lower bounds ,Theoretical Computer Science ,Combinatorics ,symbols.namesake ,Finite field ,05B15 ,010201 computation theory & mathematics ,Product (mathematics) ,symbols ,FOS: Mathematics ,Mathematics - Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,0101 mathematics ,Equipartition theorem ,Mathematics - Abstract
It is known that N ( n ) , the maximum number of mutually orthogonal latin squares of order n, satisfies the lower bound N ( n ) ≥ n 1 / 14.8 for large n. For h ≥ 2 , relatively little is known about the quantity N ( h n ) , which denotes the maximum number of ‘HMOLS’ or mutually orthogonal latin squares having a common equipartition into n holes of a fixed size h. We generalize a difference matrix method that had been used previously for explicit constructions of HMOLS. An estimate of R.M. Wilson on higher cyclotomic numbers guarantees our construction succeeds in suitably large finite fields. Feeding this into a generalized product construction, we are able to establish the lower bound N ( h n ) ≥ ( log n ) 1 / δ for any δ > 2 and all n > n 0 ( h , δ ) .
- Published
- 2020
- Full Text
- View/download PDF
7. Enumerating extensions of mutually orthogonal Latin squares
- Author
-
Tibor Szabó, Simona Boyadzhiyska, and Shagnik Das
- Subjects
Class (set theory) ,Gerechte designs ,500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik ,0102 computer and information sciences ,01 natural sciences ,Combinatorics ,symbols.namesake ,Latin square ,FOS: Mathematics ,Enumeration ,Mathematics - Combinatorics ,0101 mathematics ,Mathematics ,Orthogonal mates ,Sequence ,Applied Mathematics ,010102 general mathematics ,Graeco-Latin square ,Computer Science Applications ,Latin squares ,05B15 ,010201 computation theory & mathematics ,Ordered pair ,symbols ,Combinatorics (math.CO) ,Constant (mathematics) - Abstract
Two $n \times n$ Latin squares $L_1, L_2$ are said to be orthogonal if, for every ordered pair $(x,y)$ of symbols, there are coordinates $(i,j)$ such that $L_1(i,j) = x$ and $L_2(i,j) = y$. A $k$-MOLS is a sequence of $k$ pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed $k$, log-asymptotically tight bounds on the number of $k$-MOLS. To study the situation when $k$ grows with $n$, we bound the number of ways a $k$-MOLS can be extended to a $(k+1)$-MOLS. These bounds are again tight for constant $k$, and allow us to deduce upper bounds on the total number of $k$-MOLS for all $k$. These bounds are close to tight even for $k$ linear in $n$, and readily generalize to the broader class of gerechte designs, which include Sudoku squares., 18 pages
- Published
- 2020
8. Small Latin arrays have a near transversal
- Author
-
Darcy Best, Kyle Pula, and Ian M. Wanless
- Subjects
010102 general mathematics ,Diagonal ,Mathematics::History and Overview ,Order (ring theory) ,0102 computer and information sciences ,Row and column spaces ,01 natural sciences ,Upper and lower bounds ,Combinatorics ,Matrix (mathematics) ,Transversal (geometry) ,05B15 ,010201 computation theory & mathematics ,Latin square ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,No symbol ,Mathematics - Abstract
A Latin array is a matrix of symbols in which no symbol occurs more than once within a row or within a column. A diagonal of an $n\times n$ array is a selection of $n$ cells taken from different rows and columns of the array. The weight of a diagonal is the number of different symbols on it. We show via computation that every Latin array of order $n\le11$ has a diagonal of weight at least $n-1$. A corollary is the existence of near transversals in Latin squares of these orders. More generally, for all $k\le20$ we compute a lower bound on the order of any Latin array that does not have a diagonal of weight at least $n-k$.
- Published
- 2019
9. Covers and partial transversals of Latin squares
- Author
-
Ian M. Wanless, Trent G. Marbach, Rebecca J. Stones, and Darcy Best
- Subjects
Applied Mathematics ,Order (ring theory) ,0102 computer and information sciences ,01 natural sciences ,Computer Science Applications ,Combinatorics ,Transversal (geometry) ,05B15 ,Cover (topology) ,010201 computation theory & mathematics ,Latin square ,FOS: Mathematics ,Mathematics - Combinatorics ,Maximum size ,Combinatorics (math.CO) ,Nuclear Experiment ,Mathematics - Abstract
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 n is $$n+a$$ if and only if the maximum size of a partial transversal is either $$n-2a$$ or $$n-2a+1$$ . (2) A minimal cover in a Latin square of order n has size at most $$\mu _n=3(n+1/2-\sqrt{n+1/4})$$ . (3) There are infinitely many orders n for which there exists a Latin square having a minimal cover of every size from n to $$\mu _n$$ . (4) Every Latin square of order n has a minimal cover of a size which is asymptotically equal to $$\mu _n$$ . (5) If $$1\leqslant k\leqslant n/2$$ and $$n\geqslant 5$$ then there is a Latin square of order n with a maximal partial transversal of size $$n-k$$ . (6) For any $$\varepsilon >0$$ , asymptotically almost all Latin squares have no maximal partial transversal of size less than $$n-n^{2/3+\varepsilon }$$ .
- Published
- 2018
10. Latin squares with maximal partial transversals of many lengths
- Author
-
Adam Mammoliti, Anthony B. Evans, and Ian M. Wanless
- Subjects
Finite group ,Group (mathematics) ,010102 general mathematics ,0102 computer and information sciences ,Combinatorial group theory ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Transversal (geometry) ,05B15 ,Computational Theory and Mathematics ,Cayley table ,010201 computation theory & mathematics ,Latin square ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,0101 mathematics ,Constant (mathematics) ,Mathematics - Abstract
A partial transversal T of a Latin square L is a set of entries of L in which each row, column and symbol is represented at most once. A partial transversal is maximal if it is not contained in a larger partial transversal. Any maximal partial transversal of a Latin square of order n has size at least ⌈ n 2 ⌉ and at most n. We say that a Latin square is omniversal if it possesses a maximal partial transversal of all plausible sizes and is near-omniversal if it possesses a maximal partial transversal of all plausible sizes except one. Evans (2019) showed that omniversal Latin squares of order n exist for any odd n ≠ 3 . By extending this result, we show that an omniversal Latin square of order n exists if and only if n ∉ { 3 , 4 } and n ≢ 2 ( mod 4 ) . Furthermore, we show that near-omniversal Latin squares exist for all orders n ≡ 2 ( mod 4 ) . Finally, we show that no non-trivial finite group has an omniversal Cayley table, and only 15 finite groups have a near-omniversal Cayley table. In fact, as n grows, Cayley tables of groups of order n miss a constant fraction of the plausible sizes of maximal partial transversals. In the course of proving this, we partially solve the following interesting problem in combinatorial group theory. Suppose that we have two finite subsets R , C ⊆ G of a group G such that | { r c : r ∈ R , c ∈ C } | = m . How large do | R | and | C | need to be (in terms of m) to be certain that R ⊆ x H and C ⊆ H y for some subgroup H of order m in G, and x , y ∈ G ?
- Published
- 2021
11. Transversals in Latin Arrays with Many Distinct Symbols
- Author
-
Darcy Best, Tim E. Wilson, David R. Wood, Kevin Hendrey, and Ian M. Wanless
- Subjects
Selection (relational algebra) ,Computation ,Mathematics::History and Overview ,Order (ring theory) ,0102 computer and information sciences ,01 natural sciences ,Combinatorics ,010104 statistics & probability ,Transversal (geometry) ,05B15 ,010201 computation theory & mathematics ,Transpose ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Nuclear Experiment ,Row ,No symbol ,Mathematics - Abstract
An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an $n\times n$ array is a selection of $n$ different symbols from different rows and different columns. We prove that every $n \times n$ Latin array containing at least $(2-\sqrt{2}) n^2$ distinct symbols has a transversal. Also, every $n \times n$ row-Latin array containing at least $\frac14(5-\sqrt{5})n^2$ distinct symbols has a transversal. Finally, we show by computation that every Latin array of order $7$ has a transversal, and we describe all smaller Latin arrays that have no transversal.
- Published
- 2017
12. On the OA(1536,13,2,7) and related orthogonal arrays
- Author
-
Denis S. Krotov
- Subjects
FOS: Computer and information sciences ,Discrete mathematics ,Discrete Mathematics (cs.DM) ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,05B15 ,010201 computation theory & mathematics ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Partition (number theory) ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Orthogonal array ,Quotient ,Mathematics ,Computer Science - Discrete Mathematics - Abstract
With a computer-aided approach based on the connection with equitable partitions, we establish the uniqueness of the orthogonal array OA$(1536,13,2,7)$, constructed in [D.G.Fon-Der-Flaass. Perfect $2$-Colorings of a Hypercube, Sib. Math. J. 48 (2007), 740-745] as an equitable partition of the $13$-cube with quotient matrix $[[0,13],[3,10]]$. By shortening the OA$(1536,13,2,7)$, we obtain $3$ inequivalent orthogonal arrays OA$(768,12,2,6)$, which is a complete classification for these parameters too. After our computing, the first parameters of unclassified binary orthogonal arrays OA$(N,n,2,t)$ attending the Friedman bound $N\ge 2^n(1-n/2(t+1))$ are OA$(2048,14,2,7)$. Such array can be obtained by puncturing any binary $1$-perfect code of length $15$. We construct orthogonal arrays with these and similar parameters OA$(N=2^{n-m+1},n=2^m-2,2,t=2^{m-1}-1)$, $m\ge 4$, that are not punctured $1$-perfect codes. Additionally, we prove that any orthogonal array OA$(N,n,2,t)$ with even $t$ attending the bound $N \ge 2^n(1-(n+1)/2(t+2))$ induces an equitable $3$-partition of the $n$-cube., 18pp. V.2: revised accepted version; the title was changed
- Published
- 2019
13. Decompositions into spanning rainbow structures
- Author
-
Alexey Pokrovskiy, Benny Sudakov, and Richard Montgomery
- Subjects
Quadratic growth ,Conjecture ,Spanning tree ,Mathematics::Combinatorics ,05B15 (primary) ,General Mathematics ,Complete graph ,ems ,Rainbow ,Disjoint sets ,Combinatorics ,symbols.namesake ,05B15 ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Euler's formula ,symbols ,Bipartite graph ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics - Abstract
A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back more than two hundred years to the work of Euler on Latin squares and has been the focus of extensive research ever since. Euler posed a problem equivalent to finding properly $n$-edge-coloured complete bipartite graphs $K_{n,n}$ which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of $K_{n,n}$ without even a single rainbow perfect matching, the theme of this paper is to show that with some very weak additional constraints one can find many disjoint rainbow perfect matchings. In particular, we prove that if some fraction of the colour classes have at most $(1-o(1)) n$ edges then one can nearly-decompose the edges of $K_{n,n}$ into edge-disjoint perfect rainbow matchings. As an application of this, we establish in a very strong form a conjecture of Akbari and Alipour and asymptotically prove a conjecture of Barat and Nagy. Both these conjectures concern rainbow perfect matchings in edge-colourings of $K_{n,n}$ with quadratically many colours. Using our techniques, we also prove a number of results on near-decompositions of graphs into other rainbow structures like Hamiltonian cycles and spanning trees. Most notably, we prove that any properly coloured complete graph can be nearly-decomposed into spanning rainbow trees. This asymptotically proves the Brualdi-Hollingsworth and Kaneko-Kano-Suzuki conjectures which predict that a perfect decomposition should exist under the same assumptions.
- Published
- 2019
14. Enumerating partial Latin rectangles
- Author
-
Raúl M. Falcón and Rebecca J. Stones
- Subjects
Mathematics::Functional Analysis ,Monomial ,Lemma (mathematics) ,Mathematics::Combinatorics ,Degree (graph theory) ,Mathematics::Number Theory ,Applied Mathematics ,Algebraic geometry ,Chromatic polynomial ,Theoretical Computer Science ,Combinatorics ,Set (abstract data type) ,Mathematics::Group Theory ,Computational Theory and Mathematics ,Symmetric polynomial ,05B15 ,FOS: Mathematics ,Mathematics - Combinatorics ,Mathematics::Metric Geometry ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,Isomorphism ,Combinatorics (math.CO) ,Mathematics - Abstract
This paper deals with distinct computational methods to enumerate the set $\mathrm{PLR}(r,s,n;m)$ of $r \times s$ partial Latin rectangles on $n$ symbols with $m$ non-empty cells. For fixed $r$, $s$, and $n$, we prove that the size of this set is a symmetric polynomial of degree $3m$, and we determine the leading terms (the monomials of degree $3m$ through $3m-9$) using inclusion-exclusion. For $m \leq 13$, exact formulas for these symmetric polynomials are determined using a chromatic polynomial method. Adapting Sade's method for enumerating Latin squares, we compute the exact size of $\mathrm{PLR}(r,s,n;m)$, for all $r \leq s \leq n \leq 7$, and all $r \leq s \leq 6$ when $n=8$. Using an algebraic geometry method together with Burnside's Lemma, we enumerate isomorphism, isotopism, and main classes when $r \leq s \leq n \leq 6$. Numerical results have been cross-checked where possible., Comment: 36 pages, 2 figures, 15 tables
- Published
- 2019
- Full Text
- View/download PDF
15. Computing autotopism groups of partial Latin rectangles: A pilot study
- Author
-
Daniel Kotlar, Trent G. Marbach, Raúl M. Falcón, Rebecca J. Stones, Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII), and Junta de Andalucía
- Subjects
Autotopism ,Transitive relation ,Backtracking ,Group (mathematics) ,Computational Mechanics ,Latin square ,Block matrix ,Partial Latin rectangle ,Symbol (chemistry) ,Combinatorics ,Computational Mathematics ,Computational Theory and Mathematics ,05B15 ,Homogeneous space ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Invariant (mathematics) ,Graph automorphism ,Mathematics - Abstract
Computing the autotopism group of a partial Latin rectangle can be performed in a variety of ways. This pilot study has two aims: (a) to compare these methods experimentally, and (b) to identify the design goals one should have in mind for developing practical software. To this end, we compare six families of algorithms (two backtracking methods and four graph automorphism methods), with and without the use of entry invariants, on two test suites. We consider two entry invariants: one determined by the frequencies of row, column, and symbol representatives, and one determined by $2 \times 2$ submatrices. We find: (a) with very few entries, many symmetries often exist, and these should be identified mathematically rather than computationally, (b) with an intermediate number of entries, a quick-to-compute entry invariant was effective at reducing the need for computation, (c) with an almost-full partial Latin rectangle, more sophisticated entry invariants are needed, and (d) the performance for (full) Latin squares is significantly poorer than other partial Latin rectangles of comparable size, obstructed by the existence of Latin squares with large (possibly transitive) autotopism groups., Comment: 16 pages, 5 figures, 1 table
- Published
- 2019
16. Difference Covering Arrays and Pseudo-Orthogonal Latin Squares
- Author
-
Fatih Demirkale, Diane Donovan, Abdollah Khodkar, Asha Rao, and Joanne L. Hall
- Subjects
Discrete mathematics ,Design of experiments ,Spectrum (functional analysis) ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Graeco-Latin square ,01 natural sciences ,Theoretical Computer Science ,Connection (mathematics) ,Combinatorics ,symbols.namesake ,05B15 ,010201 computation theory & mathematics ,Software testing ,Latin square ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,Mathematics ,Data compression - Abstract
Difference arrays are used in applications such as software testing, authentication codes and data compression. Pseudo-orthogonal Latin squares are used in experimental designs. A special class of pseudo-orthogonal Latin squares are the mutually nearly orthogonal Latin squares (MNOLS) first discussed in 2002, with general constructions given in 2007. In this paper we develop row complete MNOLS from difference covering arrays. We will use this connection to settle the spectrum question for sets of 3 mutually pseudo-orthogonal Latin squares of even order, for all but the order 146.
- Published
- 2015
17. Strong orthogonal arrays of strength two plus
- Author
-
Ching-Shui Cheng, Yuanzhen He, and Boxin Tang
- Subjects
Statistics and Probability ,computer experiment ,space-filling design ,Complementary design ,05 social sciences ,second-order saturated design ,Computer experiment ,Topology ,01 natural sciences ,Connection (mathematics) ,010104 statistics & probability ,Latin hypercube ,05B15 ,62K15 ,0502 economics and business ,0101 mathematics ,Statistics, Probability and Uncertainty ,Orthogonal array ,050205 econometrics ,Mathematics - Abstract
Strong orthogonal arrays were recently introduced and studied in He and Tang [Biometrika 100 (2013) 254–260] as a class of space-filling designs for computer experiments. To enjoy the benefits of better space-filling properties, when compared to ordinary orthogonal arrays, strong orthogonal arrays need to have strength three or higher, which may require run sizes that are too large for experimenters to afford. To address this problem, we introduce a new class of arrays, called strong orthogonal arrays of strength two plus. These arrays, while being more economical than strong orthogonal arrays of strength three, still enjoy the better two-dimensional space-filling property of the latter. Among the many results we have obtained on the characterizations and constructions of strong orthogonal arrays of strength two plus, worth special mention is their intimate connection with second-order saturated designs.
- Published
- 2018
18. Constructions of optimal orthogonal arrays with repeated rows
- Author
-
Charles J. Colbourn, Shannon Veitch, and Douglas R. Stinson
- Subjects
Discrete mathematics ,Conjecture ,Modulo ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,05B15 ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,Orthogonal array ,Row ,Hadamard matrix ,Mathematics - Abstract
We construct orthogonal arrays OA λ ( k , n ) (of strength two) having a row that is repeated m times, where m is as large as possible. In particular, we consider OAs where the ratio m ∕ λ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any k ≥ n + 1 , albeit with large λ . We also study basic OAs; these are optimal OAs in which gcd ( m , λ ) = 1 . We construct a basic OA with n = 2 and k = 4 t + 1 , provided that a Hadamard matrix of order 8 t + 4 exists. This completely solves the problem of constructing basic OAs with n = 2 , modulo the Hadamard matrix conjecture.
- Published
- 2018
- Full Text
- View/download PDF
19. Optimal design of fMRI experiments using circulant (almost-)orthogonal arrays
- Author
-
Frederick Kin Hing Phoa, Ming-Hung Kao, and Yuan Lung Lin
- Subjects
Statistics and Probability ,Optimal design ,Property (programming) ,hemodynamic response function ,01 natural sciences ,Rendering (computer graphics) ,010104 statistics & probability ,03 medical and health sciences ,0302 clinical medicine ,Statistical inference ,medicine ,0101 mathematics ,Circulant matrix ,Mathematics ,medicine.diagnostic_test ,Function (mathematics) ,Circulant almost orthogonal arrays ,design efficiency ,05B15 ,62K15 ,05B10 ,Statistics, Probability and Uncertainty ,Orthogonal array ,Functional magnetic resonance imaging ,Algorithm ,030217 neurology & neurosurgery ,complete difference system - Abstract
Functional magnetic resonance imaging (fMRI) is a pioneering technology for studying brain activity in response to mental stimuli. Although efficient designs on these fMRI experiments are important for rendering precise statistical inference on brain functions, they are not systematically constructed. Design with circulant property is crucial for estimating a hemodynamic response function (HRF) and discussing fMRI experimental optimality. In this paper, we develop a theory that not only successfully explains the structure of a circulant design, but also provides a method of constructing efficient fMRI designs systematically. We further provide a class of two-level circulant designs with good performance (statistically optimal), and they can be used to estimate the HRF of a stimulus type and study the comparison of two HRFs. Some efficient three- and four-levels circulant designs are also provided, and we proved the existence of a class of circulant orthogonal arrays.
- Published
- 2017
20. A counterexample to Stein's Equi-n-square Conjecture
- Author
-
Benny Sudakov and Alexey Pokrovskiy
- Subjects
Combinatorics ,Conjecture ,05B15 ,Applied Mathematics ,General Mathematics ,Transversal (combinatorics) ,ems ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Square (algebra) ,Mathematics ,Counterexample - Abstract
In 1975 Stein conjectured that in every $n\times n$ array filled with the numbers $1, \dots, n$ with every number occuring exactly $n$ times, there is a partial transversal of size $n-1$. In this note we show that this conjecture is false by constructing such arrays without partial transverals of size $n-\frac{1}{42}\ln n$.
- Published
- 2017
21. Latin Squares with No Transversals
- Author
-
Ian M. Wanless and Nicholas J. Cavenagh
- Subjects
Selection (relational algebra) ,Modulo ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Transversal (geometry) ,Latin square ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Computer Science::Databases ,Mathematics ,Discrete mathematics ,Conjecture ,Quantitative Biology::Molecular Networks ,Applied Mathematics ,Order (ring theory) ,020206 networking & telecommunications ,05B15 ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,Geometry and Topology - Abstract
A $k$-plex in a latin square of order $n$ is a selection of $kn$ entries that includes $k$ representatives from each row and column and $k$ occurrences of each symbol. A $1$-plex is also known as a transversal.It is well known that if $n$ is even then $B_n$, the addition table for the integers modulo $n$, possesses no transversals. We show that there are a great many latin squares that are similar to $B_n$ and have no transversal. As a consequence, the number of species of transversal-free latin squares is shown to be at least $n^{n^{3/2}(1/2-o(1))}$ for even $n\rightarrow\infty$.We also produce various constructions for latin squares that have no transversal but do have a $k$-plex for some odd $k>1$. We prove a 2002 conjecture of the second author that for all even orders $n>4$ there is a latin square of order $n$ that contains a $3$-plex but no transversal. We also show that for odd $k$ and $m\geq 2$, there exists a latin square of order $2km$ with a $k$-plex but no $k'$-plex for odd $k'
- Published
- 2017
22. Solving Sudoku: Structures and Strategies
- Author
-
Curtis Cooper and Hang Chen
- Subjects
General Mathematics ,010102 general mathematics ,puzzle ,MathematicsofComputing_GENERAL ,010103 numerical & computational mathematics ,structures ,01 natural sciences ,Algebra ,05C38 ,05B15 ,strategies ,Sudoku ,walk ,0101 mathematics ,Arithmetic ,Mathematics - Abstract
We intend to solve Sudoku puzzles using various rules based on the structures and properties of the puzzle. In this paper, we shall present several structures related to either one potential solution or two potential solutions.
- Published
- 2017
23. Computing the autotopy group of a Latin square by cycle structure
- Author
-
Daniel Kotlar
- Subjects
Discrete mathematics ,Polynomial ,Group (mathematics) ,Disjoint sets ,Theoretical Computer Science ,Combinatorics ,Permutation ,05B15 ,Latin square ,Bounded function ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Combinatorics (math.CO) ,Row ,Mathematics - Abstract
An algorithm that uses the cycle structure of the rows, or the columns, of a Latin square to compute its autotopy group is introduced. As a result, a bound for the size of the autotopy group is obtained. This bound is used to show that the computation time for the autotopy group of Latin squares that have two rows or two columns that map from one to the other by a permutation which decomposes into a bounded number of disjoint cycles, is polynomial in the order n .
- Published
- 2014
24. Hownotto prove the Alon-Tarsi conjecture
- Author
-
Ian M. Wanless and Douglas S. Stones
- Subjects
Discrete mathematics ,Conjecture ,11B50 ,010308 nuclear & particles physics ,Generalization ,General Mathematics ,010102 general mathematics ,Parity of a permutation ,Congruence relation ,01 natural sciences ,Prime (order theory) ,Combinatorics ,05B15 ,Latin square ,0103 physical sciences ,Order (group theory) ,0101 mathematics ,Mathematics ,Sign (mathematics) - Abstract
The sign of a Latin square is −1 if it has an odd number of rows and columns that are odd permutations; otherwise, it is +1. LetLEnandLonbe, respectively, the number of Latin squares of ordernwith sign +1 and −1. The Alon-Tarsi conjecture asserts thatLEn≠Lonwhennis even. Drisko showed thatLEp+1≢Lop+1(modp3) for primep≥ 3 and asked if similar congruences hold for orders of the formpk+ 1,p+ 3, orpq+ 1. In this article we show that ift≤n, thenLEn+1≢L0n+1(modt3) only ift = nandnis an odd prime, thereby showing that Drisko’s method cannot be extended to encompass any of the three suggested cases. We also extend exact computation ton≤ 9, discuss asymptotics forLo/LE, and propose a generalization of the Alon-Tarsi conjecture.
- Published
- 2012
25. Gerechte designs with rectangular regions
- Author
-
E. R. Vaughan and J. Courtiel
- Subjects
Combinatorics ,05B15 ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Partition (number theory) ,Combinatorics (math.CO) ,Rectangle ,Mathematics - Abstract
A \emph{gerechte framework} is a partition of an $n \times n$ array into $n$ regions of $n$ cells each. A \emph{realization} of a gerechte framework is a latin square of order $n$ with the property that when its cells are partitioned by the framework, each region contains exactly one copy of each symbol. A \emph{gerechte design} is a gerechte framework together with a realization. We investigate gerechte frameworks where each region is a rectangle. It seems plausible that all such frameworks have realizations, and we present some progress towards answering this question. In particular, we show that for all positive integers $s$ and $t$, any gerechte framework where each region is either an $s \times t$ rectangle or a $t\times s$ rectangle is realizable., Comment: 14 pages, 12 figures
- Published
- 2011
26. On line arrangements with applications to 3-nets
- Author
-
Giancarlo Urzúa
- Subjects
52C30 ,14J10 ,05B15 ,Pure mathematics ,Quaternion group ,Construct (python library) ,Moduli ,Mathematics - Algebraic Geometry ,Line (geometry) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,Projective plane ,Algebraic Geometry (math.AG) ,Realization (systems) ,Complex number ,Mathematics - Abstract
We show a one-to-one correspondence between arrangements of d lines in the projective plane, and lines in P^{d-2}. We apply this correspondence to classify (3,q)-nets over the complex numbers for all q, 19 pages, to appear in Advances in Geometry. Sections 5, 6 and 7 of old version are worked out in more detail at the beginning of "Arrangements of rational sections over curves and the varieties they define"
- Published
- 2010
27. The Truncated & Supplemented Pascal Matrix and Applications
- Author
-
Jeffrey Sun, Michael Y. Hua, Steven B. Damelin, and Mingchao Yu
- Subjects
General Mathematics ,Computer Science - Information Theory ,maximum distance separable ,0102 computer and information sciences ,02 engineering and technology ,94B25 ,computer.software_genre ,01 natural sciences ,Matroid ,05B05 ,MDS ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,11K36 ,11T71 ,Mathematics ,computer.programming_language ,Computer Science::Information Theory ,coding ,Programming language ,020206 networking & telecommunications ,Pascal (programming language) ,Pascal ,05B15 ,05B20, 05B35 ,010201 computation theory & mathematics ,network ,code ,matroid ,05B30 ,05B35 ,computer ,Pascal matrix ,Coding (social sciences) - Abstract
In this paper, we introduce the $k\times n$ (with $k\leq n$) truncated, supplemented Pascal matrix which has the property that any $k$ columns form a linearly independent set. This property is also present in Reed-Solomon codes; however, Reed-Solomon codes are completely dense, whereas the truncated, supplemented Pascal matrix has multiple zeros. If the maximal-distance separable code conjecture is correct, then our matrix has the maximal number of columns (with the aformentioned property) that the conjecture allows. This matrix has applications in coding, network coding, and matroid theory.
- Published
- 2015
28. A central limit theorem for general orthogonal array based space-filling designs
- Author
-
Xu He and Peter Z. G. Qian
- Subjects
62E20 ,Statistics and Probability ,uncertainty quantification ,Design of experiments ,design of experiment ,Computer experiment ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,Numerical integration ,method of moment ,05B15 ,Latin hypercube sampling ,60F05 ,numerical integration ,FOS: Mathematics ,62K99 ,Applied mathematics ,Stochastic optimization ,Statistics, Probability and Uncertainty ,Uncertainty quantification ,Orthogonal array ,Mathematics ,Central limit theorem - Abstract
Orthogonal array based space-filling designs (Owen [Statist. Sinica 2 (1992a) 439-452]; Tang [J. Amer. Statist. Assoc. 88 (1993) 1392-1397]) have become popular in computer experiments, numerical integration, stochastic optimization and uncertainty quantification. As improvements of ordinary Latin hypercube designs, these designs achieve stratification in multi-dimensions. If the underlying orthogonal array has strength $t$, such designs achieve uniformity up to $t$ dimensions. Existing central limit theorems are limited to these designs with only two-dimensional stratification based on strength two orthogonal arrays. We develop a new central limit theorem for these designs that possess stratification in arbitrary multi-dimensions associated with orthogonal arrays of general strength. This result is useful for building confidence statements for such designs in various statistical applications., Comment: Published in at http://dx.doi.org/10.1214/14-AOS1231 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- Published
- 2014
29. A new bound on the size of the largest critical set in a Latin square
- Author
-
Ebadollah S. Mahmoodian and Richard Bean
- Subjects
Largest critical sets ,Discrete mathematics ,Intercalates ,Extension (predicate logic) ,Theoretical Computer Science ,Set (abstract data type) ,Combinatorics ,Latin squares ,Cardinality ,Latin square property ,05B15 ,Computer Science::Discrete Mathematics ,Latin square ,FOS: Mathematics ,Order (group theory) ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,Computer Science::Data Structures and Algorithms ,Critical set ,Mathematics - Abstract
A critical set in an n x n array is a set C of given entries, such that there exists a unique extension of C to an n x n Latin square and no proper subset of C has this property. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n), 10 pages, LaTeX
- Published
- 2003
- Full Text
- View/download PDF
30. A characterization of strong orthogonal arrays of strength three
- Author
-
Yuanzhen He and Boxin Tang
- Subjects
Statistics and Probability ,Current (mathematics) ,$(t,m,s)$-net ,space-filling design ,Mathematical analysis ,Structure (category theory) ,Computer experiment ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,Characterization (materials science) ,Latin hypercube ,05B15 ,Latin hypercube sampling ,62K15 ,Simple (abstract algebra) ,FOS: Mathematics ,Statistics, Probability and Uncertainty ,Orthogonal array ,low dimensional projection ,Mathematics - Abstract
In an early paper, He and Tang [Biometrika 100 (2013) 254-260] introduced and studied a new class of designs, strong orthogonal arrays, for computer experiments, and characterized such arrays through generalized orthogonal arrays. The current paper presents a simple characterization for strong orthogonal arrays of strength three. Besides being simple, this new characterization through a notion of semi-embeddability is more direct and penetrating in terms of revealing the structure of strong orthogonal arrays. Some other results on strong orthogonal arrays of strength three are also obtained along the way, and in particular, two $\operatorname {SOA}(54,5,27,3)$'s are constructed., Published in at http://dx.doi.org/10.1214/14-AOS1225 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- Published
- 2014
31. Enumeration of MOLS of small order
- Author
-
Judith Egan and Ian M. Wanless
- Subjects
Discrete mathematics ,Algebra and Number Theory ,Applied Mathematics ,Mathematics::History and Overview ,Order (ring theory) ,Graeco-Latin square ,Expected value ,Square (algebra) ,Combinatorics ,Set (abstract data type) ,Computational Mathematics ,symbols.namesake ,05B15 ,Latin square ,Transversal (combinatorics) ,symbols ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Orthogonal array ,Mathematics - Abstract
We report the results of a computer investigation of sets of mutually orthogonal latin squares (MOLS) of small order. For $n\le9$ we 1. Determine the number of orthogonal mates for each species of latin square of order $n$. 2. Calculate the proportion of latin squares of order $n$ 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 $n$ 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., v2 corrects some typos, including a couple of errors in tables
- Published
- 2014
32. Generalized resolution for orthogonal arrays
- Author
-
Hongquan Xu and Ulrike Grömping
- Subjects
Statistics and Probability ,qualitative factors ,generalized minimum aberration ,generalized resolution ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,Upper and lower bounds ,generalized word length pattern ,canonical correlation ,62K05 ,FOS: Mathematics ,weak strength $t$ ,Word length ,62H20 ,Mathematics ,Discrete mathematics ,Minimum aberration ,complete confounding ,05B15 ,62K15 ,Orthogonal arrays ,62J99 ,Statistics, Probability and Uncertainty ,Orthogonal array ,Canonical correlation ,Coding (social sciences) - Abstract
The generalized word length pattern of an orthogonal array allows a ranking of orthogonal arrays in terms of the generalized minimum aberration criterion (Xu and Wu [Ann. Statist. 29 (2001) 1066-1077]). We provide a statistical interpretation for the number of shortest words of an orthogonal array in terms of sums of $R^2$ values (based on orthogonal coding) or sums of squared canonical correlations (based on arbitrary coding). Directly related to these results, we derive two versions of generalized resolution for qualitative factors, both of which are generalizations of the generalized resolution by Deng and Tang [Statist. Sinica 9 (1999) 1071-1082] and Tang and Deng [Ann. Statist. 27 (1999) 1914-1926]. We provide a sufficient condition for one of these to attain its upper bound, and we provide explicit upper bounds for two classes of symmetric designs. Factor-wise generalized resolution values provide useful additional detail., Published in at http://dx.doi.org/10.1214/14-AOS1205 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- Published
- 2014
33. On a particular case of the bisymmetric equation for quasigroupes
- Author
-
Mathieu Renauld, Christophe Petit, François-Xavier Standaert, and UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
- Subjects
Discrete mathematics ,Mathématiques ,05B15 ,General Mathematics ,Functional equation ,20N05 ,Quasigroup ,Mathematics - Abstract
We characterize the solutions of the equation (1) D(G(x,y), G(u,v)) = G(D(x,u), T(y,v)) where D, G and T are quasigroups. We also discuss the particular case when D = T. © 2014 Akadémiai Kiadó, Budapest, Hungary., SCOPUS: ar.j, info:eu-repo/semantics/published
- Published
- 2014
34. Nest graphs and minimal complete symmetry groups for magic Sudoku variants
- Author
-
Rebecca Field, John Lorch, S. K. Lucas, Elizabeth Arnold, and Laura Taalman
- Subjects
Simple computation ,Mathematics::General Mathematics ,General Mathematics ,Magic (programming) ,Symmetry group ,Computer Science::Other ,Statistics::Computation ,Combinatorics ,05B15 ,05E18 ,Homogeneous space ,FOS: Mathematics ,Mathematics - Combinatorics ,Computer Science::Symbolic Computation ,Combinatorics (math.CO) ,Computer Science::Data Structures and Algorithms ,Mathematics - Abstract
A symmetry group for Sudoku is complete if its action partitions the set of Sudoku boards into all possible orbits, and minimal if no group of smaller size would do the same. Previously, for a 4 x 4 Sudoku variation known as Shidoku, the authors used an analogous symmetry group to partition the set of Shidoku boards into so-called "nests" and then use the interplay between the physical and relabeling symmetries to find certain subgroups that were both complete and minimal. In this paper these same techniques are applied to find a minimal complete symmetry group for the modular magic Sudoku variation, as well as for another Sudoku variation called semi-magic Sudoku. The paper concludes with a simple computation which leads to the non-obvious fact that the full Sudoku symmetry group is, in fact, already minimal and complete.
- Published
- 2013
- Full Text
- View/download PDF
35. On the Existence of Retransmission Permutation Arrays
- Author
-
Ian M. Wanless and Xiande Zhang
- Subjects
Discrete mathematics ,FOS: Computer and information sciences ,Applied Mathematics ,Retransmission ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Latin rectangle ,Permutation ,05B15 ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics ,Communication channel - Abstract
We investigate retransmission permutation arrays (RPAs) that are motivated by applications in overlapping channel transmissions. An RPA is an $n\times n$ array in which each row is a permutation of ${1, ..., n}$, and for $1\leq i\leq n$, all $n$ symbols occur in each $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 $n$, there exists a type-$1,2,3,4$ $\RPA(n)$ and a type-1,2 latin $\RPA(n)$., 8 pages
- Published
- 2012
36. Constructing ordered orthogonal arrays via sudoku
- Author
-
John Lorch
- Subjects
0102 computer and information sciences ,Type (model theory) ,01 natural sciences ,Prime (order theory) ,Combinatorics ,FOS: Mathematics ,Mathematics - Combinatorics ,Computer Science::General Literature ,Order (group theory) ,0101 mathematics ,Mathematics of Sudoku ,Mathematics ,Discrete mathematics ,Algebra and Number Theory ,Computer Science::Information Retrieval ,Applied Mathematics ,010102 general mathematics ,Astrophysics::Instrumentation and Methods for Astrophysics ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Linear subspace ,Finite field ,05B15 ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,Orthogonal array ,Vector space - Abstract
For prime powers q we use "strongly orthogonal" linear Sudoku solutions of order q^2 to construct ordered orthogonal arrays of type OOA (4,s,2,q), and for each q we present a range of values of s for which these constructions are valid., 18 pages
- Published
- 2016
37. Modular magic sudoku
- Author
-
John Lorch and Ellen Weld
- Subjects
Magic square ,business.industry ,Mathematics::General Mathematics ,General Mathematics ,Modulo ,Diagonal ,Mathematics::History and Overview ,Magic (programming) ,Latin square ,Symmetry group ,Modular design ,Computer Science::Other ,Combinatorics ,05B15 ,sudoku ,orthogonality ,Computer Science::Symbolic Computation ,magic square ,business ,Computer Science::Data Structures and Algorithms ,Mathematics of Sudoku ,Row ,Mathematics - Abstract
A modular magic sudoku solution is a sudoku solution with symbols in f0;1;:::;8g such that rows, columns, and diagonals of each subsquare add to zero modulo nine. We count these sudoku solutions by using the action of a suitable symmetry group and we also describe maximal mutually orthogonal families.
- Published
- 2012
38. Approximation Of Bounds On Mixed-Level Orthogonal Arrays
- Author
-
Ferruh Özbudak and Ali Devin Sezer
- Subjects
65C05 ,Statistics and Probability ,Asymptotic analysis ,Computational complexity theory ,large deviation ,Gilbert-Varshamov bound ,Rao bound ,error block code ,01 natural sciences ,optimal control ,subsolution approach ,010104 statistics & probability ,Applied mathematics ,Limit (mathematics) ,0101 mathematics ,Mathematics ,Applied Mathematics ,010102 general mathematics ,93E20 ,Optimal control ,Random walk ,asymptotic analysis ,Asymptotically optimal algorithm ,importance sampling ,05B15 ,Mixed-level orthogonal array ,counting ,62K99 ,Markov property ,Orthogonal array ,49L99 ,Hamilton-Jacobi-Bellman equation - Abstract
Mixed-level orthogonal arrays are basic structures in experimental design. We develop three algorithms that compute Rao- and Gilbert-Varshamov-type bounds for mixed-level orthogonal arrays. The computational complexity of the terms involved in the original combinatorial representations of these bounds can grow fast as the parameters of the arrays increase and this justifies the construction of these algorithms. The first is a recursive algorithm that computes the bounds exactly, the second is based on an asymptotic analysis, and the third is a simulation algorithm. They are all based on the representation of the combinatorial expressions that appear in the bounds as expectations involving a symmetric random walk. The Markov property of the underlying random walk gives the recursive formula to compute the expectations. A large deviation (LD) analysis of the expectations provides the asymptotic algorithm. The asymptotically optimal importance sampling (IS) of the same expectation provides the simulation algorithm. Both the LD analysis and the construction of the IS algorithm use a representation of these problems as a sequence of stochastic optimal control problems converging to a limit calculus of a variations problem. The construction of the IS algorithm uses a recently discovered method of using subsolutions to the Hamilton-Jacobi-Bellman equations associated with the limit problem.
- Published
- 2011
39. Isometries and construction of permutation arrays
- Author
-
Mathieu Bogaerts
- Subjects
FOS: Computer and information sciences ,Théorie des groupes ,Permutation arrays ,Computer Science - Information Theory ,Isometry ,Library and Information Sciences ,Permutation matrix ,Cyclic permutation ,Combinatorics ,Base (group theory) ,Hamming distance ,FOS: Mathematics ,Constant composition codes ,Mathematics - Combinatorics ,Permutation graph ,Géométrie combinatoire et convexité ,Mathematics ,Discrete mathematics ,Mathematics::Combinatorics ,Partial permutation ,Information Theory (cs.IT) ,Bit-reversal permutation ,Permutation codes ,Computer Science Applications ,05B15 ,Combinatorics (math.CO) ,Isometry group ,Information Systems - Abstract
An (n,d)-permutation code is a subset C of Sym(n) such that the Hamming distance dH between any two distinct elements of C is at least equal to d. In this paper, we use the characterization of the isometry group of the metric space (Sym(n),dH) in order to develop generating algorithms with rejection of isomorphic objects. To classify the (n,d) -permutation codes up to isometry, we construct invariants and study their efficiency. We give the numbers of nonisometric (4,3) - and (5,4)- permutation codes. Maximal and balanced (n,d)-permutation codes are enumerated in a constructive way. © 2006 IEEE., SCOPUS: ar.j, info:eu-repo/semantics/published
- Published
- 2010
40. Polynomial $k$-ary operations, matrices, and $k$-mappings
- Author
-
G. Belyavskaya
- Subjects
Discrete mathematics ,Polynomial ,Algebra and Number Theory ,20N05 ,Arity ,Representation theory ,20N15 ,Matrix polynomial ,law.invention ,Combinatorics ,Invertible matrix ,05B15 ,law ,Product (mathematics) ,Lie algebra ,Lie theory ,Mathematics - Abstract
We establish connection between product of two matrices of order $k\times k$ over a field and the product of the k-mappings corresponding to the $k$-operations, defined by these matrices. It is proved that, in contrast to the binary case, for arity $k\geq 3$ the components of the $k$-permutation inverse to a $k$-permutation, all components of which are polynomial $k$-quasigroups, are not necessarily $k$-quasigroups although are invertible at least in two places. Some transformations with the help of permutations of orthogonal systems of polynomial $k$-operations over a field are considered.
- Published
- 2010
41. Group Algebras of Finite Abelian Groups and their Applications to Combinatorial Problems
- Author
-
Alfred Geroldinger, Franz Halter-Koch, and Weidong Gao
- Subjects
p-group ,Discrete mathematics ,20K01 ,11B50 ,G-module ,Metabelian group ,General Mathematics ,additive Latin squares ,Perfect group ,Group algebras ,Cyclic group ,Elementary abelian group ,Davenport constant ,Free abelian group ,Combinatorics ,05B15 ,finite Abelian groups ,zero-sum sequence ,Mathematics - Abstract
Let G be an additive finite abelian group. In the last decades group algebras R[G] over suitable commutative rings R have turned out to be powerful tools for a growing variety of questions from combinatorics and number theory. Many of them can be reduced to the problem whether for some given sequence S = g1 · . . . · gl over G the elements f = (X1 − a1) · . . . · (Xl − al) 6= 0 ∈ R[G] for all a1, . . . , al ∈ R \ {0} . The present paper is devoted to this crucial problem. Before presenting our new results we recall the classical application of group algebras to the investigation of zero-sumfree sequences which is due to P. van Emde Boas, D. Kruyswijk and J.E. Olson (see [8], [9],[20]). Let d(G) denote the maximal length of a zero-sumfree sequence over G. Then d(G)+ 1 is the Davenport constant of G. For some commutative ring R, let d(G,R) denote the largest integer l ∈ N having the following property: there is some sequence S over G of length |S| = l such that (X1 − a1) · . . . · (Xl − al) 6= 0 ∈ R[G] for all a1, . . . , al ∈ R \ {0} . If S is zero-sumfree, R an integral domain, a1, . . . , al ∈ R \ {0} and
- Published
- 2009
42. Orthogonal arrays from Hermitian varieties
- Author
-
Luca Giuzzi and Angela Aguglia
- Subjects
Pure mathematics ,Collineation ,MathematicsofComputing_GENERAL ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,Set (abstract data type) ,Hermitian Varieties ,orthogonal array ,Simple (abstract algebra) ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Combinatorics ,Hermitian variety ,05B25 ,Mathematics ,Orthogonal Arrays ,05B15 ,Hermitian matrix ,Action (physics) ,collineation ,Combinatorics (math.CO) ,Orthogonal array ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
An orthogonal array OA(q^{2n-1},q^{2n-2}, q,2) is constructed from the action of a subset of PGL(n+1,q^2) on some non--degenerate Hermitian varieties in PG(n,q^2). It is also shown that the rows of this orthogonal array correspond to some blocks of an affine design, which for q> 2 is a non--classical model of the affine space AG(2n-1,q)., Corrected a typo on page 5. 14 Pages
- Published
- 2007
43. Latin bitrades derived from groups
- Author
-
Carlo Hamalainen, Nicholas J. Cavenagh, and Aleš Drápal
- Subjects
Discrete mathematics ,Group (mathematics) ,Structure (category theory) ,Homogeneous Latin bitrade ,Disjoint sets ,Permutation group ,Theoretical Computer Science ,Combinatorics ,Latin bitrade ,Derangement ,Identity (mathematics) ,Orthogonality ,05B15 ,Product (mathematics) ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics - Abstract
A latin bitrade is a pair of partial latin squares which are disjoint, occupy the same set of non-empty cells, and whose corresponding rows and columns contain the same set of entries. Dr\'apal (\cite{Dr9}) showed that a latin bitrade is equivalent to three derangements whose product is the identity and whose cycles pairwise have at most one point in common. By letting a group act on itself by right translation, we show how some latin bitrades may be derived from groups without specifying an independent group action. Properties of latin trades such as homogeneousness, minimality (via thinness) and orthogonality may also be encoded succinctly within the group structure. We apply the construction to some well-known groups, constructing previously unknown latin bitrades. In particular, we show the existence of minimal, $k$-homogeneous latin trades for each odd $k\geq 3$. In some cases these are the smallest known such examples., Comment: 23 pages
- Published
- 2007
44. Moufang loops that share associator and three quarters of their multiplication tables
- Author
-
Aleš Drápal and Petr Vojtěchovský
- Subjects
Loop (graph theory) ,Conjecture ,Series (mathematics) ,Group (mathematics) ,General Mathematics ,Associator ,20N05 ,Type (model theory) ,Combinatorics ,Mathematics::Group Theory ,20D60 ,05B15 ,Cayley table ,Order (group theory) ,Mathematics - Combinatorics ,20N05, 20D60, 05B15 ,Mathematics - Group Theory ,Mathematics - Abstract
Two constructions due to Dr\'apal produce a group by modifying exactly one quarter of the Cayley table of another group. We present these constructions in a compact way, and generalize them to Moufang loops, using loop extensions. Both constructions preserve associators, the associator subloop, and the nucleus. We conjecture that two Moufang 2-loops of finite order $n$ with equivalent associator can be connected by a series of constructions similar to ours, and offer empirical evidence that this is so for $n=16$, 24, 32; the only interesting cases with $n\le 32$. We further investigate the way the constructions affect code loops and loops of type $M(G, 2)$. The paper closes with several conjectures and research questions concerning the distance of Moufang loops, classification of small Moufang loops, and generalizations of the two constructions., Comment: 20 pages
- Published
- 2007
45. n-Ary quasigroups of order 4
- Author
-
Denis S. Krotov and Vladimir N. Potapov
- Subjects
05B15 ,20N05 ,20N15 ,94B25 ,General Mathematics ,Group Theory (math.GR) ,Composition (combinatorics) ,Characterization (mathematics) ,Combinatorics ,Set (abstract data type) ,FOS: Mathematics ,Order (group theory) ,Mathematics - Combinatorics ,Permutable prime ,Combinatorics (math.CO) ,Boolean function ,Representation (mathematics) ,Mathematics - Group Theory ,Quasigroup ,Mathematics - Abstract
We characterize the set of all N-ary quasigroups of order 4: every N-ary quasigroup of order 4 is permutably reducible or semilinear. Permutable reducibility means that an N-ary quasigroup can be represented as a composition of K-ary and (N-K+1)-ary quasigroups for some K from 2 to N-1, where the order of arguments in the representation can differ from the original order. The set of semilinear N-ary quasigroups has a characterization in terms of Boolean functions. Keywords: Latin hypercube, n-ary quasigroup, reducibility, 10pp. V2: revised
- Published
- 2007
46. On the size of the minimum critical set of a Latin square
- Author
-
Mahya Ghandehari, Ebadollah S. Mahmoodian, and Hamed Hatami
- Subjects
Discrete mathematics ,Mathematics::History and Overview ,Extension (predicate logic) ,Upper and lower bounds ,Theoretical Computer Science ,Computer Science::Other ,Combinatorics ,Set (abstract data type) ,05B15 ,Latin square ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Critical set ,Mathematics - Abstract
A critical set in an $n \times n$ array is a set $C$ of given entries, such that there exists a unique extension of $C$ to an $n\times n$ Latin square and no proper subset of $C$ has this property. For a Latin square $L$, $\scs{L}$ denotes the size of the smallest critical set of $L$, and $\scs{n}$ is the minimum of $\scs{L}$ over all Latin squares $L$ of order $n$. We find an upper bound for the number of partial Latin squares of size $k$ and prove that $$n^2-(e+o(1))n^{10/6} \le \max \scs{L} \le n^2-\frac{\sqrt{\pi}}{2}n^{9/6}.$$ % This improves a result of N. Cavenagh (Ph.D. thesis, The University of Queensland, 2003) and disproves one of his conjectures. Also it improves the previously known lower bound for the size of the largest critical set of any Latin square of order $n$.
- Published
- 2006
47. An additive theorem and restricted sumsets
- Author
-
Zhi-Wei Sun
- Subjects
Discrete mathematics ,Cyclic torsion ,11B75 ,15A15 ,Mathematics - Number Theory ,General Mathematics ,Cube (algebra) ,Field (mathematics) ,05A05 ,05B15 ,05E99 ,11C08 ,11P99 ,20D60 ,Numbering ,Combinatorics ,Cardinality ,Transversal (combinatorics) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Number Theory (math.NT) ,Abelian group ,Mathematics - Abstract
Let $G$ be any additive abelian group with cyclic torsion subgroup, and let $A$, $B$ and $C$ be finite subsets of $G$ with cardinality $n>0$. We show that there is a numbering $\{a_i\}_{i=1}^n$ of the elements of $A$, a numbering $\{b_i\}_{i=1}^n$ of the elements of $B$ and a numbering $\{c_i\}_{i=1}^n$ of the elements of $C$, such that all the sums $a_i+b_i+c_i\ (1\ls i\ls n)$ are (pairwise) distinct. Consequently, each subcube of the Latin cube formed by the Cayley addition table of $\Z/N\Z$ contains a Latin transversal. This additive theorem is an essential result which can be further extended via restricted sumsets in a field.
- Published
- 2006
48. PARTIAL LATIN SQUARES AND THEIR GENERALIZED QUOTIENTS
- Author
-
L. Yu. Glebsky and Carlos J. Rubio
- Subjects
Discrete mathematics ,Mathematics::General Mathematics ,quasigroups ,General Mathematics ,Mathematics::History and Overview ,quotients ,Set (abstract data type) ,Combinatorics ,Latin squares ,05D15 ,Mathematics::Group Theory ,05B15 ,Latin square property ,Latin square ,amalgamation ,05B20 ,Multiplication ,Quotient ,Quasigroup ,05C65 ,Computer Science::Cryptography and Security ,Mathematics - Abstract
A (partial) Latin square is a table of multiplication of a (partial) quasigroup. Multiplication of a (partial) quasigroup may be considered as a set of triples. We give a necessary and sufficient condition for a set of triples to be a quotient of a (partial) latin square.
- Published
- 2006
49. Construction of optimal multi-level supersaturated designs
- Author
-
Hongquan Xu and Chien-Fu Wu
- Subjects
Statistics and Probability ,Minimum aberration ,generalized minimum aberration ,additive character ,Addelman–Kempthorne construction ,Mathematics - Statistics Theory ,Statistics Theory (math.ST) ,Upper and lower bounds ,Galois field ,orthogonal array ,Finite field ,Quadratic equation ,05B15 ,62K15 ,62K05 ,supersaturated design ,FOS: Mathematics ,Applied mathematics ,Statistics, Probability and Uncertainty ,Orthogonal array ,Row ,62K15 (Primary) 62K05, 05B15 (Secondary) ,Mathematics - Abstract
A supersaturated design is a design whose run size is not large enough for estimating all the main effects. The goodness of multi-level supersaturated designs can be judged by the generalized minimum aberration criterion proposed by Xu and Wu [Ann. Statist. 29 (2001) 1066--1077]. A new lower bound is derived and general construction methods are proposed for multi-level supersaturated designs. Inspired by the Addelman--Kempthorne construction of orthogonal arrays, several classes of optimal multi-level supersaturated designs are given in explicit form: Columns are labeled with linear or quadratic polynomials and rows are points over a finite field. Additive characters are used to study the properties of resulting designs. Some small optimal supersaturated designs of 3, 4 and 5 levels are listed with their properties., Published at http://dx.doi.org/10.1214/009053605000000688 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- Published
- 2006
50. Asymptotics for the number of n-quasigroups of order 4
- Author
-
Denis S. Krotov and Vladimir N. Potapov
- Subjects
Pure mathematics ,General Mathematics ,Order (ring theory) ,Group Theory (math.GR) ,94B25 ,20N15 ,Asymptotic form ,05B15 ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Mathematics - Group Theory ,Mathematics - Abstract
The asymptotic form of the number of n-quasigroups of order 4 is $3^{n+1} 2^{2^n +1} (1+o(1))$. Keywords: n-quasigroups, MDS codes, decomposability, reducibility., Comment: 15 p., 3 fig
- Published
- 2006
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.