Date
2004
Notes
La version de travail s'intitule "Local Properties of Large Collections of Sets".
Dewey
Probabilités et mathématiques appliquées
Sujet
extremal; extremal set theory; set; singleton; ramsey
Journal issue
European Journal of Combinatorics
Volume
25
Number
5
Publication date
2004
Article pages
719-734
Publisher
Elsevier
Author
Maffray, Frédéric
Gravier, Sylvain
Trotignon, Nicolas
Renault, Jérôme
Type
Article accepté pour publication ou publié
Abstract (FR)
On dit qu’une matrice 0–1 N de taille a×b se trouve dans une collection d’ensembles Image si l’on peut trouver des ensembles H1,H2,…,Ha dans Image et des éléments e1,e2,…,eb dans Image tels que N soit la matrice d’incidence de la trace des H1,H2,…,Ha sur les éléments e1,e2,…,eb. Nous démontrons le résultat suivant de type Ramsey: Pour tout Image , il existe un nombre S(n) tel que dans toute collection d’au moins S(n) ensembles distincts, on trouve soit la matrice d’incidence d’une collection de n singletons, soit le complémentaire de cette matrice, soit la matrice d’incidence d’une collection de n ensembles totalement ordonnés par l’inclusion. Nous donnons quelques résultats similaires de théorie extrèmale des ensembles. Pour certains d’entre eux, nous donnons le nombre exact d’ensembles requis.
Abstract (EN)
We say that a 0–1 matrix N of size a×b can be found in a collection of sets Image if we can find sets H1,H2,…,Ha in Image and elements e1,e2,…,eb in Image such that N is the incidence matrix of the sets H1,H2,…,Ha over the elements e1,e2,…,eb. We prove the following Ramsey-type result: for every Image , there exists a number S(n) such that in any collection of at least S(n) sets, one can find either the incidence matrix of a collection of n singletons, or its complementary matrix, or the incidence matrix of a collection ofn sets completely ordered by inclusion. We give several results of the same extremal set theoretical flavour. For some of these, we give the exact value of the number of sets required.