[Mittagsseminar TI] Mittagsseminar am Dienstag, 22. 10. und Donnerstag, 24. 10.

[Günter Rote <rote@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 22. Oktober 2019, 12:00 Uhr, SR 055, Takustraße 9
    Manfred Scheucher (TU Berlin)
    zum Thema: Using SAT Solvers in Combinatorics and Geometry
    (see below for the abstract)

und am

    Donnerstag, 24. Oktober 2019, 12:00 Uhr, SR 055, Takustraße 9
    Günter Rote
    zum Thema: Counting Pseudoline Arrangements

=========================================
Zusammenfassung des Vortrags am Dienstag:
We discuss how modern SAT solvers such as Minisat or Glucose can be used 
to tackle mathematical problems. We present some of our recent results 
on various problems to give the audience a better understanding, which 
problems might be tackled in this fashion, and which problems might not.

Besides the naive SAT formulation also further ideas might be required 
to tackle certain problems - additional constraints (such as statements 
which hold "without loss of generality") might need to be added to the 
SAT model so that it becomes solvable in reasonable time. In particular, 
to tackle universal point sets for planar graphs, we present a 
sophisticated approach which combines the following four powerful tools:
complete enumeration of order types, complete enumeration of (planar) 
graphs, SAT solvers, and IP solvers.

Literature
* K. Däubel, S. Jäger, T. Mütze, and M. Scheucher. On orthogonal 
symmetric chain decompositions. In Proc. EUROCOMB 2019. Full version to 
appear in the Electronic Journal of Combinatorics (EJC). [arXiv:1810.09847]
* T. Mütze and M. Scheucher. On L-shaped Point Set Embeddings of Trees: 
First Non-embeddable Examples. In Proc. Graph Drawing 2018. 
[arXiv:1807.11043]
* M. Scheucher. On Disjoint Holes in Point Sets. In Proc. EUROCOMB 2019. 
[arXiv:1807.10848]
* M. Scheucher, H. Schrezenmaier, and R. Steiner. A Note On Universal 
Point Sets for Planar Graphs. In Proc. Graph Drawing 2019. 
[arXiv:1811.06482]