Article ID Journal Published Year Pages File Type
4651095 Discrete Mathematics 2007 20 Pages PDF
Abstract

Let m and t   be positive integers with t⩾2t⩾2. An (m,t)(m,t)-splitting system   is a pair (X,B)(X,B) where |X|=m|X|=m and BB is a collection of subsets of X called blocks   such that for every Y⊆XY⊆X with |Y|=t|Y|=t, there exists a block B∈BB∈B such that |B∩Y|=⌊t/2⌋|B∩Y|=⌊t/2⌋. An (m,t)(m,t)-splitting system is uniform   if every block has size ⌊m/2⌋⌊m/2⌋. In this paper, we give several constructions and bounds for splitting systems, concentrating mainly on the case t=3t=3. We consider uniform splitting systems as well as other splitting systems with special properties, including disjunct and regular splitting systems. Some of these systems have interesting connections with other types of set systems.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,