Partitions of Finite Relational and Set Systems
Partitions of Finite Relational and Set Systems
复制标题
DOI：
10.1016/0097-3165(77)90004-8
复制
发表时间：
1977-05
期刊：
影响因子：
--
通讯作者：
J. Nesetril;V. Rödl
中科院分区：
文献类型：
--
作者：
J. Nesetril;V. Rödl
Ramsey的经典定理[12]指出：给定k，I，m个正整数，存在n具有以下性质：对于一个具有n个元素的集合的Z-元素子集的每一个划分为k个类，存在一个具有m个元素的子集，其所有I-元素子集在一个类中。这个定理及其类似物的一些结构扩展已经出现（见[2，4，5，71;[6]是对这一最近发展的综述）。粗略地说，Ramsey型定理保证了给定的（对象，结构，.）A，B：存在一个对象C，它包含B的许多“副本”，即使把C中A的所有副本的集合分成少量的部分，也不能“摧毁”B的所有副本（具体公式见第2节）。本文的目的有两个：首先，我们提出了一种方法，通过它可以证明一个定理的拉姆齐型的类集系统是局部不太密集（即不包含完整的子系统）。这（Erdas和其他人的问题）是这项研究的原始动机;证明，对于集合系统，一个定理类似于图的早期结果[9]。这种推广比预期的要困难得多，必须设计一种新的方法。所得结果推广了有关图的所有已知结果（见[lo]）.其次，（有点令人惊讶），新方法足够强大，可以证明不仅可以划分边，超边，顶点等，但所有合适的（称为基本）子系统，并在大多数情况下，给出这一事实的充分表征（见[lo]中的“原型定理”）。
The classical theorem of Ramsey [12] states: Given k, I, m positive integers, there exists n with the following property: For every partition of Z-element subsets of a set with n elements into k classes, there exists a subset with m elements with all its I-element subsets in one class. A number of structural extensions of this theorem and its analogs have appeared (see [2, 4, 5, 71;[6] is a survey of this recent development). Roughly speaking, a theorem of Ramsey type guarantees for given (objects, structures,...) A, B the existence of an object C which contains so many “copies” of B that even by a partition of the set of all copies of A in C into a small number of parts, one cannot “destroy” all copies of B (see Section 2 for the exact formulation).The purpose of this paper is twofold: First, we present a method by means of which one can prove a theorem of Ramsey type for classes of set systems which are locally not too dense (ie, do not contain complete subsystems). This (a problem of Erdas and others) was the original motivation for this research; to prove, for the set systems, a theorem analogous to the earlier results for graphs [9]. This generalization was more difficult than expected, and a new method had to be devised. The results extend all the previously known results concerning graphs (see [lo]). Second,(and a bit surprisingly), the new method is sufficiently strong to prove that one can partition not only edges, hyperedges, vertices, etc., but all suitable (called fundamental) subsystems, and in most cases to give the full characterization of this fact (see the “prototype theorem” in [lo]).