From rote@inf.fu-berlin.de Wed May 23 18:00:58 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 <1fLWCA-001O3s-HQ>; Wed, 23 May 2018 18:00:58 +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 <1fLWCA-0024Gt-E7>; Wed, 23 May 2018 18:00:58 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) 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 <1fLWCA-001yN8-91>; Wed, 23 May 2018 18:00:58 +0200 To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= Message-ID: Date: Wed, 23 May 2018 18:00:58 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1527091258-000005A1-4D707214/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000228, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: X-Mailman-Approved-At: Wed, 23 May 2018 18:02:48 +0200 Subject: [Facets-of-complexity] testnachricht 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, 23 May 2018 16:00:58 -0000 -- G"unter Rote (Germany=49)30-838-75150 (office) Freie Universit"at Berlin -75103 (secretary) Institut f"ur Informatik FAX (49)30-838-4-75150 Takustrase 9, D-14195 Berlin, GERMANY From rote@inf.fu-berlin.de Thu May 24 21:00:13 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 <1fLvTB-003ahN-Bq>; Thu, 24 May 2018 21:00:13 +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 <1fLvTB-001We4-8T>; Thu, 24 May 2018 21:00:13 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) 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 <1fLvTB-0010Xa-1z>; Thu, 24 May 2018 21:00:13 +0200 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: <20180511071310.kltmoo2ecw2sbllj@math.tu-berlin.de> <592b9db1-6622-feda-15db-5a80e5f223fa@inf.fu-berlin.de> <8168db40-4f4d-0935-e559-242dd58c7a21@inf.fu-berlin.de> Message-ID: <8d979c39-5c26-1c6a-9faf-d9e2146dc3f2@inf.fu-berlin.de> Date: Thu, 24 May 2018 21:00:12 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 In-Reply-To: <8168db40-4f4d-0935-e559-242dd58c7a21@inf.fu-berlin.de> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-Originating-IP: 160.45.40.209 X-purgate: suspect X-purgate-type: suspect X-purgate-ID: 151147::1527188413-000005A1-44F6F0E8/2/26091860435 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000033, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-49.0 required=5.0 tests=ALL_TRUSTED, FU_XPURGATE_SUSP, URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lectures new Mailing List FACETS OF COMPLEXITY 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, 24 May 2018 19:00:13 -0000 As announced, the series of Monday lectures of the Graduiertenkolleg MDS (Methods of Discrete Structures) will be continued in the new Graduiertenkolleg FACETS OF COMPLEXITY, You have received this message through the new mailing list (potentially through a subsidiary list), and you will be notified about the Monday lectures and other events through this list. With best regards -- G"unter Rote, spokesman "Facets of Complexity" Freie Universit"at Berlin (Germany=49)30-838-75150 (office) Institut f"ur Informatik Takustrase 9, D-14195 Berlin, GERMANY From rote@inf.fu-berlin.de Sun May 27 08:50:14 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 <1fMpVN-000Jhj-R3>; Sun, 27 May 2018 08:50:13 +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 <1fMpVN-001uc6-NC>; Sun, 27 May 2018 08:50:13 +0200 Received: from dslb-094-222-024-118.094.222.pools.vodafone-ip.de ([94.222.24.118] helo=[192.168.178.36]) 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 <1fMpVN-000AZ5-Dh>; Sun, 27 May 2018 08:50:13 +0200 References: From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de X-Forwarded-Message-Id: Message-ID: Date: Sun, 27 May 2018 08:50:12 +0200 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-CA Content-Transfer-Encoding: 8bit X-Originating-IP: 94.222.24.118 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1527403813-000005A1-F54D0554/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000611, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lectures Facets of Complexity: May 28, 2018, change of schedule 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: Sun, 27 May 2018 06:50:14 -0000 You are cordially invited to this week's Monday Lecture. When? Monday, May 28, 2018, 14:15 h Where? Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin room MA 041, ground floor The talk by Alan Arroyo at 16:00 is *cancelled* and the talk by Dušan Knop is *rescheduled* from 17:00 to 16:00. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Lecture - 14:15 Marek Cygan, University of Warsaw Approximation algorithms for the k-Set packing problem In the k-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most k. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms, mostly involving local-search-based routines. Tea and coffee break ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Colloquium - 16:00 (moved from 17:00) Dušan Knop, University of Bergen Parameterized Complexity of Steiner Problems In the Steiner Tree problem, a set of terminal vertices in an edge-weighted graph needs to be connected in the cheapest possible way. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on the one hand, Steiner Tree is known to be APX-hard, and on the other hand, it is W[2]-hard if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H of G of the minimum cost such that there is a directed path from s to t in H for all arcs st of R. It is known that the problem can be solved in time |V(G)|^O(|A(R)|) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|^o(|A(R)|) even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|^o(|T|), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to |T| in the exponent. We show that Directed Steiner Network is solvable in time f(|T|) · |V(G)|^O(c_g·|T|), where c_g is a constant depending solely on the genus g of G and f is a computable function. ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Colloquium - 16:00 (cancelled) Alan Arroyo, University of Waterloo Pseudolinear drawings of graphs - CANCELLED ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Graduiertenkolleg "Facets of Complexity" - www.facetsofcomplexity.de/monday From i.brunke@inf.fu-berlin.de Thu May 31 17:09:22 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 <1fOPCb-002k3K-PC>; Thu, 31 May 2018 17:09:21 +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 <1fOPCb-001L49-LI>; Thu, 31 May 2018 17:09:21 +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 <1fOPCb-003WKp-EW>; Thu, 31 May 2018 17:09:21 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <6a1fe0e1-8484-3bf1-eeb0-55c6682b6ccf@inf.fu-berlin.de> Date: Thu, 31 May 2018 17:09:21 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------04C44352AB8EDDD114375975" 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::1527779361-000004CA-FE7FF6B4/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.121252, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: X-Mailman-Approved-At: Thu, 31 May 2018 17:14:03 +0200 Subject: [Facets-of-complexity] Invitation to Monday Colloquium - June 4th 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, 31 May 2018 15:09:22 -0000 This is a multi-part message in MIME format. --------------04C44352AB8EDDD114375975 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Colloquium on June 4th at 14:15 h at TU Berlin. *_Speaker_: Andrew Newman (Ohio State University**)* *_Title_: **Small simplicial complexes with large torsion in homology* *_Time_: **Monday, June 4th - 14:15 h* *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Abstract_:* From Kalai's classic paper generalizing Cayley's tree-enumeration formula to simplicial complexes, it is known that simplicial complexes on a small number of vertices can have enormous torsion in homology. Moreover, in a random setting one may find instances of this phenomenon such as, for example, a 3-dimensional simplicial complex on 30 vertices with the torsion subgroup of the second homology group having order larger than 10^^82 . In this talk I will discuss the problem of explicitly constructing such complexes. In particular, I will discuss my work to use the probabilistic method to construct optimally small (up to a constant factor from a known lower bound) simplicial complexes with /prescribed/ torsion in homology. I will also discuss an application of this work to the problem of counting homotopy types of simplicial complexes. /Exceptionally, there will be no lecture and only this colloquium./ -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------04C44352AB8EDDD114375975 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Colloquium on June 4th at 14:15 h at TU Berlin.

Speaker: Andrew Newman (Ohio State University)

Title: Small simplicial complexes with large torsion in homology

Time: Monday, June 4th - 14:15 h

Location:

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

Abstract:
From Kalai's classic paper generalizing Cayley's tree-enumeration formula to simplicial complexes, it is known that simplicial complexes on a small number of vertices can have enormous torsion in homology. Moreover, in a random setting one may find instances of this phenomenon such as, for example, a 3-dimensional simplicial complex on 30 vertices with the torsion subgroup of the second homology group having order larger than 10^82. In this talk I will discuss the problem of explicitly constructing such complexes. In particular, I will discuss my work to use the probabilistic method to construct optimally small (up to a constant factor from a known lower bound) simplicial complexes with prescribed torsion in homology. I will also discuss an application of this work to the problem of counting homotopy types of simplicial complexes.

