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--