From i.brunke@inf.fu-berlin.de Wed Jul 04 17:21:29 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fajaz-001Deg-3K>; Wed, 04 Jul 2018 17:21:29 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fajay-000v8j-Vk>; Wed, 04 Jul 2018 17:21:29 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:DHE-RSA-AES128-SHA:128) (envelope-from ) id <1fajay-002i7g-P8>; Wed, 04 Jul 2018 17:21:28 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <15e3c98b-3865-3178-35a1-bc19f28f636e@inf.fu-berlin.de> Date: Wed, 4 Jul 2018 17:21:28 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------B4ED3332CA327538C159649D" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1530717689-000D4455-BDFBFA67/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.017576, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to EXCEPTIONAL THURSDAY Lecture - July 5th X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.26 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 04 Jul 2018 15:21:29 -0000 This is a multi-part message in MIME format. --------------B4ED3332CA327538C159649D Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Lecture on *Thursday,* *July 5th,* at 14:15 h at FU Berlin. *_Speaker_: Akihiro Higashitani (Kyoto San**gyo University)* *_Title_: Finding a new universal condition in Ehrhart theory** * *_Time_: **THURSDAY, July 5th - 14:15 h* *_Location_**: ** * *Seminar Room* Freie Universität Berlin Institut für Mathematik Arnimallee 2 14195 Berlin *_Abstract_:* Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* \leq 3h_2^* + 3; or (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish. /Exceptionally, this talk will be ///on *T**hursday*///./ -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------B4ED3332CA327538C159649D Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Lecture on Thursday, July 5th, at 14:15 h at FU Berlin.

Speaker: Akihiro Higashitani (Kyoto Sangyo University)

Title: Finding a new universal condition in Ehrhart theory

Time: THURSDAY, July 5th - 14:15 h

Location:

Seminar Room
Freie Universität Berlin
Institut für Mathematik
Arnimallee 2
14195 Berlin

Abstract:
Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* \leq 3h_2^* + 3; or (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish.

Exceptionally, this talk will be on Thursday.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------B4ED3332CA327538C159649D-- From i.brunke@inf.fu-berlin.de Thu Jul 05 15:57:21 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fb4l6-003zgH-BM>; Thu, 05 Jul 2018 15:57:20 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fb4l6-003aV5-7N>; Thu, 05 Jul 2018 15:57:20 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:DHE-RSA-AES128-SHA:128) (envelope-from ) id <1fb4l5-002yfj-Tb>; Thu, 05 Jul 2018 15:57:20 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 5 Jul 2018 15:57:19 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------FA7973066A21E5D927151C49" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1530799040-000D4455-4F335D3C/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.177579, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.1 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 9th 2018 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.26 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 05 Jul 2018 13:57:21 -0000 This is a multi-part message in MIME format. --------------FA7973066A21E5D927151C49 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on July 9th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *R**oom MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, July 9th - 14:15 h* *_Lecture_: Jeroen Zuiddam (CWI, Amsterdam)* *_Title_: Asymptotic spectra of tensors and graphs: matrix multiplication exponent and Shannon capacity * *_Abstract_:* Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs. _*Coffee & Tea Break*_*:*_* *_* R**oom MA 316 - Third Floor* *_Time_: **Monday, July 9th - 16:00 h* *_Colloquium_: Aaron Williams (Bard College at Simon's Rock, USA) * *_Title_: Fun and Games: The Computational Complexity of Puzzles and Video Games * *_Abstract_:* Most computer scientists and discrete mathematicians are familiar with computational complexity due to the famous P = NP conjecture. Some researchers have a more thorough understanding of the classes P, NP, and PSPACE since problems in logic, graph theory, and combinatorial optimization are often classified by their relationship to one of these classes. More recently, these concepts have found a wider audience through their application to puzzles and games. For example, it is known that the number puzzle Sudoku is NP-complete, whereas the box pushing game Sokoban is PSPACE-complete. In this talk we establish the computational complexity of several puzzles and games. We prove that two new paper and pencil puzzles are NP-complete. These puzzles are called Pencils and Sto-Stone, and were created by the Japanese publisher Nikoli that popularized Sudoku. We then prove that several puzzles that have been implemented as video games are PSPACE-complete. These games include a row shifting puzzle called MazezaM, a turnstile puzzle for the Nintendo Game Boy called Kwirk, and a puzzle called Switches that was invented by undergraduate student Jonathan Gabor while he was attending high school. Our reductions use conventional approaches such as Boolean Satisfiability, as well as some less conventional tools including Gray Codes, and the new Constraint Logic model pioneered by Hearn and Demaine in their influential textbook "Games, Puzzles, and Computation". The talk aims to be accessible to a wide audience, and hopes to encourage researchers to seek similar results for problems (or puzzles!) that are close to them. Most of the new results consist of joint work with undergraduate students at Bard College at Simon's Rock. -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------FA7973066A21E5D927151C49 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on July 9th 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 9th - 14:15 h

