*banner
 

Multicoloured extremal problems
Bela Bollobas, Peter Keevash

Citation
Bela Bollobas, Peter Keevash. "Multicoloured extremal problems". Journal of Combinatorial Theory, Series A 107, 2003.

Abstract
Many problems in extremal set theory can be formulated as finding the largest set system (or r -uniform set system) on a fixed ground set X that doesn't contain some forbidden configuration of sets. We will consider multicoloured versions of such problems, defined as follows. Given a list of set systems, which we think of as colours, we call another set system multicoloured if for each of its sets we can choose one of the colours it belongs to in such a way that each set gets a different colour. Given an integer k and some forbidden configurations, the multicoloured extremal problem is to choose k colours with total size as large as possible subject to containing no multicoloured forbidden configuration. Let f be the number of sets in the largest forbidden configuration. For k  f – 1 we can take all colours to consist of all subsets of X (or all r -subsets in the uniform case), and this is trivially the best possible construction. Even for k  f - 1, one possible construction is to take f – 1 colours to consist of all subsets, and the other colours empty. Another construction is to take all $k$ colours to be equal to a fixed family that is as large as possible subject to not containing a forbidden configuration. We will consider a variety of problems in extremal set theory, for which we show that one of these two constructions is always optimal. This was shown for the multicoloured version of Sperner's theorem by Daykin, Frankl, Greene and Hilton. We will extend their result to some other Sperner problems, and also prove multicoloured versions of the generalised Erdős-Ko-Rado theorem and the Sauer-Shelah theorem.

Electronic downloads

Citation formats  
  • HTML
    Bela Bollobas, Peter Keevash. <a
    href="http://chess.eecs.berkeley.edu/pubs/725.html"
    >Multicoloured extremal problems</a>, Journal of
    Combinatorial Theory, Series A 107, 2003.
  • Plain text
    Bela Bollobas, Peter Keevash. "Multicoloured extremal
    problems". Journal of Combinatorial Theory, Series A
    107, 2003.
  • BibTeX
    @inproceedings{BollobasKeevash03_MulticolouredExtremalProblems,
        author = {Bela Bollobas and Peter Keevash},
        title = {Multicoloured extremal problems},
        booktitle = {Journal of Combinatorial Theory, Series A 107},
        year = {2003},
        abstract = {Many problems in extremal set theory can be
                  formulated as finding the largest set system (or r
                  -uniform set system) on a fixed ground set X that
                  doesn't contain some forbidden configuration of
                  sets. We will consider multicoloured versions of
                  such problems, defined as follows. Given a list of
                  set systems, which we think of as colours, we call
                  another set system multicoloured if for each of
                  its sets we can choose one of the colours it
                  belongs to in such a way that each set gets a
                  different colour. Given an integer k and some
                  forbidden configurations, the multicoloured
                  extremal problem is to choose k colours with total
                  size as large as possible subject to containing no
                  multicoloured forbidden configuration. Let f be
                  the number of sets in the largest forbidden
                  configuration. For k ï£ f â 1 we can take all
                  colours to consist of all subsets of X (or all r
                  -subsets in the uniform case), and this is
                  trivially the best possible construction. Even for
                  k ï³ f - 1, one possible construction is to take
                  f â 1 colours to consist of all subsets, and the
                  other colours empty. Another construction is to
                  take all $k$ colours to be equal to a fixed family
                  that is as large as possible subject to not
                  containing a forbidden configuration. We will
                  consider a variety of problems in extremal set
                  theory, for which we show that one of these two
                  constructions is always optimal. This was shown
                  for the multicoloured version of Sperner's theorem
                  by Daykin, Frankl, Greene and Hilton. We will
                  extend their result to some other Sperner
                  problems, and also prove multicoloured versions of
                  the generalised ErdÅs-Ko-Rado theorem and the
                  Sauer-Shelah theorem.},
        URL = {http://chess.eecs.berkeley.edu/pubs/725.html}
    }
    

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess