Show simple item record

dc.contributor.authorMaffray, Frédéric
dc.contributor.authorGravier, Sylvain
dc.contributor.authorTrotignon, Nicolas
dc.contributor.authorRenault, Jérôme
dc.date.accessioned2009-06-30T10:06:30Z
dc.date.available2009-06-30T10:06:30Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/548
dc.descriptionLa version de travail s'intitule "Local Properties of Large Collections of Sets".
dc.description.abstractfrOn 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.
dc.language.isoenen
dc.subjectextremal
dc.subjectextremal set theoryen
dc.subjectset
dc.subjectsingleton
dc.subjectramsey
dc.subject.ddc519en
dc.titleRamsey-type results on singletons, co-singletons and montone sequences in large collections of setsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Joseph Fourier Grenoble 1 INPG;France
dc.description.abstractenWe 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.
dc.relation.isversionofjnlnameEuropean Journal of Combinatorics
dc.relation.isversionofjnlvol25en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2004
dc.relation.isversionofjnlpages719-734en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejc.2003.10.004
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelProbabilités et mathématiques appliquéesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record