Exceptionally, there will be no lecture and only this colloquium.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------04C44352AB8EDDD114375975-- From i.brunke@inf.fu-berlin.de Wed Jun 06 14:34:34 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 <1fQXe5-002087-RY>; Wed, 06 Jun 2018 14:34:33 +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 <1fQXe5-002uWy-Nl>; Wed, 06 Jun 2018 14:34:33 +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 <1fQXe5-001E0R-D1>; Wed, 06 Jun 2018 14:34:33 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <6cd00102-e3be-be40-a676-6bc313ab540b@inf.fu-berlin.de> Date: Wed, 6 Jun 2018 14:34:33 +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="------------A58EC9E00751370622B5C668" 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::1528288473-000004CA-95981FA7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.262811, 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 on June 11th 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, 06 Jun 2018 12:34:34 -0000 This is a multi-part message in MIME format. --------------A58EC9E00751370622B5C668 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 11th at 14:15 h & 16:00 h at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, June 11th - 14:15 h* *_Lecture_: John Bamberg (University**of Western Australia, Perth)* *_Title_: Bruck nets, metric planes, and their friends*** *_Abstract_:* In 1967, F. Arthur Sherk gave a simple proof that the finite metric planes (of Bachmann and Schmidt) are precisely the affine planes of odd order. Moreover, Sherk’s proof holds for a more general class of incidence structures that do not involve the ‘three-reflection theorem’ whatsoever, and thus yields a beautiful characterisation of the finite affine planes of odd order. By relaxing the first of Sherk’s axioms to ‘every pair of points lies on at most**one line’, we can study what we call /partial Sherk planes/. In this talk, we outline our characterisation of these incidence structures as /Bruck nets/, in the same vein as Sherk’s result, and what it means for connected combinatorial objects such as mutually orthogonal latin squares. (Joint work with Joanna Fawcett and Jesse Lansdown) _*Coffee & Tea Break*_ *_Time_: **Monday, June 11th - 16:00 h* *_Colloquium_: Anurag Bishnoi (Freie Universität Berlin**)* *_Title_: New upper bounds on some cage numbers * *_Abstract_:* The cage problem asks for the smallest number c(k, g) of vertices in a k-regular graph of girth g. The (k, g)-graphs which have c(k, g) vertices are known as cages. While cages are known to exist for all integers k > 1 and g > 2, an explicit construction is known only for some small values of k, g and three infinite families for which g is 6, 8 or 12 and k − 1 is a prime power: corresponding to the generalized g/2-gons of order k − 1. To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12), when k - 1 is not a prime power, one of the main techniques that has been used so far is to construct small (k, g) graphs by picking a prime power q ≥ k and then finding a small k-regular subgraph of the incidence graph of a generalized g/2-gon of order q. In this talk I will present new constructions in generalized quadrangles and hexagons which improve the known upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k = p^h, where p is an arbitrary prime. Moreover, we will see a spectral lower bound on the number of vertices in a k-regular induced subgraph of an arbitrary regular graph, which in particular will prove the optimality of a known construction in projective planes. (Joint work with John Bamberg and Gordon Royle) -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------A58EC9E00751370622B5C668 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, June 11th - 14:15 h

Lecture: John Bamberg (University of Western Australia, Perth)

Title: Bruck nets, metric planes, and their friends

Abstract:

In 1967, F. Arthur Sherk gave a simple proof that the finite metric planes (of Bachmann and Schmidt) are precisely the affine planes of odd order. Moreover, Sherk’s proof holds for a more general class of incidence structures that do not involve the ‘three-reflection theorem’ whatsoever, and thus yields a beautiful characterisation of the finite affine planes of odd order. By relaxing the first of Sherk’s axioms to ‘every pair of points lies on at most one line’, we can study what we call partial Sherk planes. In this talk, we outline our characterisation of these incidence structures as Bruck nets, in the same vein as Sherk’s result, and what it means for connected combinatorial objects such as mutually orthogonal latin squares.

(Joint work with Joanna Fawcett and Jesse Lansdown)


Coffee & Tea Break

Time: Monday, June 11th - 16:00 h

Colloquium: Anurag Bishnoi (Freie Universität Berlin)

Title: New upper bounds on some cage numbers

Abstract:

The cage problem asks for the smallest number c(k, g) of vertices in a k-regular graph of girth g. The (k, g)-graphs which have c(k, g) vertices are known as cages. While cages are known to exist for all integers k > 1 and g > 2, an explicit construction is known only for some small values of k, g and three infinite families for which g is 6, 8 or 12 and k − 1 is a prime power: corresponding to the generalized g/2-gons of order k − 1.

To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12), when k - 1 is not a prime power, one of the main techniques that has been used so far is to construct small (k, g) graphs by picking a prime power q ≥ k and then finding a small k-regular subgraph of the incidence graph of a generalized g/2-gon of order q. In this talk I will present new constructions in generalized quadrangles and hexagons which improve the known upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k = p^h, where p is an arbitrary prime. Moreover, we will see a spectral lower bound on the number of vertices in a k-regular induced subgraph of an arbitrary regular graph, which in particular will prove the optimality of a known construction in projective planes.

(Joint work with John Bamberg and Gordon Royle)
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------A58EC9E00751370622B5C668-- From i.brunke@inf.fu-berlin.de Thu Jun 14 13:31:28 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 <1fTQTP-003IwC-Ss>; Thu, 14 Jun 2018 13:31:27 +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 <1fTQTP-000cuQ-PD>; Thu, 14 Jun 2018 13:31:27 +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 <1fTQTP-001bFv-IE>; Thu, 14 Jun 2018 13:31:27 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <5e8953c6-4d2b-29a2-d759-73cdb1d540f4@inf.fu-berlin.de> Date: Thu, 14 Jun 2018 13:31:27 +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="------------E60464890C6FDF33777A62BC" 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::1528975887-000D4455-5591C3E8/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.004480, 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 Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture - June 18th 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, 14 Jun 2018 11:31:28 -0000 This is a multi-part message in MIME format. --------------E60464890C6FDF33777A62BC Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture on June 18th at 14:15 h at TU Berlin. *_Speaker_: Rico Zenklusen (ETH Zürich**)* *_Title_: **At the Interface of Combinatorial Optimization and Integer Programming * *_Time_: **Monday, June 18th - 14:15 h* *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Abstract_:* In this talk, I will show how techniques from Combinatorial Optimization and Combinatorics can be leveraged to achieve progress on a well-known question in Integer Programming, namely how to solve integer linear programs (ILPs) with bounded subdeterminants. More precisely, I will present an efficient (even strongly polynomial) algorithm to solve ILPs defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2}. This problem class naturally extends the well-known class of ILPs with a totally unimodular (TU) constraint matrix, i.e., where subdeterminants are within {-1,0,1}, and captures some open problems. We employ a variety of techniques common in Combinatorial Optimization, including polyhedral techniques, matroids, and submodular functions. In particular, using a polyhedral result of Veselov and Chirkov, we reduce the problem to a combinatorial one with a so-called parity constraint. We then show how a seminal, purely combinatorial result of Seymour on decomposing TU matrices, which is tightly related to regular matroids and was originally developed in this context, can be used algorithmically to break the problem into smaller ones. Finally, these smaller problems are amenable to combinatorial optimization techniques like parity-constrained submodular minimization. Additionally, I will highlight some of the many open problems in this field and discuss recent related results. /Exceptionally, there will be ///only this ///lecture and //no ///colloquium///./ -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------E60464890C6FDF33777A62BC Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture on June 18th at 14:15 h at TU Berlin.

Speaker: Rico Zenklusen (ETH Zürich)

Title: At the Interface of Combinatorial Optimization and Integer Programming

Time: Monday, June 18th - 14:15 h

Location:

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

Abstract:
In this talk, I will show how techniques from Combinatorial Optimization and Combinatorics can be leveraged to achieve progress on a well-known question in Integer Programming, namely how to solve integer linear programs (ILPs) with bounded subdeterminants. More precisely, I will present an efficient (even strongly polynomial) algorithm to solve ILPs defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2}. This problem class naturally extends the well-known class of ILPs with a totally unimodular (TU) constraint matrix, i.e., where subdeterminants are within {-1,0,1}, and captures some open problems. We employ a variety of techniques common in Combinatorial Optimization, including polyhedral techniques, matroids, and submodular functions. In particular, using a polyhedral result of Veselov and Chirkov, we reduce the problem to a combinatorial one with a so-called parity constraint. We then show how a seminal, purely combinatorial result of Seymour on decomposing TU matrices, which is tightly related to regular matroids and was originally developed in this context, can be used algorithmically to break the problem into smaller ones. Finally, these smaller problems are amenable to combinatorial optimization techniques like parity-constrained submodular minimization. Additionally, I will highlight some of the many open problems in this field and discuss recent related results.

