Discrepancy of high-dimensional permutations

DOI10.19086/DA.845MaRDI QIDQ2826225zbMATH OpenOpenAlexFDO

Authors Nathan Linial, Zur Luria

Publication date 10 October 2016

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1512.04123

zbMATH Keywords

Latin square

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: Let $L$ be an order-$n$ Latin square. For $X,Y,Zsubseteq1,\mathrm{...},n$, let $L(X,Y.Z)$ be the number of triples $iinX,jinY,kinZ$ such that $L(i,j)=k$. We conjecture that asymptotically almost every Latin square satisfies $|L(X,Y,Z)-frac1n|X||Y||Z||leO(sqrt|X||Y||Z|)$ for every $X,Y$ and $Z$. Let $varepsilon(L):=max|X||Y||Z|$ when $L(X,Y,Z)=0$. The above conjecture implies that $varepsilon(L)leO(n^2)$ holds asymptotically almost surely (this bound is obviously tight). We show that there exist Latin squares with $varepsilon(L)leO(n^2)$, and that $varepsilon(L)leO(n^{2}lo{g}^{2}n)$ for almost every order-$n$ Latin square. On the other hand, we recall that $varepsilon(L)geqOmega(n^{33/14})$ if $L$ is the multiplication table of an order-$n$ group. Some of these results extend to higher dimensions. Many open problems remain.

Recommendations

• All-even Latin squares
• Intercalates and discrepancy in random Latin squares
• Transversals in Latin Squares
• Substructures in Latin squares
• Large deviations in random latin squares

Cites work

• A note on the random greedy triangle-packing algorithm
• An upper bound on the number of high-dimensional permutations
• Expander graphs and their applications
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Large product-free subsets of finite groups
• Quasirandom Groups
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Sidon sets in groups and induced subgraphs of Cayley graphs

Cited in

(11)

• Good permutations for extreme discrepancy
• A universal exponent for homeomorphs
• Coloured and directed designs
• An upper bound on the number of high-dimensional permutations
• Almost all Steiner triple systems are almost resolvable
• On the threshold problem for Latin boxes
• Simplicial homeomorphs and trace-bounded hypergraphs
• Substructures in Latin squares
• Large deviations in random latin squares
• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• On the twin-width of near-regular graphs

This page was built for publication: Discrepancy of high-dimensional permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826225)