Lecture: Jeroen Zuiddam (CWI, Amsterdam)

Title: Asymptotic spectra of tensors and graphs: matrix multiplication exponent and Shannon capacity

Abstract:

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs.


Coffee & Tea Break :

Room MA 316 - Third Floor

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

Colloquium: Aaron Williams (Bard College at Simon's Rock, USA)

Title: Fun and Games: The Computational Complexity of Puzzles and Video Games

Abstract:
Most computer scientists and discrete mathematicians are familiar with computational complexity due to the famous P = NP conjecture. Some researchers have a more thorough understanding of the classes P, NP, and PSPACE since problems in logic, graph theory, and combinatorial optimization are often classified by their relationship to one of these classes. More recently, these concepts have found a wider audience through their application to puzzles and games. For example, it is known that the number puzzle Sudoku is NP-complete, whereas the box pushing game Sokoban is PSPACE-complete. In this talk we establish the computational complexity of several puzzles and games. We prove that two new paper and pencil puzzles are NP-complete. These puzzles are called Pencils and Sto-Stone, and were created by the Japanese publisher Nikoli that popularized Sudoku. We then prove that several puzzles that have been implemented as video games are PSPACE-complete. These games include a row shifting puzzle called MazezaM, a turnstile puzzle for the Nintendo Game Boy called Kwirk, and a puzzle called Switches that was invented by undergraduate student Jonathan Gabor while he was attending high school. Our reductions use conventional approaches such as Boolean Satisfiability, as well as some less conventional tools including Gray Codes, and the new Constraint Logic model pioneered by Hearn and Demaine in their influential textbook "Games, Puzzles, and Computation". The talk aims to be accessible to a wide audience, and hopes to encourage researchers to seek similar results for problems (or puzzles!) that are close to them. Most of the new results consist of joint work with undergraduate students at Bard College at Simon's Rock.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------FA7973066A21E5D927151C49-- From i.brunke@inf.fu-berlin.de Wed Jul 11 17:01:11 2018 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fdGcA-003oYC-GS>; Wed, 11 Jul 2018 17:01:10 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1fdGcA-000giw-D7>; Wed, 11 Jul 2018 17:01:10 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:DHE-RSA-AES128-SHA:128) (envelope-from ) id <1fdGcA-001Uji-6V>; Wed, 11 Jul 2018 17:01:10 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <77c7d586-6e84-aa06-c350-2122913dd2fc@inf.fu-berlin.de> Date: Wed, 11 Jul 2018 17:01:09 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------1DDEFF8A45135942AB3CCDF7" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1531321270-000D4455-35078936/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.260273, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.1 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - on July 16th 2018 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.26 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 11 Jul 2018 15:01:11 -0000 This is a multi-part message in MIME format. --------------1DDEFF8A45135942AB3CCDF7 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on July 16th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *R**oom 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*_*:*_* *_*R**oom 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 --------------1DDEFF8A45135942AB3CCDF7 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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
--------------1DDEFF8A45135942AB3CCDF7-- From felsner@math.tu-berlin.de Tue Jul 17 15:09:35 2018 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1ffPjS-0043tv-Jn>; Tue, 17 Jul 2018 15:09:34 +0200 Received: from mail.math.tu-berlin.de ([130.149.12.212]) by relay1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1ffPjS-000clj-Fd>; Tue, 17 Jul 2018 15:09:34 +0200 Received: from tutte.math.tu-berlin.de (tutte.math.tu-berlin.de [130.149.12.143]) by mail.math.tu-berlin.de (8.14.7/8.14.7) with ESMTP id w6HD9X972659210 for ; Tue, 17 Jul 2018 15:09:33 +0200 Received: by tutte.math.tu-berlin.de (Postfix, from userid 2103) id 0990F4FF; Tue, 17 Jul 2018 15:09:33 +0200 (CEST) Date: Tue, 17 Jul 2018 15:09:32 +0200 From: Stefan Felsner To: facets-of-complexity@lists.fu-berlin.de Message-ID: <20180717130932.qpzarc6yqfzgrve4@math.tu-berlin.de> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: NeoMutt/20170421 (1.8.2) X-Virus-Scanned: clamav-milter 0.99.4 at mail X-Virus-Status: Clean X-Originating-IP: 130.149.12.212 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1531832974-000D4455-BDB5CDE0/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.427701, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-2.3 required=5.0 tests=RCVD_IN_DNSWL_MED, URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Fall School: Order and Geometry X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.27 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Jul 2018 13:09:35 -0000 Please forward the following announcement to potentially interested students. The deadline for application to participate at the fall-school is July 31st. ====================================================================== Fall School: Order and Geometry September 14 - 17, 2018 Gutshof Sauen, near Berlin http://page.math.tu-berlin.de/~felsner/FoC/OGschool2018.html ====================================================================== The fall school is organized within the Research Training Group "Facets of Complexity" (www.facetsofcomplexity.de). The purpose of the fall school is to give an introductory overview of some new developments in the area, to present current research directions, and to give students working in this or related fields the opportunity to meet and to get to know each other. The school is addressed to advanced undergraduate and graduate students of Mathematics or Computer Science with interest in Discrete Mathematics and in particular in Partially Ordered Sets and Discrete Geometry. Basic knowledge in discrete mathematics is assumed. The fall school consists of four courses. Topics on flip graphs Jean Cardinal, (Université Libre de Bruxelles, Belgium) Colorings of graphs with geometric representations Bartosz Walczak, (Jagiellonian University, Kraków, Poland) Layered treewidth/separators with applications Vida Dujmović, (University of Ottawa, Canada) On crossing numbers of complete and complete bipartite graphs Oswin Aichholzer, (Technische Universität Graz, Austria) In addition to the lectures, exercises will be solved in small groups with solution sessions in the evenings. The language of the school is English. The school will take place at Gutshof Sauen, a remote manor 70 km southeast of Berlin. The costs per participant are EURO 150 and includes full board during the fall school. The number of participants is limited to about 25. Applications can be submitted using the form on the summer school website until July 31, 2018. If you have any further questions, please contact the organizers via og-school2018@math.tu-berlin.de Stefan Felsner ====================================================================== http://page.math.tu-berlin.de/~felsner/FoC/OGschool2018.html ====================================================================== From muetze@math.tu-berlin.de Mon Sep 24 10:09:02 2018 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1g4LvS-001vop-8P>; Mon, 24 Sep 2018 10:09:02 +0200 Received: from mail.math.tu-berlin.de ([130.149.12.212]) by relay1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1g4LvS-000Ova-53>; Mon, 24 Sep 2018 10:09:02 +0200 Received: from math.tu-berlin.de (webmail.math.tu-berlin.de [130.149.13.134]) by mail.math.tu-berlin.de (8.14.7/8.14.7) with ESMTP id w8O88x2A2571193; Mon, 24 Sep 2018 10:08:59 +0200 Received: from ceva.math.tu-berlin.de (ceva.math.tu-berlin.de [130.149.14.138]) by webmail.math.tu-berlin.de (Horde Framework) with HTTP; Mon, 24 Sep 2018 10:08:59 +0200 Message-ID: <20180924100859.14936lv86ol5jrmj@webmail.math.tu-berlin.de> Date: Mon, 24 Sep 2018 10:08:59 +0200 From: muetze@math.tu-berlin.de To: facets-of-complexity@lists.fu-berlin.de, I.Brunke@inf.fu-berlin.de MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) 4.2.2 X-Virus-Scanned: clamav-milter 0.99.4 at mail X-Virus-Status: Clean X-Originating-IP: 130.149.12.212 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1537776542-000004D7-1C9B1385/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.153191, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-2.3 required=5.0 tests=RCVD_IN_DNSWL_MED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to two events at TU Berlin at Oct 08 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 24 Sep 2018 08:09:02 -0000 ******************** Event 1: Pre-semester Monday lecture ******************** On Monday, Oct 08, 2 pm, at TU Berlin, in room MA 041, Dan Kral will give the following talk. You are all cordially invited. Dan Kral (Brno): Step Sidorenko property and weakly norming graphs Abstract: There has recently been a lot of interplay between extremal graph theory and the theory of graph limits. After a brief survey of the theory of dense graph limits, we focus on exploring a link between Sidorenko's Conjecture, one of the most prominent open problems in extremal graph theory, and weakly norming graphs, one of the concepts studied in the theory of graph limits. Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We are interested in a stronger property, which we call the step Sidorenko property. We relate this property to weakly norming graphs and use our results to construct a bipartite edge-transitive graph that is not weakly norming - this answers a question of Hatami [Israel J. Math. 175 (2010), 125-150]. The talk is based on joint work with Taisa Martins, Peter Pal Pach and Marcin Wrochna. ******************** Event 2: Habilitation defense ******************** On the same day, Monday, Oct 08, at 10 am (sharp) in the morning, in room BEL 301 at TU Berlin (the small villa behind the math building), I will defend my habilitation thesis entitled: "Combinatorial algorithms". You are also cordially invited to attend. There will be a reception including drinks and food afterwards, starting at 12am in room MA 508.