• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
local_properties.PDF (248.3Kb)
Type
Article accepté pour publication ou publié
Date
2004
Journal name
European Journal of Combinatorics
Volume
25
Number
5
Publisher
Elsevier
Pages
719-734
Publication identifier
http://dx.doi.org/10.1016/j.ejc.2003.10.004
Metadata
Show full item record
Author(s)
Maffray, Frédéric
Gravier, Sylvain
Trotignon, Nicolas cc
Renault, Jérôme
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.
Subjects / Keywords
extremal; extremal set theory; set; singleton; ramsey

Related items

Showing items related by title and author.

  • Thumbnail
    In search of the carbon price: The european CO2 emission trading scheme : from ex ante and ex post analysis to the protection in 2020 
    Trotignon, Raphaël (2012-10) Thèse
  • Thumbnail
    Un destin qui bascule. L'Entrepreneuriat, comme processus d'émancipation collectif et transgénérationnel : Analyse de parcours d'entrepreneurs Français d'Algérie, dans les périodes coloniales et postcoloniales 
    Audureau, Sylvain (2018-06-21) Thèse
  • Thumbnail
    Fast User Notification in Large-Scale Digital Librairies: Experiments and Results 
    Belhaj Frej, Hanen; Rigaux, Philippe; Spyratos, Nicolas (2007) Communication / Conférence
  • Thumbnail
    Complexity Results for the Empire Problem in Collection of Stars 
    Couëtoux, Basile; Monnot, Jérôme; Toubaline, Sónia (2012) Communication / Conférence
  • Thumbnail
    New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set 
    Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis; Xiao, Mingyu (2015) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo