Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge deviations in random Latin squares
123
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this note, we study large deviations of the number $mathbf{N}$ of intercalates ($2times2$ combinatorial subsquares which are themselves Latin squares) in a random $ntimes n$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mathbf{N}le(1-delta)n^{2}/4)leexp(-Omega(n^{2}))$ and $Pr(mathbf{N}ge(1+delta)n^{2}/4)leexp(-Omega(n^{4/3}(log n)^{2/3}))$, both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-$n$ Latin square has $(1+o(1))n^{2}/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.
rate research
Read More
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.
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$.
A Latin square has six conjugate Latin squares obtained by uniformly permuting its (row, column, symbol) triples. We say that a Latin square has conjugate symmetry if at least two of its six conjugates are equal. We enumerate Latin squares with conjugate symmetry and classify them according to several common notions of equivalence. We also do similar enumerations under additional hypotheses, such as assuming the Latin square is reduced, diagonal, idempotent or unipotent. Our data corrected an error in earlier literature and suggested several patterns that we then found proofs for, including (1) The number of isomorphism classes of semisymmetric idempotent Latin squares of order $n$ equals the number of isomorphism classes of semisymmetric unipotent Latin squares of order $n+1$, and (2) Suppose $A$ and $B$ are totally symmetric Latin squares of order $n otequiv0bmod3$. If $A$ and $B$ are paratopic then $A$ and $B$ are isomorphic.
In this paper two independent and unitarily invariant projection matrices P(N) and Q(N) are considered and the large deviation is proven for the eigenvalue density of all polynomials of them as the matrix size $N$ converges to infinity. The result is formulated on the tracial state space $TS({cal A})$ of the universal $C^*$-algebra ${cal A}$ generated by two selfadjoint projections. The random pair $(P(N),Q(N))$ determines a random tracial state $tau_N in TS({cal A})$ and $tau_N$ satisfies the large deviation. The rate function is in close connection with Voiculescus free entropy defined for pairs of projections.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
