
Ramsey-type results on singletons, co-singletons and montone sequences in large collections of sets
Maffray, Frédéric; Gravier, Sylvain; Trotignon, Nicolas; Renault, Jérôme (2004), Ramsey-type results on singletons, co-singletons and montone sequences in large collections of sets, European Journal of Combinatorics, 25, 5, p. 719-734. http://dx.doi.org/10.1016/j.ejc.2003.10.004
View/ Open
Type
Article accepté pour publication ou publiéDate
2004Journal name
European Journal of CombinatoricsVolume
25Number
5Publisher
Elsevier
Pages
719-734
Publication identifier
Metadata
Show full item recordAbstract (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.Subjects / Keywords
extremal; extremal set theory; set; singleton; ramseyRelated items
Showing items related by title and author.
-
Trotignon, Raphaël (2012-10) Thèse
-
Belhaj Frej, Hanen; Rigaux, Philippe; Spyratos, Nicolas (2007) Communication / Conférence
-
Couëtoux, Basile; Monnot, Jérôme; Toubaline, Sónia (2012) Communication / Conférence
-
Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis; Xiao, Mingyu (2015) Article accepté pour publication ou publié