Design theory and some forbidden configurations

DOI10.1002/JCD.21709MaRDI QIDQ6187433zbMATH OpenOpenAlexFDO

Authors R. P. Anstee, Farzin Barekat

Publication date 31 January 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.11602

zbMATH Keywords

\(t\)-designsextremal set theoryforbidden configurations\((0,1)\)-matricesdesign theory

Mathematics Subject Classification ID

Other designs, configurations (05B30) Extremal set theory (05D05) Designs and configurations (05B99)

Abstract: In this paper we relate t-designs to a forbidden configuration problem in extremal set theory. Let 1_t 0_l denote a column of t 1's on top of l 0's. We assume t>l. Let q. (1_t 0_l) denote the (t+l)xq matrix consisting of t rows of q 1's and l rows of q 0's. We consider extremal problems for matrices avoiding certain submatrices. Let A be a (0,1)-matrix forbidding any (t+l)x(lambda+2) submatrix (lambda+2). (1_t 0_l) . Assume A is m-rowed and only columns of sum t+1,t+2,... ,m-l are allowed to be repeated. Assume that A has the maximum number of columns subject to the given restrictions. Assume m is sufficiently large. Then A has each column of sum 0,1,... ,t and m-l+1,m-l+2,..., m exactly once and, given the appropriate divisibility condition, the columns of sum t+1 correspond to a t-design with block size t+1 and parameter lambda and there are no other columns. The proof derives a basic upper bound on the number of columns of A by a pigeonhole argument and then a careful argument, for large m, reduces the bound by a substantial amount down to the value given by design based constructions. We extend in a few directions.

Recommendations

• Forbidden configurations and Steiner designs
• Large forbidden configurations and design theory
• Small forbidden configurations. V: Exact bounds for \(4 \times 2\) cases
• General forbidden configuration theorems
• Matrices with forbidden subconfigurations

Cites work

• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• A survey of forbidden configuration results
• Forbidden configurations and Steiner designs
• Forbidden submatrices
• Multiply intersecting families of sets
• On the existence of 2-designs Slambda(2,3,v) without repeated blocks
• Small forbidden configurations. II
• Small forbidden configurations. III.

This page was built for publication: Design theory and some forbidden configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187433)