Exceptionally, there will be only this lecture and no colloquium.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------E60464890C6FDF33777A62BC-- From i.brunke@inf.fu-berlin.de Thu Jun 21 16:03:16 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 <1fW0BA-000Jic-7u>; Thu, 21 Jun 2018 16:03:16 +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 <1fW0BA-003M7H-4D>; Thu, 21 Jun 2018 16:03:16 +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 <1fW0B9-003fMV-S1>; Thu, 21 Jun 2018 16:03:16 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <5dab334b-3cb8-fc76-549c-9529a079a99f@inf.fu-berlin.de> Date: Thu, 21 Jun 2018 16:03:15 +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="------------80C7536509466062F2E8F378" 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::1529589796-000D4455-8EA269D7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.459832, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lectures on June 25th 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, 21 Jun 2018 14:03:16 -0000 This is a multi-part message in MIME format. --------------80C7536509466062F2E8F378 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next *two* Monday Lectures on June 25th at 14:15 h & 16:00 h at TU Berlin. *_Location of the two Lectures_**: ** * *R**oom MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, June 25th - 14:15 h* *_Lecture_: Antoine Deza (Université Paris Sud)** * *_Title_: On lattice polytopes, convex matroid optimization, and degree sequences of hypergraphs * *_Abstract_:* We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type $B_d$. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII). _*Coffee & Tea Break*_*:*_* *_*R**oom MA 316 - Third Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, June 25th - 16:00 h* *_*_Lecture_*_: Matthias Beck*** *_Title_: Binomial Inequalities of Chromatic, Flow, and Ehrhart Polynomials * *_Abstract_:* A famous and wide-open problem, going back to at least the early 1970's, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute one such set of inequalities when a chromatic polynomial $\chi_G(n) = \chi^*_0 \binom {n+d} d + \chi^*_1 \binom {n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a binomial-coefficient basis. More precisely, we prove that $\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \ \chi^*_1+\chi^*_2+\dots+\chi^*_j $, for $1 \le j \le \lfloor \frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow polynomials enumerating either modular or integral nowhere-zero flows of a graph. Our theorems follow from connections among chromatic, flow, order, and Ehrhart polynomials, and the fact that the latter satisfy a decomposition formula into symmetric polynomials due to Stapledon. (This is joint work with Emerson Le\'on.) /Exceptionally, there will be two//////lectures and //no ///colloquium///./ -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------80C7536509466062F2E8F378 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next two Monday Lectures on June 25th at 14:15 h & 16:00 h at TU Berlin.

Location of the two Lectures:

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

Time: Monday, June 25th - 14:15 h

Lecture: Antoine Deza (Université Paris Sud)

Title: On lattice polytopes, convex matroid optimization, and degree sequences of hypergraphs

Abstract:
We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type $B_d$. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Coffee & Tea Break :

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

Time: Monday, June 25th - 16:00 h

Lecture: Matthias Beck

Title: Binomial Inequalities of Chromatic, Flow, and Ehrhart Polynomials

Abstract:
A famous and wide-open problem, going back to at least the early 1970's, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute one such set of inequalities when a chromatic polynomial $\chi_G(n) = \chi^*_0 \binom {n+d} d + \chi^*_1 \binom {n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a binomial-coefficient basis. More precisely, we prove that $\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \ \chi^*_1+\chi^*_2+\dots+\chi^*_j $, for $1 \le j \le \lfloor \frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow polynomials enumerating either modular or integral nowhere-zero flows of a graph. Our theorems follow from connections among chromatic, flow, order, and Ehrhart polynomials, and the fact that the latter satisfy a decomposition formula into symmetric polynomials due to Stapledon.

