2017/03/16 by Sali, Attila, Spiro, Sam · 1 citation
#05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1703.05602
A matrix is simple if it is a (0,1)-matrix and there are no repeated columns. Given a (0,1)-matrix F, we say a matrix A has F as a configuration, denoted F\prec A, if there is a submatrix of A which is a row and column permutation of F. Let |A| denote the number of columns of A. Let F be a family of matrices. We define the extremal function forb(m, F) = max\|A|\colon A is an m-rowed simple matrix and has no configuration F\inF\. We consider pairs F=\F1,F2\ such that F1 and F2 have no common extremal construction and derive that individually each forb(m, Fi) has greater asymptotic growth than forb(m, F), extending research started by Anstee and Koch.