Binary matroid representation of cyclic families
Let [math]B=\{b_1,b_2,\ldots ,b_k\}\subset\{0,1,\ldots ,n-1\}[/math], and let [math]B_i=\{b_1+i, b_2+i,\ldots, b_k+i\}[/math] where addition is modulo n. That is, [math]{\mathcal B}=\{B_1,B_2,\ldots B_N\}[/math] is the collection of cyclic translates of B. Prove that there exists a binary matroid M such that every [math]B_i[/math] is a basis of M.
Remarks
This question was asked by Attila Sali. If true, then it would prove an extremal set theoretical conjecture of Vera T. Sós, see [1].
It was proven (implicitly) for [math]B=\{1,2,\ldots k\}[/math] by Griggs and Walker [2]. In this case, there even exist graphic matroids as it was proved by Sali and Simonyi [3].
If n=7 and [math]B=\{1,2,4\}[/math], then the cyclic translates form the Fano plane, so graphic matroid cannot be expected for general B.
The statement was proven for k=3 by Füredi et al.[4].
References
- ↑ F.R.K. Chung, R.L. Graham, P. Frankl, J.B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A 43 (1986), no. 1, 23-37. DOI link, Author link.
- ↑ J.R. Griggs, J.W. Walker, Anticlusters and intersecting families of subsets, J. Combin. Theory Ser. A 51 (1989), no. 1, 99-103, DOI link.
- ↑ A. Sali, G. Simonyi, Intersecting set systems and graphic matroids, Discrete Math. 185 (1998), 279-285, DOI link.
- ↑ Z. Füredi, J.R. Griggs, R. Holzman, D.J. Kleitman, Representations of families of triples over GF(2), J. Combin. Theory Ser. A 53 (1990), no. 2, 306-315. DOI link, Author link.
