| A generalization of Completely Separating Systems |
| English |
| Böhm, Matthias [Universität Rostock, Institut für Mathematik, D-18051 Rostock, Germany] |
| Schölzel, Karsten [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >] |
| 2012 |
| Discrete Mathematics |
| 312 |
| 22 |
| 3213-3227 |
| Yes |
| International |
| 0012365X |
| [en] Completely Separating Systems ; Extremal set theory ; Latin squares ; Transversals |
| [en] A Completely Separating System (CSS) C on [n] is a collection of blocks of [n] such that for any pair of distinct points x,y ∈ [n], there exist blocks A,B ∈ C such that x ∈ A-B and y ∈ B-A. One possible generalization of CSSs are r-CSSs. Let T be a subset of 2[n], the power set of [n]. A point i ∈ [n] is called r-separable if for every r-subset S ⊆ [n]-i there exists a block T ∈ T with i ∈ T and with the property that S is disjoint from T. If every point i ∈ [n] is r-separable, then T is an r-CSS (or r-(n)CSS). Furthermore, if T is a collection of k-blocks, then T is an r-(n,k)CSS. In this paper we offer some general results, analyze especially the case r=2 with the additional condition that k ≥ 5, present a construction using Latin squares, and mention some open problems. © 2012 Elsevier B.V. All rights reserved. |
| http://hdl.handle.net/10993/11348 |
| 10.1016/j.disc.2012.07.019 |