2025/02/07 by Wallace Peaslee, Peaslee, Wallace, Attila Sali +3
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2502.04741
openalex publication_date 2025/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The present paper considers extremal combinatorics questions in the language of matrices. An s-matrix is a matrix with entries in \0,1,…, s-1\. An s-matrix is simple if it has no repeated columns. A matrix F is a configuration in a matrix A, denoted F\prec A, if it is a row/column permutation of a submatrix of A. Avoid(m,s,F) is the set of m-rowed, simple s-matrices not containing a configuration of F and forb(m,s, F)=max\|A|\colon A ∈ Avoid(m,s,F)\. Dillon and Sali initiated the systematic study of forb(m,s, F) for 2-matrices F, and computed forb(m,s, F) for all 2-rowed F when s>3. In this paper we tackle the remaining cases when s=3. In particular, we determine the asymptotics of forb(m,3,p⋅ K2)-forb(m,3,p⋅ I2) for p>3, where K2 is the 2× 4 simple 2-matrix and I2 is the 2× 2 identity matrix, as well as the exact values of forb(m,3,F) for many 2-rowed 2-matrices F.