{
  "id": "1710.00374",
  "version": "v1",
  "published": "2017-10-01T16:19:24.000Z",
  "updated": "2017-10-01T16:19:24.000Z",
  "title": "Multivalued matrices and forbidden configurations",
  "authors": [
    "Richard Anstee",
    "Jeffrey Dawson",
    "Linyuan Lu",
    "Attila Sali"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An $r$-matrix is a matrix with symbols in $\\{0,1,\\ldots,r-1\\}$. A matrix is simple if it has no repeated columns. Let ${\\cal F}$ be a finite set of $r$-matrices. Let $\\hbox{forb}(m,r,{\\cal F})$ denote the maximum number of columns possible in a simple $r$-matrix $A$ that has no submatrix which is a row and column permutation of any $F\\in{\\cal F}$. Many investigations have involved $r=2$. For general $r$, $\\hbox{forb}(m,r,{\\cal F})$ is polynomial in $m$ if and only if for every pair $i,j\\in\\{0,1,\\ldots,r-1\\}$ there is a matrix in ${\\cal F}$ whose entries are only $i$ or $j$. Let ${\\cal T}_{\\ell}(r)$ denote the following $r$-matrices. For a pair $i,j\\in\\{0,1,\\ldots,r-1\\}$ we form four $\\ell\\times\\ell$ matrices namely the matrix with $i$'s on the diagonal and $j$'s off the diagonal and the matrix with $i$'s on and above the diagonal and $j$'s below the diagonal and the two matrices with the roles of $i,j$ reversed. Anstee and Lu determined that $\\hbox{forb}(m,r,{\\cal T}_{\\ell}(r))$ is a constant. Let ${\\cal F}$ be a finite set of 2-matrices. We ask if $\\hbox{forb}(m,r,{\\cal T}_{\\ell}(3)\\backslash {\\cal T}_{\\ell}(2)\\cup {\\cal F})$ is $\\Theta(\\hbox{forb}(m,2,{\\cal F}))$ and settle this in the affirmative for some cases including most 2-columned $F$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-01T16:19:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "forbidden configurations",
      "multivalued matrices",
      "finite set",
      "maximum number",
      "column permutation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}