(This is joint work with Emerson Le\'on.)

Exceptionally, there will be two lectures and no colloquium.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------80C7536509466062F2E8F378-- From rolf.niedermeier@tu-berlin.de Mon Jun 25 19:35:08 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 <1fXVOO-0008HV-9j>; Mon, 25 Jun 2018 19:35:08 +0200 Received: from exchange.tu-berlin.de ([130.149.7.70]) 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 <1fXVOO-003XiP-4F>; Mon, 25 Jun 2018 19:35:08 +0200 Received: from SPMA-02.tubit.win.tu-berlin.de (localhost.localdomain [127.0.0.1]) by localhost (Email Security Appliance) with SMTP id DA0B036294_B3127CAB for ; Mon, 25 Jun 2018 17:35:06 +0000 (GMT) Received: from exchange.tu-berlin.de (exchange.tu-berlin.de [130.149.7.70]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (Client CN "exchange.tu-berlin.de", Issuer "DFN-Verein Global Issuing CA" (not verified)) by SPMA-02.tubit.win.tu-berlin.de (Sophos Email Appliance) with ESMTPS id 17ABA35CB5_B3127CAF for ; Mon, 25 Jun 2018 17:35:06 +0000 (GMT) Received: from [130.149.208.196] (130.149.208.196) by EX-MBX-04.tubit.win.tu-berlin.de (172.26.35.174) with Microsoft SMTP Server (TLS) id 15.0.1365.1; Mon, 25 Jun 2018 19:35:05 +0200 To: From: Rolf Niedermeier Message-ID: <26c43cff-ce51-065f-e903-c5f4abbaa525@tu-berlin.de> Date: Mon, 25 Jun 2018 19:35:05 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Language: en-US Content-Transfer-Encoding: 8bit X-ClientProxiedBy: EX-MBX05.tubit.win.tu-berlin.de (172.26.35.175) To EX-MBX-04.tubit.win.tu-berlin.de (172.26.35.174) X-PMWin-Version: 4.0.1, Antivirus-Engine: 3.72.1, Antivirus-Data: 5.52 X-PureMessage: [Scanned] X-SASI-RCODE: 200 X-Originating-IP: 130.149.7.70 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1529948108-000D4455-B9D2C7B5/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000137, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=0.7 required=5.0 tests=RCVD_IN_DNSWL_NONE, SPF_NEUTRAL, URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.1 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Symposium on Theoretical Aspects of Computer Science (STACS 2019) at TU Berlin, March 2019 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: Mon, 25 Jun 2018 17:35:08 -0000 STACS 2019 - Call for papers The 36th International Symposium on Theoretical Aspects of Computer Science March 13—16, 2019, TU Berlin, Berlin, Germany Authors are invited to submit papers presenting original and unpublished research on theoretical aspects of computer science. Typical areas include (but are not limited to): * algorithms and data structures, including: design of parallel, distributed, approximation, parameterized and randomized algorithms; analysis of algorithms and combinatorics of data structures; computational geometry, cryptography, algorithmic learning theory, algorithmic game theory; * automata and formal languages, including: algebraic and categorical methods, coding theory; * complexity and computability, including: computational and structural complexity theory, parameterized complexity, randomness in computation; * logic in computer science, including: finite model theory, database theory, semantics, specification verification, rewriting and deduction; * current challenges, for example: natural computing, quantum computing, mobile and net computing, computational social choice. INVITED SPEAKERS Leslie Ann Goldberg (Oxford) Anca Muscholl (Bordeaux) Petra Mutzel (Dortmund) PROGRAM COMMITTEE Christoph Berkholz (Berlin) Benedikt Bollig (Cachan) Karl Bringmann (Saarbrücken) Gerth Stølting Brodal (Aarhus) Maike Buchin (Bochum) David Eppstein (Irvine) Serge Gaspers (Sydney) Edward Hirsch (St. Petersburg) Telikepalli Kavitha (Mumbai) Hartmut Klauck (Singapore) Antonín Kučera (Brno) K Narayan Kumar (Chennai) Dietrich Kuske (Ilmenau) Jérôme Lang (Paris) Sophie Laplante (Paris) Kazuhisa Makino (Kyoto) Barnaby Martin (Durham) Cyril Nicaud (Marne-la-Vallée) Rolf Niedermeier (Berlin, co-chair) Jakob Nordström (Stockholm) Christophe Paul (Montpellier, co-chair) Pascal Schweitzer (Kaiserslautern) Shinnosuke Seki (Tokyo) Michał Skrzypczak (Warsaw) Srikanth Srinivasan (Mumbai) Jan Arne Telle (Bergen) Denis Trystram (Grenoble) Takeaki Uno (Tokyo) Mikhail Volkov (Ekaterinburg) Stefan Woltran (Wien) TUTORIALS There will be the following two tutorials taking place on March 13, 2019: Tobias Friedrich (HPI Potsdam): "Network Science" Karl Bringmann (MPI Saarbrücken): "Fine-Grained Complexity Theory" SUBMISSIONS Submissions can be uploaded to EasyChair: https://easychair.org/conferences/?conf=stacs2019. Authors are invited to submit a draft of a full paper with at most 12 pages (excluding the title page and the references section). The title page consists of the title of the paper, author information, and abstract. The usage of pdflatex and the LIPIcs style file (see http://www.dagstuhl.de/en/publications/lipics) are mandatory; no changes to font size, page geometry, etc. are permitted. Submissions not in the correct format or submitted after the deadline will not be considered. The paper should contain a succinct statement of the issues and of their motivation, a summary of the main results, and a brief explanation of their significance, accessible to non-specialist readers. Proofs omitted due to space constraints must be put into an appendix, to be read by the program committee members at their discretion. Simultaneous submission to other conferences with published proceedings or to journals is not allowed. PC members are excluded from submitting. There will be a rebuttal period for authors between November 26—29, 2019. Authors will receive the reviews of their submissions (via EasyChair) and have three days to submit rebuttals (via EasyChair). These rebuttals become part of the PC meeting, but entail no specific responses. PROCEEDINGS Accepted papers will be published in the proceedings of the symposium. As usual, these proceedings will appear in the Leibniz International Proceedings in Informatics (LIPIcs) series, based at Schloss Dagstuhl. This guarantees perennial, free and easy electronic access, while the authors retain the rights over their work. With their submission, authors consent to sign a license authorizing the program committee chairs to organize the electronic publication of their paper, provided the paper is accepted. IMPORTANT DATES * Deadline for submissions: October 1, 2018 (AoE) * Rebuttal: November 26–29, 2018 * Author notification: December 20, 2018 * Final version: January 16, 2019 * STACS 2019: March 13–16, 2019 CONTACT INFORMATION Web: https://stacs2019.akt.tu-berlin.de/ Email: stacs2019@akt.tu-berlin.de From i.brunke@inf.fu-berlin.de Wed Jun 27 20:21:09 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 <1fYF41-004673-3u>; Wed, 27 Jun 2018 20:21:09 +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 <1fYF40-001wgb-W1>; Wed, 27 Jun 2018 20:21:09 +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 <1fYF40-002wHH-PH>; Wed, 27 Jun 2018 20:21:08 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <451ff52a-3e35-843e-b299-8db27b6a613b@inf.fu-berlin.de> Date: Wed, 27 Jun 2018 20:21:08 +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="------------6042C6795519D85BC69FF2AF" 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::1530123669-000D4455-A066D611/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.010058, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 2nd 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, 27 Jun 2018 18:21:09 -0000 This is a multi-part message in MIME format. --------------6042C6795519D85BC69FF2AF 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 2nd at 14:15 h & 16:00 h at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, July 2nd - 14:15 h* *_Lecture_: Benjamin Burton  (University**of Queensland, Australia)* *_Title_: From parameterised to non-parameterised algorithms in knot theory* *_Abstract_:* We describe some recent developments in treewidth-based algorithms for knots, which exploit the structure of the underlying 4-valent planar graph. In particular, we show how these led to the first general sub-exponential-time algorithm for the HOMFLY-PT polynomial, and we describe some recent progress on parameterised algorithms for unknot recognition. _*Coffee & Tea Break*_ *_Time_: **Monday, July 2nd - 16:00 h* *_Colloquium_: Laith Rastanawi (Freie Universität Berlin**)* *_Title_: On the Dimension of the Realization Spaces of Polytopes * *_Abstract_:* The study of realization spaces of convex polytopes is one of the oldest subjects in Polytope Theory. Most likely, it goes back to Legendre (1794).  A lot of progress took place since that time. However, many questions remained open. In general, computing the dimension of the realization space $\mathcal{R}(P)$ of a d-polytope $P$ is hard, even for $d = 4$, as shown by Mnëv (1988) and Richter-Gebert (1996).In this presentation, we will discuss two criteria to determine the dimension of the realization space, and use them to show that $\dim \mathcal{R}(P) = f_1(P) + 6$ for a 3-polytope $P$, and $\dim \mathcal{R}(P) = df_{d-1}(P)$ (resp. $\dim \mathcal{R}(P) = df_0(P)$ ) for a simple (resp. simplicial) $d$-polytope $P$. We will also discuss the realization spaces of some interesting 2-simple 2-simplicial 4-polytopes. Namely, we will consider the realization space of the 24-cell and of a 2s2s polytope with 12 vertices which was found by Miyata (2011), and give a better bound for/determine its dimension. -- Graduiertenkolleg 'Facets of Complexity'www.facetsofcomplexity.de/monday --------------6042C6795519D85BC69FF2AF Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 2nd - 14:15 h

Lecture: Benjamin Burton  (University of Queensland, Australia)

Title: From parameterised to non-parameterised algorithms in knot theory

Abstract:

We describe some recent developments in treewidth-based algorithms for knots, which exploit the structure of the underlying 4-valent planar graph. In particular, we show how these led to the first general sub-exponential-time algorithm for the HOMFLY-PT polynomial, and we describe some recent progress on parameterised algorithms for unknot recognition.


Coffee & Tea Break

Time: Monday, July 2nd - 16:00 h

Colloquium: Laith Rastanawi (Freie Universität Berlin)

Title: On the Dimension of the Realization Spaces of Polytopes

Abstract:
The study of realization spaces of convex polytopes is one of the oldest subjects in Polytope Theory. Most likely, it goes back to Legendre (1794).  A lot of progress took place since that time. However, many questions remained open. In general, computing the dimension of the realization space $\mathcal{R}(P)$ of a d-polytope $P$ is hard, even for $d = 4$, as shown by Mnëv (1988) and Richter-Gebert (1996).In this presentation, we will discuss two criteria to determine the dimension of the realization space, and use them to show that $\dim \mathcal{R}(P) = f_1(P) + 6$ for a 3-polytope $P$, and $\dim \mathcal{R}(P) = df_{d-1}(P)$ (resp. $\dim \mathcal{R}(P) = df_0(P)$ ) for a simple (resp. simplicial) $d$-polytope $P$. We will also discuss the realization spaces of some interesting 2-simple 2-simplicial 4-polytopes. Namely, we will consider the realization space of the 24-cell and of a 2s2s polytope with 12 vertices which was found by Miyata (2011), and give a better bound for/determine its dimension.
-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday
--------------6042C6795519D85BC69FF2AF-- 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. From i.brunke@inf.fu-berlin.de Thu Oct 18 12:56:10 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 <1gD5yM-004BnM-C7>; Thu, 18 Oct 2018 12:56: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 <1gD5yM-001nYV-8R>; Thu, 18 Oct 2018 12:56: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:AES128-SHA:128) (envelope-from ) id <1gD5yL-002tvK-MQ>; Thu, 18 Oct 2018 12:56:10 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 18 Oct 2018 12:56:09 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------552737630548D06E74A94E33" 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::1539860170-000004D7-54EB5312/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.013416, 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 - October 22nd 2018 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: Thu, 18 Oct 2018 10:56:10 -0000 This is a multi-part message in MIME format. --------------552737630548D06E74A94E33 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our Monday Lecture & Colloquium on October 22nd 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, October 22nd - 14:15 h* *_Lecture_: Alexander Fink (Queen Mary University London)* *_Title_: Stiefel tropical linear spaces * *_Abstract_:* As we tell our undergraduates, if K is a field, then there are a great number of different ways to describe a linear subspace of K^n. If the base is an algebraic object with less structure than a field, linear algebra becomes more subtle, and some of these descriptions cease to agree. One such setting is tropical geometry. Tropical geometers have reached consensus as to what the "correct" notion of tropical linear subspace is (one way to get it is by a vector of determinants). My subject will be one of the "wrong" descriptions, namely row spaces of matrices, which only produces a subset of the tropical linear spaces. Applications include generalisations of Mason's results from the '70s on presentations of transversal matroids, and a construction in the new area of tropical ideal theory. This work is variously joint with Felipe Rinc\'on, Jorge Alberto Olarte, and Jeffrey and Noah Giansiracusa. _*Coffee & Tea Break*_*:*_* *_* R**oom MA 316 - Third Floor* *_Time_: **Monday, ***October 22nd* - 16:00 h* *_Colloquium_: Akiyoshi Tsuchiya (Osaka University) * *_Title_: Polyhedral characterizations of perfect graphs * *_Abstract_:* Perfect graphs are important objects in graph theory. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs. Our interest is to give other characterizations of perfect graphs. In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes. This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi. --------------552737630548D06E74A94E33 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our Monday Lecture & Colloquium on October 22nd 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, October 22nd - 14:15 h

Lecture: Alexander Fink (Queen Mary University London)

Title: Stiefel tropical linear spaces

Abstract:

As we tell our undergraduates, if K is a field, then there are a great number of different ways to describe a linear subspace of K^n. If the base is an algebraic object with less structure than a field, linear algebra becomes more subtle, and some of these descriptions cease to agree. One such setting is tropical geometry. Tropical geometers have reached consensus as to what the "correct" notion of tropical linear subspace is (one way to get it is by a vector of determinants). My subject will be one of the "wrong" descriptions, namely row spaces of matrices, which only produces a subset of the tropical linear spaces. Applications include generalisations of Mason's results from the '70s on presentations of transversal matroids, and a construction in the new area of tropical ideal theory.

This work is variously joint with Felipe Rinc\'on, Jorge Alberto Olarte, and Jeffrey and Noah Giansiracusa.


Coffee & Tea Break :

Room MA 316 - Third Floor

Time: Monday, October 22nd - 16:00 h

Colloquium: Akiyoshi Tsuchiya (Osaka University)

Title: Polyhedral characterizations of perfect graphs

Abstract:

Perfect graphs are important objects in graph theory. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs. Our interest is to give other characterizations of perfect graphs. In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes.

This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi.

--------------552737630548D06E74A94E33-- From i.brunke@inf.fu-berlin.de Thu Oct 25 12:59:40 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 <1gFdMa-002AcH-1Q>; Thu, 25 Oct 2018 12:59:40 +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 <1gFdMZ-0042O6-UR>; Thu, 25 Oct 2018 12:59:39 +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:AES128-SHA:128) (envelope-from ) id <1gFdMZ-001Ehe-OV>; Thu, 25 Oct 2018 12:59:39 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <05215f79-79f1-6f49-ac44-e957ea1ec52a@inf.fu-berlin.de> Date: Thu, 25 Oct 2018 12:59:39 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------B0C79390DF0CF419FB05C14C" 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::1540465180-000004D7-0BA83D89/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.426363, 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 Colloquium - October 29th 2018 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: Thu, 25 Oct 2018 10:59:40 -0000 This is a multi-part message in MIME format. --------------B0C79390DF0CF419FB05C14C Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Colloquium on October 29th at 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, October 29th - 16:00 h* *_Colloquium_: Jan Goedgebeur (Ghent University**)* *_Title_: **Obstructions for 3-coloring graphs with one forbidden induced subgraph* *_Abstract_:* For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 denotes the induced path on six vertices.) Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand. In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths. This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong. /Exceptionally, there will be no lecture and only this colloquium, because of the 'Einstein Workshop'./ --------------B0C79390DF0CF419FB05C14C Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Colloquium on October 29th at 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, October 29th - 16:00 h

