2023/12/18 by Wallace Peaslee, Peaslee, Wallace, Attila Sali +3
Engineering · Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Mathematical Approximation and Integration #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2312.11446
openalex publication_date 2023/12/18 · openalex created_date 2023/12/20 · openalex updated_date 2026/08/01
The forbidden number forb(m,F), which denotes the maximum number of distinct columns in an m-rowed (0,1)-matrix with no submatrix that is a row and column permutation of F, has been widely studied in extremal set theory. Recently, this function was extended to r-matrices, whose entries lie in \0,1,⋯,r-1\. forb(m,r,F) is the maximum number of distinct columns in an r-matrix with no submatrix that is a row and column permutation of F. While forb(m,F) is polynomial in m, forb(m,r,F) is exponential for r≥ 3. Recently, forb(m,r,F) was studied for some small (0,1)-matrices F, and exact values were determined in some cases. In this paper we study forb(m,r,M) for M=\beginbmatrix0&1 0&1 1&0\endbmatrix, which is the smallest matrix for which this forbidden number is unknown. Interestingly, it turns out that this problem is closely linked with the following optimisation problem. For each triangle in the complete graph Km, pick one of its edges. Let me denote the number of times edge e is picked. For each α∈ℝ, what is H(m,α)=max∑e∈ E(Km)αme? We establish a relationship between forb(m,r,M) and H(m,(r-1)/(r-2)), find upper and lower bounds for H(m,α), and use them to significantly improve known bounds for forb(m,r,M).