Re: [Mittagsseminar TI] Mittagsseminar am 24.03.2015 -> 26.03.2015

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

Since the ERC-workshop is taking place simultaneously at Seminaris,
tomorrow's Mittagsseminar has been rescheduled. The new date and time are:

Thursday, 26.03.2015
14:00 st
Takustr. 9, SR 053

Frédéric Meunier
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.


On 03/20/2015 05:22 PM, Wolfgang Mulzer wrote:
> 
> 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