Colloquium: Jan Goedgebeur (Ghent University)

Title: Obstructions for 3-coloring graphs with one forbidden induced subgraph

Abstract:

For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 denotes the induced path on six vertices.) Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand. In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths.

This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.

Exceptionally, there will be no lecture and only this colloquium, because of the 'Einstein Workshop'.
--------------B0C79390DF0CF419FB05C14C-- From i.brunke@inf.fu-berlin.de Thu Nov 01 12:41:47 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 <1gIBMA-003HfU-TZ>; Thu, 01 Nov 2018 12:41:47 +0100 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 <1gIBMA-002hjB-QB>; Thu, 01 Nov 2018 12:41:46 +0100 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:AES128-SHA:128) (envelope-from ) id <1gIBMA-0030HW-Fu>; Thu, 01 Nov 2018 12:41:46 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <9b0d8627-1fe0-395c-8611-947a824400ff@inf.fu-berlin.de> Date: Thu, 1 Nov 2018 12:41:46 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------48B0CBBC3FF41BA60B153F33" 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::1541072506-000004BE-2F4D1F79/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.095215, 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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 5th 2018 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: Thu, 01 Nov 2018 11:41:47 -0000 This is a multi-part message in MIME format. --------------48B0CBBC3FF41BA60B153F33 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our Monday Lecture & Colloquium on November 5th at 14:15 h & 16:00 h at HU Berlin. *_Location_**: ** * *Room 3.408 (House 3 / 4th Floor)* *[British Reading]* Humboldt-Universität zu Berlin Institut für Informatik Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin *_Time_: **Monday, November 5th - 14:15 h* *_Lecture_: Henning Meyerhenke (Humboldt-Universität zu Berlin)* *_Title_: Algorithms for Large-scale Network Analysis * *_Abstract_:* Network centrality measures indicate the importance of nodes (or edges) in a network. In this talk we will discuss a few popular measures and algorithms for computing complete or partial node rankings based on these measures. These algorithms are implemented in NetworKit, an open-source framework for large-scale network analysis, on which we provide an overview, too. One focus of the talk will be on techniques for speeding up a greedy (1-1/e)-approximation algorithm for the NP-hard group closeness centrality problem. Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to a heuristic proposed by Chen et al., we always find a solution with better quality in a comparable running time in our experiments. Our method Greedy++ allows us to approximate the group with maximum closeness centrality on networks with up to hundreds of millions of edges in minutes or at most a few hours. In a comparison with the optimum, our experiments show that the solution found by Greedy++ is actually much better than the theoretical guarantee. _*Coffee & Tea Break*_*:*_* *_* **Room 3.321 (House 3 / 3rd Floor)* *[British Reading]* *_Time_: **Monday, ***November 5th* - 16:00 h* *_Colloquium_: Alexander van der Grinten (Universität zu Köln) * *_Title_: Scalable Katz Ranking Computation * *_Abstract_:* Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds. --------------48B0CBBC3FF41BA60B153F33 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our Monday Lecture & Colloquium on November 5th at 14:15 h & 16:00 h at HU Berlin.

Location:

