Source author record

Richard P. Anstee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Exact Bounds for Forbidden Configurations and the Extremal Matrices

Let $F$ be a $k\times \ell$ (0,1)-matrix. A matrix is simple if it is a (0,1)-matrix with no repeated columns. A (0,1)-matrix $A$ is said to have a $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$ . In the language of sets, a configuration is a trace. Let $\mathrm{Avoid}(m,F)$ be all simple $m$ -rowed matrices $A$ with no configuration $F$ . Define $\mathrm{forb}(m,F)$ as the maximum number of columns of any matrix in $\mathrm{Avoid}(m,F)$ . The $2\times (p+1)$ (0,1)-matrix $F(0,p,1,0)$ consists of a row of $p$ 1's and a row of one 1 in the remaining column. The paper determines $\mathrm{forb}(m,F(0,p,1,0))$ for $1\le p\le 9$ and the extremal matrices are characterized. A construction may be extremal for all $p$ .

preprint2014arXiv

Unavoidable Multicoloured Families of Configurations

Balogh and Bollobás [{\em Combinatorica 25, 2005}] prove that for any $k$ there is a constant $f(k)$ such that any set system with at least $f(k)$ sets reduces to a $k$ -star, an $k$ -costar or an $k$ -chain. They proved $f(k)<(2k)^{2^k}$ . Here we improve it to $f(k)<2^{ck^2}$ for some constant $c>0$ . This is a special case of the following result on the multi-coloured forbidden configurations at 2 colours. Let $r$ be given. Then there exists a constant $c_r$ so that a matrix with entries drawn from $\{0,1,...,r-1\}$ with at least $2^{c_rk^2}$ different columns will have a $k\times k$ submatrix that can have its rows and columns permuted so that in the resulting matrix will be either $I_k(a,b)$ or $T_k(a,b)$ (for some $a\ne b\in \{0,1,..., r-1\}$ ), where $I_k(a,b)$ is the $k\times k$ matrix with $a$ 's on the diagonal and $b$ 's else where, $T_k(a,b)$ the $k\times k$ matrix with $a$ 's below the diagonal and $b$ 's elsewhere. We also extend to considering the bound on the number of distinct columns, given that the number of rows is $m$ , when avoiding a $t k\times k$ matrix obtained by taking any one of the $k \times k$ matrices above and repeating each column $t$ times. We use Ramsey Theory.

preprint2013arXiv

Repeated columns and an old chestnut

Let $t\ge 1$ be a given integer. Let ${\cal F}$ be a family of subsets of $[m]=\{1,2,\ldots,m\}$ . Assume that for every pair of disjoint sets $S,T\subset [m]$ with $|S|=|T|=k$ , there do not exist $2t$ sets in ${\cal F}$ where $t$ subsets of ${\cal F}$ contain $S$ and are disjoint from $T$ and $t$ subsets of ${\cal F}$ contain $T$ and are disjoint from $S$ . We show that $|{\cal F}|$ is $O(m^{k})$ . Our main new ingredient is allowing, during the inductive proof, multisets of subsets of $[m]$ where the multiplicity of a given set is bounded by $t-1$ . We use a strong stability result of Anstee and Keevash. This is further evidence for a conjecture of Anstee and Sali. These problems can be stated in the language of matrices Let $t\cdot M$ denote $t$ copies of the matrix $M$ concatenated together. We have established the conjecture for those configurations $t\cdot F$ for any $k\times 2$ (0,1)-matrix $F$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.