[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 1st 2019

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

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

Lecture: Rekha R. Thomas (University of Washington)

Title: Graph Density Inequalities and Sums of Squares

Abstract:

Many results in extremal graph theory can be formulated as inequalities on
graph densities. While many inequalites are known, many more are
conjectured. A standard tool to establish an inequality is to write the
expression whose nonnegativity needs to be certified as a sum of squares.
This technique has had many successes but also limitations. In this talk I
will describe new restrictions that show that several simple inequalities
cannot be certified by sums of squares. These results extend to the
powerful frameworks of flag algebras by Razborov and graph algebras by
Lovasz and Szegedy. This is joint work with Greg Blekherman, Annie
Raymond, and Mohit Singh.


Coffee & Tea Break:
Room 134

Time: Monday, July 1st - 16:00 h s.t.

Colloquium: Manfred Scheucher (Technische Universität Berlin)

Title: On Arrangements of Pseudocircles

Abstract:

Towards a better understanding of arrangements of circles and also to get
rid of geometric difficulties, we look at the more general setting of
''arrangements of pseudocircles'' which was first introduced by Grünbaum
in the 1970's. An arrangement of pseudocircles is a collection of simple
closed curves on the sphere or in the plane such that any two of the
curves are either disjoint or intersect in exactly two points, where the
two curves cross. In his book, Grünbaum conjectured that every digon-free
arrangement of n pairwise intersecting pseudocircles contains at least
$2n-4$ triangular cells. We present arrangements to disprove this
conjecture and give new bounds on the number of triangular cells for
various classes of arrangements. Furthermore, we study the
''circularizability'' of arrangements: it is clear that every arrangement
of circles is an arrangement of pseudocircles, however, deciding whether
an arrangement of pseudocircles is isomorphic to an arrangement of circles
is computationally hard. Using a computer program, we have enumerated all
combinatorially different arrangements of up to $7$ pseudocircles. For the
class of arrangements of $5$ pseudocircles and for the class of digon-free
intersecting arrangements of $6$ pseudocircles, we give a complete
classification: we either provide a circle representation or a
non-circularizability proof. For these proofs we use incidence theorems
like Miquel's and arguments based on continuous deformation, where circles
of an assumed circle representation grow or shrink in a controlled way.
This talk summarizes results from two articles, which are both joint work
with Stefan Felsner: * Arrangements of Pseudocircles: Triangles and
Drawings; short version in Proc. GD'17; full version available at arXiv
(1708.06449) * Arrangements of Pseudocircles: On Circularizability; short
version in Proc. GD'18; full version in DCG: Ricky Pollack Memorial Issue
(doi:10.1007/s00454-019-00077-y)