[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - on July 16th 2018

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on July 16th at 14:15 h & 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, July 16th - 14:15 h

Lecture: Mihyun Kang (Graz University of Technology)

Title: Vanishing of cohomology groups of random simplicial complexes

Abstract:

We consider random simplicial complexes that are generated from the binomial random hypergraphs by taking the downward-closure. We determine when all cohomology groups with coefficients in F_2 vanish. This is joint work with Oliver Cooley, Nicola Del Giudice, and  Philipp Spruessel.

Coffee & Tea Break :

Room MA 316 - Third Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, July 16th - 16:00 h

Colloquium: Martin Balko (Charles University of Prague)

Title: Ramsey numbers and monotone colorings

Abstract:
For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color. For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ORS(n;2)=(n-1)^{^2}+1 and ORS(n;3) = ((2n-4) choose (n-2))+1, respectively. It follows from a result of Eliáš and Matoušek that ORS (n;4) grows as o tower of height 2. We show that ORS(n;r) grows at least as a tower of height r-2 for every r >= 3. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ORS(n;r) and two Ramsey-type problems that have been recently considered by several researchers. We also prove asymptotically tight estimates on the number of r-monotone colorings.

-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday