Description
Abstract:
$\newcommand{\forb}{\textrm{forb}}$
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,\dots,r-1\}$. $\forb(m,r,F)$ is the maximum number of distinct columns of 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\geq 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,3,M)$ for $M=\begin{bmatrix}0&1\\0&1\\1&0\end{bmatrix}$, which is the smallest matrix for which this forbidden number is unknown, and show that it is strictly between the known general lower and upper bound results. Interestingly, it turns out that this problem is closely linked with the following optimisation problem. For each triangle in the complete graph $K_m$, pick one of its edges. Let $m_e$ denote the number of times edge $e$ is picked. What is $\max\sum_{e\in E(K_m)}2^{m_e}$? We prove lower and upper bounds for this maximum and use it to bound $\forb(m,3,M)$ away from the known general bounds.