Room 3.408 (House 3 / 4th Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 5th - 14:15 h

Lecture: Henning Meyerhenke (Humboldt-Universität zu Berlin)

Title: Algorithms for Large-scale Network Analysis

Abstract:

Network centrality measures indicate the importance of nodes (or edges) in a network. In this talk we will discuss a few popular measures and algorithms for computing complete or partial node rankings based on these measures. These algorithms are implemented in NetworKit, an open-source framework for large-scale network analysis, on which we provide an overview, too.

One focus of the talk will be on techniques for speeding up a greedy (1-1/e)-approximation algorithm for the NP-hard group closeness centrality problem.
Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to a heuristic proposed by Chen et al., we always find a solution with better quality in a comparable running time in our experiments. Our
method Greedy++ allows us to approximate the group with maximum closeness centrality on networks with up to hundreds of millions of edges in minutes or at most a few hours.
In a comparison with the optimum, our experiments show that the solution found by Greedy++ is actually much better than the theoretical guarantee.


Coffee & Tea Break :

Room 3.321 (House 3 / 3rd Floor) [British Reading]

Time: Monday, November 5th - 16:00 h

Colloquium: Alexander van der Grinten (Universität zu Köln)

Title: Scalable Katz Ranking Computation

Abstract:

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

--------------48B0CBBC3FF41BA60B153F33-- From i.brunke@inf.fu-berlin.de Thu Nov 08 12:19:07 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 <1gKiL4-003eTb-A0>; Thu, 08 Nov 2018 12:19:06 +0100 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 <1gKiL4-001r5u-6L>; Thu, 08 Nov 2018 12:19:06 +0100 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:AES128-SHA:128) (envelope-from ) id <1gKiL3-0021Ms-Op>; Thu, 08 Nov 2018 12:19:06 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <4dad45c3-2c8b-2d53-4888-2622904632c7@inf.fu-berlin.de> Date: Thu, 8 Nov 2018 12:19:05 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------6EB16D1C3B5AC5F9FE472636" 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::1541675946-000004BE-C69975B0/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.014971, 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.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 12th 2018 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: Thu, 08 Nov 2018 11:19:07 -0000 This is a multi-part message in MIME format. --------------6EB16D1C3B5AC5F9FE472636 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our Monday Lecture & Colloquium on November 12th at 14:15 h & 16:00 h at HU Berlin. *_Location_**: ** * *Humboldt-Kabinett (between House 3&4 / 1st Floor)* *[British Reading]* Humboldt-Universität zu Berlin Institut für Informatik Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin *_Time_: **Monday, November 12th - 14:15 h* *_Lecture_: Christoph Berkholz (Humboldt-Universität zu Berlin)* *_Title_: **A comparison of algebraic and semi-algebraic proof systems * *_Abstract_:* In this lecture I will give an introduction to algebraic and semi-algebraic methods for proving the unsatisfiability of systems of real polynomial equations over the Boolean hypercube. The main goal of this talk is to compare the relative strength of these approaches using methods from proof complexity. On the one hand, I will focus on the static semi-algebraic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, I will discuss polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations. I am going to present two recent results on the relative strength between algebraic and semi-algebraic proof systems:¹ The first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree d can be transformed into a sum-of-squares refutation of degree 2d and only polynomial increase in size. In contrast, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree 3 and polynomial size, but require Sherali-Adams refutations of large degree and exponential size. ¹) this work was presented at STACS 2018; a preprint is available at https://eccc.weizmann.ac.il/report/2017/154/ _*Coffee & Tea Break*_*:*_* *_* Before ***Humboldt-Kabinett (between House 3&4 / 1st Floor)* *[British Reading]* * *_Time_: **Monday, ***November 12th* - 16:00 h* *_Colloquium_: Till Fluschnik (Technische Universität Berlin) * *_Title_: Fractals for Kernelization Lower Bounds* *_Abstract_:* Kernelization is a key concept in fixed-parameter algorithmics for polynomial-time preprocessing of NP-hard problems. Herein one seeks to preprocess any instance of a parameterized problem with parameter k to an “equivalent” instance (the so-called (problem) kernel) with size upper-bounded by some function (preferably by some polynomial) in k. Ten years ago, with the development of the so-called composition technique, first NP-hard parameterized problems were proven to presumably admit no polynomial-size problem kernel. Since then the line of Research concerning "limits of kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of graph problems dealing with some sort of cuts, hereby answering an open question stated in 2009. Our T-fractals---due to their fractal structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier. (Journal version appeared in SIAM Journal on Discrete Mathematics 2018.) --------------6EB16D1C3B5AC5F9FE472636 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our Monday Lecture & Colloquium on November 12th at 14:15 h & 16:00 h at HU Berlin.

Location:

Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 12th - 14:15 h

Lecture: Christoph Berkholz (Humboldt-Universität zu Berlin)

Title: A comparison of algebraic and semi-algebraic proof systems

Abstract:

In this lecture I will give an introduction to algebraic and semi-algebraic methods for proving the unsatisfiability of systems of real polynomial equations over the Boolean hypercube. The main goal of this talk is to compare the relative strength of these approaches using methods from proof complexity.
On the one hand, I will focus on the static semi-algebraic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, I will discuss polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations.
I am going to present two recent results on the relative strength between algebraic and semi-algebraic proof systems:¹
The first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree d can be transformed into a sum-of-squares refutation of degree 2d and only polynomial increase in size. In contrast, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree 3 and polynomial size, but require Sherali-Adams refutations of large degree and exponential size.

¹) this work was presented at STACS 2018; a preprint is available at https://eccc.weizmann.ac.il/report/2017/154/


Coffee & Tea Break :

Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]

Time: Monday, November 12th - 16:00 h

Colloquium: Till Fluschnik (Technische Universität Berlin)

Title: Fractals for Kernelization Lower Bounds

Abstract:

Kernelization is a key concept in fixed-parameter algorithmics for polynomial-time preprocessing of NP-hard problems. Herein one seeks to preprocess any instance of a parameterized problem with parameter k to an “equivalent” instance (the so-called (problem) kernel) with size upper-bounded by some function (preferably by some polynomial) in k. Ten years ago, with the development of the so-called composition technique, first NP-hard parameterized problems were proven to presumably admit no polynomial-size problem kernel. Since then the line of Research concerning "limits of kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of graph problems dealing with some sort of cuts, hereby answering an open question stated in 2009. Our T-fractals---due to their fractal structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier.
(Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)
--------------6EB16D1C3B5AC5F9FE472636-- From i.brunke@inf.fu-berlin.de Thu Nov 15 14:06:23 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 <1gNHLj-003ZQG-5p>; Thu, 15 Nov 2018 14:06:23 +0100 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 <1gNHLj-002Kcy-2e>; Thu, 15 Nov 2018 14:06:23 +0100 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:AES128-SHA:128) (envelope-from ) id <1gNHLi-000KHC-Md>; Thu, 15 Nov 2018 14:06:23 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <094267fd-ddfa-91a2-30f7-964f2404a8ee@inf.fu-berlin.de> Date: Thu, 15 Nov 2018 14:06:22 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------86EBBCF3B65B9D6142037AA1" 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::1542287183-000004BE-4EC51FC0/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.011713, 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.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 19th 2018 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: Thu, 15 Nov 2018 13:06:23 -0000 This is a multi-part message in MIME format. --------------86EBBCF3B65B9D6142037AA1 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our Monday Lecture & Colloquium on November 19th 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, November 19th - 14:15 h* *_Lecture_: Jörg Rambau (Universität Bayreuth)* *_Title_: **Optimal Diplomacy * *_Abstract_:* Picture yourself in a committee numerically evaluating a scientific proposal that you find worth funding: A rating of "0" means "easily achievable but not at all innovative", whereas "1" means "very innovative but totally unachievable". In both cases, funding is not recommended. In contrast, "1/2" means "innovative and achievable", in other words: worth funding. All intermediate values are possible. Any rating that is closer to "1/2" than to "1/4" and "3/4" is considered a vote for funding. The proposal passes if 50% of the members support funding, i.e., rate the proposal between "1/2 - 1/8" and "1/2 + 1/8". Now, there are 10 meetings ahead of you. You have an idea how the opinions of the committee members develop. How should your statements look like in the meetings one through ten if you want to have eventually as many supporters of the proposal as possible? This is an instance of the "Optimal Diplomacy Problem" (ODP), introduced by Hegselmann, König, Kurz, Niemann, and Rambau in 2010, published in 2015. How do opinions interact? How is the dynamics of opinions modeled mathematically? What does it mean to "influence others" in this dynamical system? How difficult is it to find optimal diplomacies? How can one compute or at least narrow down optimal diplomacies? What happens if not all informations about committee members are known to the diplomat? In this talk we will discuss our findings, techniques, and open questions based on the arguably most influential model: the Bounded-Confidence model by Hegselmann and Krause. We draw on joint work with Andreas Deuerling, Rainer Hegselmann, Stefan König, Julia Kinkel, Sascha Kurz, and Christoph Niemann. _*Coffee & Tea Break*_*:*_* *_* **R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***November 19th* - 16:00 h* *_Colloquium_: Jean-Philippe Labbé (Freie Universität Berlin) * *_Title_: (At least) three hard problems behind the multiassociahedron * *_Abstract_:* The associahedron has a natural extension called the multiassociahedron. It is a vertex-decomposable simplicial sphere (in other words, a "combinatorially nice" sphere). Since at least 2003, people tried to construct simplicial polytopes, whose boundary is this simplicial complex, with limited success. In this talk, I will reveal (at least) three combinatorial "known-to-be-challenging" computational problems which should be indispensably faced to solve this problem. --------------86EBBCF3B65B9D6142037AA1 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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

Lecture: Jörg Rambau (Universität Bayreuth)

Title: Optimal Diplomacy

Abstract:

Picture yourself in a committee numerically evaluating a scientific proposal that you find worth funding: A rating of "0" means "easily achievable but not at all innovative", whereas "1" means "very innovative but totally unachievable". In both cases, funding is not recommended. In contrast, "1/2" means "innovative and achievable", in other words: worth funding. All intermediate values are possible. Any rating that is closer to "1/2" than to "1/4" and "3/4" is considered a vote for funding. The proposal passes if 50% of the members support funding, i.e., rate the proposal between "1/2 - 1/8" and "1/2 + 1/8". Now, there are 10 meetings ahead of you. You have an idea how the opinions of the committee members develop. How should your statements look like in the meetings one through ten if you want to have eventually as many supporters of the proposal as possible? This is an instance of the "Optimal Diplomacy Problem" (ODP), introduced by Hegselmann, König, Kurz, Niemann, and Rambau in 2010, published in 2015. How do opinions interact? How is the dynamics of opinions modeled mathematically? What does it mean to "influence others" in this dynamical system? How difficult is it to find optimal diplomacies? How can one compute or at least narrow down optimal diplomacies? What happens if not all informations about committee members are known to the diplomat? In this talk we will discuss our findings, techniques, and open questions based on the arguably most influential model: the Bounded-Confidence model by Hegselmann and Krause. We draw on joint work with Andreas Deuerling, Rainer Hegselmann, Stefan König, Julia Kinkel, Sascha Kurz, and Christoph Niemann.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]

Time: Monday, November 19th - 16:00 h

Colloquium: Jean-Philippe Labbé (Freie Universität Berlin)

Title: (At least) three hard problems behind the multiassociahedron

Abstract:

The associahedron has a natural extension called the multiassociahedron. It is a vertex-decomposable simplicial sphere (in other words, a "combinatorially nice" sphere). Since at least 2003, people tried to construct simplicial polytopes, whose boundary is this simplicial complex, with limited success. In this talk, I will reveal (at least) three combinatorial "known-to-be-challenging" computational problems which should be indispensably faced to solve this problem.
--------------86EBBCF3B65B9D6142037AA1-- From i.brunke@inf.fu-berlin.de Tue Nov 20 16:25: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 <1gP7tx-001Fwc-FY>; Tue, 20 Nov 2018 16:25:21 +0100 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 <1gP7tx-003SR9-Bq>; Tue, 20 Nov 2018 16:25:21 +0100 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:AES128-SHA:128) (envelope-from ) id <1gP7tx-001aBR-3H>; Tue, 20 Nov 2018 16:25:21 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <363b9caf-c453-2b7f-75e3-26f53f3dd20b@inf.fu-berlin.de> Date: Tue, 20 Nov 2018 16:25:21 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------8AD132702276B7DB3B5F6A7A" 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::1542727521-000004BE-9691B086/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.152508, 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.2 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 26th 2018 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: Tue, 20 Nov 2018 15:25:22 -0000 This is a multi-part message in MIME format. --------------8AD132702276B7DB3B5F6A7A Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our Monday Lecture & Colloquium on November 26th at 14:15 h & 16:00 h at HU Berlin. *_Location_**: ** * *Humboldt-Kabinett (between House 3&4 / 1st Floor)* *[British Reading]* Humboldt-Universität zu Berlin Institut für Informatik Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin *_Time_: **Monday, November 26th - 14:15 h* *_Lecture_: Marcin Pilipczuk (University of Warsaw)* *_Title_: **The square root phenomenon: subexponential algorithms in sparse graph classes * *_Abstract_:* While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches. _*Coffee & Tea Break*_*:*_* *_* Before ***Humboldt-Kabinett (between House 3&4 / 1st Floor)* *[British Reading]* * *_Time_: **Monday, ***November 26th* - 16:00 h* *_Colloquium_: Sebastian Siebertz (Humboldt-Universität zu Berlin) * *_Title_: First-order interpretations of sparse graph classes* *_Abstract_:* The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal. --------------8AD132702276B7DB3B5F6A7A Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our Monday Lecture & Colloquium on November 26th at 14:15 h & 16:00 h at HU Berlin.

Location:

Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 26th - 14:15 h

Lecture: Marcin Pilipczuk (University of Warsaw)

Title: The square root phenomenon: subexponential algorithms in sparse graph classes

Abstract:

While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

Coffee & Tea Break :

Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]

Time: Monday, November 26th - 16:00 h

Colloquium: Sebastian Siebertz (Humboldt-Universität zu Berlin)

Title: First-order interpretations of sparse graph classes

Abstract:

The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal.
--------------8AD132702276B7DB3B5F6A7A-- From rote@inf.fu-berlin.de Mon Dec 03 11:33: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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gTlXV-001UiF-GN>; Mon, 03 Dec 2018 11:33:21 +0100 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gTlXV-0018dF-Ea>; Mon, 03 Dec 2018 11:33:21 +0100 Received: from dslb-178-012-117-018.178.012.pools.vodafone-ip.de ([178.12.117.18] helo=[192.168.178.36]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:AES128-SHA:128) (envelope-from ) id <1gTlXV-002pLk-5R>; Mon, 03 Dec 2018 11:33:21 +0100 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de Message-ID: <0cc13894-bf20-8f25-4d84-b08bea510df2@inf.fu-berlin.de> Date: Mon, 3 Dec 2018 11:33:16 +0100 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-CA Content-Transfer-Encoding: 8bit X-Originating-IP: 178.12.117.18 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1543833201-0005565A-EE9D5892/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.028377, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquium - Dec 3, 2018 - TODAY 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, 03 Dec 2018 10:33:22 -0000 You are cordially invited to our Monday Lecture & Colloquium on Dec 3rd at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, Dec 3rd - 14:15 h =============================================== László Kozma (Freie Universität Berlin): Self-adjusting data structures: trees and heaps =============================================== Abstract: Binary search trees (BSTs) and heaps are perhaps the simplest implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about them remain open. What is the best strategy for updating a BST in response to queries? Is there a single strategy that is optimal for every possible scenario? Are self-adjusting trees ("splay trees", Sleator and Tarjan, 1983) optimal? In which cases can we improve upon the logarithmic worst-case cost per operation? Our understanding of heaps is even more limited. Fibonacci heaps (and their relatives) are theoretically optimal in a worst-case sense, but they perform operations outside the "pure" comparison-based heap model (in addition to being complicated in practice). Is there a simple, "self-adjusting" alternative to Fibonacci heaps? Is there, by analogy to BSTs, a heap that can adapt to regularities in the input? Are the two problems related? In my talk I will present some old and new results pertaining to this family of questions. Coffee & Tea Break Colloquium: 16:00 h =============================================================== Petr Gregor (Charles University, Prague): Incidence colorings of subquartic graphs and Cartesian products =============================================================== Abstract: Two incidences (u,e) and (v,f) of vertices u, v and edges e, f (respectively) are adjacent if u=v, or e=f, or uv is one of edges e, f. An incidence coloring of a graph G is a coloring of its incidences such that adjacent incidences have distinct colors. We show that every graph of maximal degree 4 has an incidence coloring with 7 colors. Furthermore, we present sufficient conditions for Cartesian product graphs to have incidence colorings with Delta+2 colors where Delta is the maximal degree. In particular, we confirm a conjecture of Pai et al. on incidence colorings of hypercubes. Joint work with B. Lužar and R. Soták. Location: Room 005 - Ground Floor Freie Universität Berlin Takustr. 9 14195 Berlin From i.brunke@inf.fu-berlin.de Thu Dec 06 17:03:24 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gUw7Y-000A9C-1D>; Thu, 06 Dec 2018 17:03:24 +0100 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gUw7X-001a1z-VF>; Thu, 06 Dec 2018 17:03:23 +0100 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:AES128-SHA:128) (envelope-from ) id <1gUw7X-002vsw-Nr>; Thu, 06 Dec 2018 17:03:23 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <59fca3af-c4c9-32df-9796-efdfcaaffd73@inf.fu-berlin.de> Date: Thu, 6 Dec 2018 17:03:23 +0100 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.3.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------0B873EBE9050253E371C2135" 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::1544112204-0002A4D2-5A6AB7C7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.318117, 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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - December 10th 2018 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: Thu, 06 Dec 2018 16:03:24 -0000 This is a multi-part message in MIME format. --------------0B873EBE9050253E371C2135 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on December 10th at 14:15 h & 16:00 h at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, December 10th - 14:15 h* *_Lecture_: Marijn Heule (University**of Texas, Austin)* *_Title_: Everything's Bigger in Texas: "The Largest Math Proof Ever" * *_Abstract_:* Progress in satisfiability (SAT) solving has enabled answering long-standing open questions in mathematics completely automatically resulting in clever though potentially gigantic proofs. We illustrate the success of this approach by presenting the solution of the Boolean Pythagorean triples problem. We also produced and validated a proof of the solution, which has been called the ``largest math proof ever''. The enormous size of the proof is not important. In fact a shorter proof would have been preferable. However, the size shows that automated tools combined with super computing facilitate solving bigger problems. Moreover, the proof of 200 terabytes can now be validated using highly trustworthy systems, demonstrating that we can check the correctness of proofs no matter their size. _*Coffee & Tea Break*_ *Room 134* *_Time_: **Monday, ***December 10th* - 16:00 h s.t.* *_Colloquium_: Ander Lamaison (Freie Universität Berlin**)* *_Title_: Ramsey density of infinite paths * *_Abstract_:* In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a two-colouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang. --------------0B873EBE9050253E371C2135 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

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

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, December 10th - 14:15 h

