m 4分裂系和 1 2分隔系的若干结果.docx

T T h e M aster T h esis of Sh an gh aiJ iao TO n g U niversity S O M E N E W R E SU L T S O F (残 4)一SP L I’1’T 班 G SY S T E M A N D (残 1夕)一S E P A R A T 研 G SY S T E M S C H 0 0 L N O 。: 1 0 2 4 8 C A N D ID A T E : 兀 n x in Z h a n g A D V IS O R : D a m e n g D e n g A P P lie d M a th e m a tic s D eP artlllen t o f M atllem atics，S h an g h ai Jiao To n g U n iv ersity O c to b e r，2 0 0 8 (残 4 (残 4) 一分 裂 系 和 (残 1，2) 一分 隔 系 的若 干结 果 摘 要 假设 。、/均为整数 ，满足 。 /三。。了是一个 。元集合 ，即 l川 二那 B 是了的大小为L侧2」的子集构成的集族，其元素方称为区组。若二元组 吓 B )满足对 了 中任意的子集 犬 使得 一州二/，在B 中存在一个元素 多 使得…方自月一 阿2」或…(/ \劝 自Y 卜阿2」，则称二元组杯 B )是一个 (。，/)- 分 裂 系 。 假设 。、/l、毛为整数，满足 /l+ 毛三。。了是一个 。元集合 ，即 一川 二。，B 是了的L可2」大小的子集构成的集族，其元素方称为区组。若二元组吓 B )满 足 对 了 中任 意 两 个 不 相 交 的子 集 只 夕 其 中 …月 一/l，…夕 卜毛，p 自夕 - 燕 在B 中都存在一个元素 方，使得p 二方，夕自方一域 夕二方，p 自方一碑 则称 二元 组吓 B )是 一个 (。，/l，/z) 一分 隔系 。 本 文 首 先讨 论 了分裂 系 和 分 隔系 的一些 基 本 性 质 ，借 助传 统概 率 方 法 和 贪 心算 法 等 一 些有 力 工 具讨 论 了既是 (。，2 ，2升分裂 系又 是 (。，1，2 )- 分 隔系 的系 统 的存 在 的 区组 大 小 的一个 边 界 情 况 。 关键 词 : 分裂 系 ，分 隔系 ，概率 方法 ，贪 心算 法 S O S O M E N E W R E SU L T S O F (残 5)一SP L I’1’T 班 G SY S T E M A N D (残 1夕)一S E P A R A T 研 G SY S T E M A B S T R A C T SuPP ose “ an d / are integers Sueh th at o /三。.A n (溉 /)一SPlitting Sy stem 15 a P air 汀 B ) th at satisfies for ev ery 了二了w ith …尹…= 乙there is a Subset方of 了in B ，Such th叫 方自月一 夕2」or …(/ \劝 自Y …一少2」. SuPP ose 溉 /lan d /2are integers Sueh th at /l+ /2三。.A n ( 溉 /l，/2)- SeP aratin g Sy stem 15 a Pair 汀 B ) w llieh satisfies for ev ery p 互了，夕互了 w ith …p …一/l，…夕 …一/2an d p 自夕 一碑there 15 a bloek 方任B for wh ieh either P 二方，夕 自方一尹or 夕 二方，P 自方一歼 In th is P ap e r，w e first d ise u ss so m e b a sie P ro P e rtie s o f th e S P littin g S y ste m an d S e P ar atin g S y ste m . W e u se P o w e rful to o ls，th e b a sie P ro b ab ilistie me thod an d greedy m eth od to Produee a boun d of bloek s size for th e e x iste n e e o f b o th S P littin g S y ste m an d S e P ar atin g S y ste m . W e m