A generalization of Completely Separating Systems

作者：Boehm Matthias; Schoelzel Karsten

来源：Discrete Mathematics, 2012, 312(22): 3213-3227.

DOI：10.1016/j.disc.2012.07.019

• Extremal set theory
• Completely Separating Systems
• (Regular) antichain
• Latin squares
• Transversals

A Completely Separating System (CSS) (sic) on [n] is a collection of blocks of [n] such that for any pair of distinct points x, y is an element of [n], there exist blocks A, B is an element of (sic) such that x is an element of A - B and y is an element of 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 is an element of [n] is called r-separable if for every r-subset S subset of [n] - {i} there exists a block T is an element of T with i is an element of T and with the property that S is disjoint from T. If every point i is an element of [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 %26lt;= 5, present a construction using Latin squares, and mention some open problems.

• 出版日期2012-11-28