• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Ramsey-type results on singletons, co-singletons and montone sequences in large collections of sets

Thumbnail
View/Open
local_properties.PDF (248.3Kb)
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
DOI
http://dx.doi.org/10.1016/j.ejc.2003.10.004
URI
https://basepub.dauphine.fr/handle/123456789/548
Collections
  • CEREMADE : Publications
Metadata
Show full item record
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.