Lecture: Marijn Heule (University of Texas, Austin)

Title: Everything's Bigger in Texas: "The Largest Math Proof Ever"

Abstract:

Progress in satisfiability (SAT) solving has enabled answering long-standing open questions in mathematics completely automatically resulting in clever though potentially gigantic proofs. We illustrate the success of this approach by presenting the solution of the Boolean Pythagorean triples problem. We also produced and validated a proof of the solution, which has been called the ``largest math proof ever''. The enormous size of the proof is not important. In fact a shorter proof would have been preferable. However, the size shows that automated tools combined with super computing facilitate solving bigger problems. Moreover, the proof of 200 terabytes can now be validated using highly trustworthy systems, demonstrating that we can check the correctness of proofs no matter their size.


Coffee & Tea Break
Room 134

Time: Monday, December 10th - 16:00 h s.t.

Colloquium: Ander Lamaison (Freie Universität Berlin)

Title: Ramsey density of infinite paths

Abstract:
In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a two-colouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang.
--------------0B873EBE9050253E371C2135-- From rote@inf.fu-berlin.de Fri Dec 14 11:58:14 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gXlAb-000C2i-Q1>; Fri, 14 Dec 2018 11:58:14 +0100 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gXlAb-000ERE-Ns>; Fri, 14 Dec 2018 11:58:13 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:AES128-SHA:128) (envelope-from ) id <1gXlAb-000b3M-Hw>; Fri, 14 Dec 2018 11:58:13 +0100 References: <0cc13894-bf20-8f25-4d84-b08bea510df2@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= X-Forwarded-Message-Id: <0cc13894-bf20-8f25-4d84-b08bea510df2@inf.fu-berlin.de> Message-ID: Date: Fri, 14 Dec 2018 11:58:13 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.3.0 MIME-Version: 1.0 In-Reply-To: <0cc13894-bf20-8f25-4d84-b08bea510df2@inf.fu-berlin.de> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1544785093-000901CF-BEF2C51D/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.030365, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquium - Dec 17, 2018 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: Fri, 14 Dec 2018 10:58:14 -0000 You are invited to our Monday Lecture & Colloquium on Dec 17th at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, Dec 17th - 14:15 h =============================================== Shagnik Das (Freie Universität Berlin): Randomly perturbed Ramsey problems =============================================== Abstract: The combinatorial properties much-loved Erdős-Rényi random graph G(n,p), which has n vertices and whose edges are present independently with probability p, have been comprehensively studied in the decades since its introduction. In recent years, much research has been devoted to the randomly perturbed graph model, introduced in 2003 by Bohman, Frieze and Martin. In this talk we shall present and motivate this new model of random graphs, and then focus on the Ramsey properties of these randomly perturbed graphs. More precisely, given a pair of graphs (F,H), we ask how many random edges must be added to a dense graph G to ensure that any two-colouring of the edges of the perturbed graph has either a red copy of F or a blue copy of G. This question was first studied in 2006 by Krivelevich, Sudakov and Tetali, who answered it in the case of F being a triangle and H being a clique. We generalise these results, considering pairs of larger cliques, and, should the audience be willing (but even otherwise), shall take a quick look at some of the ideas required in our proofs. This is joint work with Andrew Treglown (Birmingham). Coffee & Tea Break Colloquium: 16:00 h =============================================================== Marie Brandenburg (Freie Universität Berlin): Product-Mix Auctions, Competitive Equilibrium and Lattice Polytopes =============================================================== Abstract: In 2007, when the credit crisis began, the Bank of England approached the economist Paul Klemperer with the need of a new auction design that would enable them to give liquidity to all banks in an economically efficient way. Since then, Klemperer’s Product-Mix Auction design became more and more relevant, with particular interest in when competitive equilibrium exists, that is, when a set of (indivisible) goods can be split such that exactly one bid of each bidder is fulfilled. Originally being a question of economics, this can be translated into a question of specific lattice polytopes that rely on underlying graphs. I will present the Product-Mix Auction setting, the translation to polytopes and first results on when competitive equilibrium exists. Location: Room 005 - Ground Floor Freie Universität Berlin Takustr. 9 14195 Berlin From rote@inf.fu-berlin.de Sun Dec 30 01:29:47 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gdOzD-002YMl-Gx>; Sun, 30 Dec 2018 01:29:47 +0100 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:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1gdOzD-0000ns-EY>; Sun, 30 Dec 2018 01:29:47 +0100 Received: from z0ec3.pia.fu-berlin.de ([87.77.14.195]) 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 <1gdOzD-002nCv-2X>; Sun, 30 Dec 2018 01:29:47 +0100 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: Message-ID: <7f002bd3-b362-9102-de49-adeb94711989@inf.fu-berlin.de> Date: Sun, 30 Dec 2018 01:29:54 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 87.77.14.195 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1546129787-0008B5E6-634BFDB2/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.125440, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] New Year's Monday Lecture & Colloquium - Jan 7, 2019 at FU 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: Sun, 30 Dec 2018 00:29:48 -0000 You are invited to our Monday Lecture & Colloquium on Jan 7th, 2019 at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, January 7th - 14:15 h =============================================== Péter Pál Pach (Budapest University of Technology and Economics): The polynomial method and the cap set problem =============================================== Abstract: In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z_4^n (Croot, Lev and myself) and Z_3^n (Ellenberg and Gijswijt) are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets, including some recent bounds found by Elsholtz and myself. We will also mention some further applications of the method, for instance, the solution of the Erdős-Szemerédi sunflower conjecture. Coffee & Tea Break: Room 134 Colloquium: 16:00 h =============================================================== Ardalan Khazraei (Bonn): Cost-distance Steiner trees =============================================================== Abstract: In the well-known Steiner Tree Problem, the objective is to connect a set of terminals at the least total cost. We can further constrain the problem by specifying upper bounds for the distance of each terminal to a chosen root terminal. Further, using the Lagrangian relaxation of this restriction, we can penalize large distances in the objective function rather than applying strict distance constraints. We arrive at a special case of the so-called Cost-Distance Steiner Tree Problem in which we have a single weight function on the edges. In this talk, I will present several results from my master's thesis that concern the Cost-Distance Steiner Tree Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem trivially follows from the fact that the regular Steiner Tree Problem is the special case where we set demand weights (Lagrange multipliers) of the terminals to zero. I therefore proceed to prove that the problem remains NP-hard in three restricted cases that do not contain the regular Steiner Tree Problem as a special case anymore. Then I improve on a previous constant-factor approximation for the single-weighted case by using a hybrid method of an approximate Steiner tree with a shortest path tree replacing sections of the tree where path segments are used by many terminals with demand weights summing to higher than a tunable threshold. I also use a similar approach to extend Arora's dynamic programming method for the two-dimensional geometric Steiner Tree Problem to the case with the penalizing terms in the objective function. Location: Room 005 - Ground Floor Freie Universität Berlin Takustr. 9 14195 Berlin