Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn completing three cyclic transversals to a latin square
303
0
0.0
(
0
)
Added by
Carlo H\\\"am\\\"al\\\"ainen
Publication date
2007
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $P$ be a partial latin square of prime order $p>7$ consisting of three cyclically generated transversals. Specifically, let $P$ be a partial latin square of the form: [ P={(i,c+i,s+i),(i,c+i,s+i),(i,c+i,s+i)mid 0 leq i< p} ] for some distinct $c,c,c$ and some distinct $s,s,s$. In this paper we show that any such $P$ completes to a latin square which is diagonally cyclic.
rate research
Read More
We introduce a notion of parity for transversals, and use it to show that in Latin squares of order $2 bmod 4$, the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving $E_1,dots, E_n$, where $E_i$ is the number of diagonals of a given Latin square that contain exactly $i$ different symbols. Let $A(imid j)$ denote the matrix obtained by deleting row $i$ and column $j$ from a parent matrix $A$. Define $t_{ij}$ to be the number of transversals in $L(imid j)$, for some fixed Latin square $L$. We show that $t_{ab}equiv t_{cd}bmod2$ for all $a,b,c,d$ and $L$. Also, if $L$ has odd order then the number of transversals of $L$ equals $t_{ab}$ mod 2. We conjecture that $t_{ac} + t_{bc} + t_{ad} + t_{bd} equiv 0 bmod 4$ for all $a,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 $k$-regular bipartite graph on $2n$ vertices is divisible by $4$ when $n$ is odd and $kequiv0bmod 4$. We also show that $${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,d$, when $A$ is an integer matrix of odd order with all row and columns sums equal to $kequiv2bmod4$.
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 $ntimes 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.
In combinatorics, a latin square is a $ntimes n$ matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Associated to each latin square, we can define a simple graph called a latin square graph. In this article, we compute lower and upper bounds for the domination number and the k-tuple total domination numbers of such graphs. Moreover, we describe a formula for the 2-tuple total domination number.
We prove a conjecture by Garbe et al. [arXiv:2010.07854] by showing that a Latin square is quasirandom if and only if the density of every 2x3 pattern is 1/720+o(1). This result is the best possible in the sense that 2x3 cannot be replaced with 2x2 or 1xN for any N.
We develop a limit theory of Latin squares, paralleling the recent limit theories of dense graphs and permutations. We introduce a notion of density, an appropriate version of the cut distance, and a space of limit objects - so-called Latinons. Key results of our theory are the compactness of the limit space and the equivalence of the topologies induced by the cut distance and the left-convergence. Last, using Keevashs recent results on combinatorial designs, we prove that each Latinon can be approximated by a finite Latin square.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
