Exponential multivalued forbidden configurations

The forbidden number forb(m, F), which denotes the maximum number of unique 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,...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2021-01, Vol.23 (1), p.1-13
Main Authors: Dillon, Travis, Sali, Attila
Format: Article
Language:English
Subjects:
Combinatorial analysis
Matrices (mathematics)
Permutations
Set theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The forbidden number forb(m, F), which denotes the maximum number of unique 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}. The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many (0,1)-matrices F, including all 2-rowed matrices when r > 3. We also prove a stability result for the 2 × 2 identity matrix. Along the way, we expose some interesting qualitative differences between the cases r = 2, r = 3, and r > 3.
ISSN:1365-8050