PreprintCC BY-NC-ND 4.0arXiv
Block Designs with Large Transversal-Block Intersections
Abstract
A block design is a set family, whose members are called blocks, where every pair of points in the universe is covered by exactly one block. Erdős asked the following question: is it true that if the universe is of size n and each block is of size Ω(√n), then there exists a transversal intersecting every block in O(1) points? We provide a negative answer to this question. Indeed, for arbitrarily large n, we construct such a block designs where every transversal intersects some block in Ω((log n)/(loglog n)) points.
Related
- Mathieu groups as flag-transitive automorphism groups of block designs
- A Method of Construction of Pairwise Additive Balanced Incomplete Block Designs
- Block-Transitive $5−(v,k,2)$ Designs with k divides v
- Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs
- Non-convex integer programming: a deterministic solution method of the large block sale problem
BibTeX
@misc{nie2026block,
title = {{Block Designs with Large Transversal-Block Intersections}},
author = {Jiaxi Nie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07736},
eprint = {2609.07736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07736},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Block Designs with Large Transversal-Block Intersections
AU - Jiaxi Nie
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07736
UR - https://arxiv.org/abs/2609.07736
AB - A block design is a set family, whose members are called blocks, where every pair of points in the universe is covered by exactly one block. Erdős asked the following question: is it true that if the universe is of size n and each block is of size Ω(√n), then there exists a transversal intersecting every block in O(1) points? We provide a negative answer to this question. Indeed, for arbitrarily large n, we construct such a block designs where every transversal intersects some block in Ω((log n)/(loglog n)) points.
ER -