[Mittagsseminar TI] Mittagsseminar am 24.03.2015

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 24.03.2015
        Frédéric Meunier
        zum Thema: Hedetniemi’s conjecture for Kneser hypergraphs

Abstract: One of the most famous conjectures in graph theory is
Hedetniemi’s conjecture stating that the chromatic number of the
categorical product of graphs is the minimum of their chromatic numbers.
Using a suitable extension of the definition of the categorical product,
Zhu proposed in 1992 a similar conjecture for hypergraphs. With the help
of a technique originally introduced by Jiri Matousek and based on
combinatorial counterparts of the Borsuk-Ulam theorem, it is possible to
prove that Zhu’s conjecture is true for Kneser hypergraphs, which become
the first non-trivial and explicit family of hypergraphs satisfying this
conjecture. A similar approach also allows to exhibit new families of
graphs that satisfy Hedetniemi’s conjecture. This is joint work with
Hossein Hajiabolhassan.



***************************************************
Ort: Takustr. 9, RM 055

Uhrzeit: 12 Uhr s.t.
***************************************************

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature