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

• https://web.archive.org/web/20081031211348/http://www.math.ucla.edu/~bsudakov/multicolored-problems.pdf

• 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.