Seminar coordinates:
This is a Discrete Mathematics Seminar with weekly talks followed by discussion and lunch. The sessions are informal, talks last about 30 minutes and treat discrete topics the speakers like or have been working on. Everybody is welcome to participate. If you would like to give a talk, let us know.Time: Wednesdays, 12.15-13.00
Questions: email to knauer [at] math.tu-berlin.de
Room: MA-645
Next Talks:
Speaker: Bartosz Walczak
Title: "Parity in graph sharing games"
Date: February 10
February 3, 2010: Tom Trotter, "On the Size of Maximal Antichains and the Number of Pairwise Disjoint Maximal Chains"
January 27, 2010: Torsten Ueckerdt, "One way to generalize interval graphs: edge-intersection graphs of elbows in the plane grid"
January 20, 2010: Kolja Knauer, "Generalizing the order polytope"
January 13, 2010: Daniel Heldt, "Walking on a path (with loops)"
January 6, 2010: Cornelia Dangelmayr, "Neues zum Satz von Hanani und Tutte"
December 18, 2009: Andrea Hoffkamp, "Funktionales Denken im propädeutischen Analysisunterricht - Ansätze und empirische Befunde zu einem qualitativen Zugang durch Computereinsatz II"
December 16, 2009: Andrea Hoffkamp, "Funktionales Denken im propädeutischen Analysisunterricht - Ansätze und empirische Befunde zu einem qualitativen Zugang durch Computereinsatz I"
December 9, 2009: Stefan Felsner, "Lower bounds for on-line chain partitioning"
December 2, 2009: Bartek Bosek and Tomasz Krawczyk, "A subexponential upper bound for the on-line chain partitioning problem"
November 25, 2009: Stefan Felsner, "Coding and Counting Arrangements of Pseudolines"
November 18, 2009: Torsten Ueckerdt, "The Balloon Popping Problem"
November 11, 2009: Stefan Felsner, "Planar Bipartite Posets"
November 4, 2009: Daniel Heldt, "Sensitivity of 3-heights on a path"
Ocotober 21, 2009: Till Miltzow, "Points with Some Quadrant Depth"
Ocotober 14, 2009: Kolja Knauer, "Polynomial Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids"
Ocotober 7, 2009: Torsten Ueckerdt, "Enumerating all Ideals of a Poset"
September 30, 2009: Stefan Felsner, "Squarings of Quadrangulations"
September 16, 2009: Vincent Pilaud, "A failed construction of the multiassociahedron"
September 2, 2009: Mareike Massow, "Swap Colors in Linear Extension Graphs"
August 5, 2009: Daniel Heldt, "Layer decomposition of planar graphs"
July 22, 2009: Balchandra Thatte, "Reconstruction of Pedigrees"
July 15, 2009: Julia Pap, "Kernels and Sperner's Lemma"
July 8, 2009: Daniel Heldt, "Computational aspects of mixing heights"
June 31, 2009: Matjaz Kovse, "Topological representations of planar partial cubes"
June 24, 2009: Kolja Knauer, "Antimatroids, Polytopes and ULDs"
June 17, 2009: Torsten Ueckerdt, "(Linear) Induced Forests in Planar Graphs"
June 10, 2009: Stefan Felsner, "Condorcet Domains and Arrangements of Pseudolines"
June 3, 2009: Pavel Valtr, "On Triconnected and Cubic Plane Graphs on Given Point Sets"
May 27, 2009: Stefan Felsner, "Rectangular layouts: associated graphs and constructions."
May 13, 2009: Florent Becker, "Curry-Hähnchen zu Mittag (An Introduction to Curry-Howard and the Coq Proof-Assistant)"
May 6, 2009: Tobias Friedel, "Root Systems and Generalized Associahedra"
April 29, 2009: Sarah Li, "Adjacency Posets"
April 22, 2009: Mareike Massow, "Convex Partitions of the Permutahedron"
April 15, 2009: Jan Foniok, "Constraint Satisfaction and Category Theory: Constructing Tractable Templates"
March 25, 2009: Daniel Heldt, "A Short Introduction to Block Cipher Algorithms"
March 18, 2009: Anton Dochtermann, "Graph Homomorphisms and Reflection Positivity"
March 11, 2009: Torsten Ueckerdt, "On Quadrant-Depth - Closing the Gap"
March 4, 2009: Melanie Win Myint, "Compactness proofs for infinite graphs"
February 25, 2009: Stefan Felsner, "On Quadrant-Depth"
February 18, 2009: Kolja Knauer, "Generalized Chip Firing"
February 11, 2009: Mareike Massow, "Linear Extension Diameter of Boolean Lattices"
January 28, 2009: Stefan Felsner, "Sorting Pairs in Bins, aka 'Das Krawattenraetsel'"
January 21, 2009: Torsten Ueckerdt, "On the number of non-decreasing paths in grid graphs"
January 14, 2009: Mihyun Kang, "Yet Another Way of Counting Planar Graphs"
January 7, 2009: Paul Bonsma, "Avaloqix is strongly PSPACE-hard"
December 17, 2008: Florent Becker, "Self-Assembling Tilings, Orders and Signal Systems"
December 10, 2008: Britta Peis, "Covering Graphs by Colored Stable Sets"
December 3, 2008: Bruno Benedetti, "Bipartite Graphs and Basic k-Covers"
November 26, 2008: Daniel Heldt, "A Reason Why Avaloqix Could Be 'Interesting' (i.e. NP-hard)"
November 19, 2008: Melanie Win Myint, "An Algebraic Characterization of Planar Graphs"
November 12, 2008: Mareike Massow, "The Boolean Lattice and its Linear Extension Diameter"
November 5, 2008: Sarah Li, "Characterization of Maps with Order Dimension at most 2"
October 29, 2008: Stefan Felsner, "Partitioning Boolean Lattices into Intervals"
October 22, 2008: Hal Kierstead, "Efficient packing via game coloring"
October 15, 2008: Torsten Ueckerdt, "How to Eat 4/9 of a Pizza"
October 8, 2008: Daniel Heldt, Jannik Matuschke and Madeleine Theile, "Avaloqix - A Max Flow Game"
September 10, 2008: Bartlomiej Bosek and Kamil Kloch, "Online Dimension of Semi-Orders with Representation"
September 3, 2008: Kamil Kloch and Piotr Micek, "Some Open Problems We Like"
July 30, 2008: Uwe Schauz, "Tutte's Flow Conjectures and Berlekamp's Switching Game"
July 16, 2008: Bernd Sturmfels, "Evolution on distributive lattices"
July 9, 2008: Torsten Ueckerdt, "Distributive polyhedra and related problems on weighted parameterized graphs"
July 2, 2008: Melanie Win Myint, "Cycles and Bicycles in Locally Finite Graphs II"
June 25, 2008: Felix Fischer, "Voting Caterpillars"
June 18, 2008: Melanie Win Myint, "Cycles and Bicycles in Locally Finite Graphs I"
June 11, 2008: Peter Allen, "A connection between Ramsey number and chromatic number"
June 4, 2008: Mareike Massow, "LINEAR EXTENSION DIAMETER is NP-complete"
May 28, 2008: Sarah Li, "Random Walks and Search Problems"
May 21, 2008: Ludmila Scharf, "Inducing Polygons of Line Arrangements"
May 14, 2008: Mareike Massow, "Linear Extensions in Diametral Pairs Don't Have to Be Reversing"
April 30, 2008: Paul Bonsma, "A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs"
April 23, 2008: Uwe Schauz, "Mr. Paint and Mrs. Sandpaper"
April 16, 2008: Axel Werner, "Linkages in Polytope Graphs"
April 9, 2008: Bernd Sturmfels, "Permutohedra, Semigraphoids, and Mice"
March 19, 2008: Stefan Felsner, "Hamiltonicity Properties of Arrangement Graphs"
March 12, 2008: Kolja Knauer, "On Frankl's Conjecture"
March 5, 2008: Cornelia Dangelmayr, "k-Segments in Arrangements of Pseudolines"
February 27, 2008: Patrick Baier, "Distributed Computation of Virtual Coordinates"
February 20, 2008: Stefan Felsner, "Markov Chains and the Second Eigenvalue"
February 13, 2008: Moritz Schmitt, "The Spectrum of a Graph"
February 6, 2008: Anton Dochtermann, "Foldings and the Topology of Graph Homomorphisms"
January 30, 2008: Mareike Massow, "Reconstructing Posets from Linear Extension Graphs"
January 23, 2008: Kolja Knauer, "A Distributive Lattice on Pseudo-Flows"
January 16, 2008: Gesine Koch, "Counting Paths in Cube Configurations"
January 9, 2008: Paul Bonsma, "A Polynomial Time Algorithm for Finding Fullerene Patches"
December 21st '07: Graham Brightwell, "Polyhedral Methods for Linear Extensions of Partial Orders"
December 12th '07: Sarah Li, "The Dictator Paradox"
December 5th '07: Stefan Felsner, "Sorting Using Networks of Stacks and Queues"
November 28th '07: Florian Zickfeld, "Leafy Trees in Planar Graphs"
November 21st '07: Nina Siebold, "How to Draw an Order"
November 14th '07: Leonid Ioffe, "Dimension Of Orders via Constraint Programming"
November 7th '07: Patrick Baier, "Greedy Drawings of Planar Triangulations"
October 31st '07: Cornelia Dangelmayr, "k-Level Complexity of Arrangements of (Pseudo-)Segments"
October 24th '07: Kolja Knauer, "Construction of Steiner Triple Systems"
October 17th '07: Martin Pergel, "Recognition and Optimization Problems on Geometric Intersection Graphs"
October 10th '07: Balazs Keszegh, "Weak Conflict-Free Colorings of Point Sets and Simple Regions"
September 28th '07: Florian Pfender, "Turan's Theorem for Multipartite Graphs"
September 19th '07: Stefan Felsner, "Compact Drawings with Bends"
September 5th '07: Mareike Massow, "Partitioning Posets"
August 29th '07: Stefan Felsner, "Matchings and Edge Colorings in Regular Graphs"
August 8th '07: Carolyn Chun, "Unavoidable Minors of c-connected Graphs"
August 1st '07: Bertrand Marc, "2-Arrangements of Pseudolines"
July 25th '07: Florian Zickfeld, "Leafy Trees"
July 18th '07: Eric Fusy, "A bijection between loopless maps and triangulations"
July 11th '07: Patrick Baier, "Digital Geometry"
July 4th '07: Stefan Felsner, "Infeasibility of Arrangements"
June 27th '07: Kamil Kloch, Tomasz Krawczyk and Piotr Micek "On-line Dimension of Intervals"
June 20th '07: Kamil Kloch, "On-line Colouring of Intervals"
June 13th '07: Olivier Bernardi, "Bijective Countings of Tree-Rooted Maps"
June 6th '07: Cornelia Dangelmayr, "Planar Graphs are in 1-STRING"
May 23rd '07: Stefan Felsner, "On-line chain partitions of up-growing 2-dimensional orders"
May 16th '07: Felix Breuer, "Perlenketten mit Quoten"
May 9th '07: Mareike Massow, "Diametral Pairs of Linear Extensions of a Poset"
May 2nd '07: Florian Zickfeld, "Hardness of Counting Orientations with Fixed Out-Degrees"
April 25th '07: Sarah Kappes, "Was ist ein semidefinites Programm?"
April 18th '07: Patrick Baier, "Compass Routing"
April 11th '07: Cornelia Dangelmayr, "Pseudo-Connections in the Plane"
April 4th '07: Stefan Felsner, "Triangle Contact Representations of Graphs"
March 21st '07: Andreas Hoffmeister, "Random sampling in distributive lattices"
March 7th '07: Stefan Felsner, "Online Ramsey Theory"
January 31st '07: Mareike Massow, "2-Dimensional Partial Orders Revisited"
January 24th '07: Florian Zickfeld, "Counting Planar Eulerian Orientations is #P-complete" (Recent result by Pa�d� Creed)
January 17th '07: Cornelia Dangelmayr, "How Many 3-Pseudosegments can a Pseudoline Arrangements have?"
January 10th '07: Patrick Baier, "The Crossing Number of Geometric Complete Graphs"
December 20th '06: Stefan Felsner, "Arrangements of pseudolines; news, problems, and goodies."
December 13th '06: Kolja Knauer, "α-Orientations and Regular Oriented Matroids"
December 6th '06: Kolja Knauer, "α-Orientations and FlipFlops"
November 29th '06: Sarah Kappes, "Kombinatorik orthogonaler Flächen"
November 22nd '06: Florian Zickfeld, "α-Orientations and Bipartite Perfect Matchings"
November 15th '06: Leonid Ioffe, "Constraint Programming"
November 1st '06: Martin Pergel, "On Complicacy of Graphs Representable by Polygons"
October 25th '06: Dominik Piesker, "Spezialfälle der 'list edge coloring conjecture'"
October 18th '06: Stefan Felsner, "Baxter and Schröder Families"
August 23rd '06: Patrick Baier, "Adaptive colouring of upgrowing posets"
July 19th '06: Cornelia Dangelmayr, "Dominating pairs in AT-free graphs"
July 5th '06: Stefan Felsner, "Counting Bipolar Orientations on the Grid"
June 28th '06: Sarah Kappes, "Convex-Pseudo Decompositions"
June 20th '06: Maria del Pilar Sabariego Arenas, "3-Loop Networks with many Minimum Distance Diagrams"
June 14th '06:Eric Fusy, "Enumeration of Bipolar Orientations"
June 7th '06: Johan Nilsson, "The Gupta-Newman-Rabinovich-Sinclair Conjecture"
May 31st '06: Florian Zickfeld, "Integer Realizations of 3-Polytopes"
May 24th '06: Stefan Felsner, "Proofs of Untileability"
May 17th '06: Cornelia Dangelmayr, "Cocomparability graphs of posets with (interval) dimension at most two"
May 10th '06: Patrick Baier, "Online Chain Partitioning of Upgrowing Interval Posets - The Upper Bound"
May 3rd '06: Mareike Massow, "Semi Bar 1-Visibility Graphs"
April 26th '06: Harald Schülzke, "The Normal Graph Conjecture for line graphs"
April 19th '06: Steffen Melang, "Bipolar Orientations"
April 5th '06: Maria del Pilar Sabariego Arenas, "Circulant Graphs and Binomial Ideals"
March15th '06: Florian Zickfeld, "On the Number of 3-Orientations of a Triangulation"
March 8th '06: Sarah Kappes, "A binary labeling for the angles of a plane quadrangulation"
March 1st '06: Johan Nilsson, "Reachability substitutes"
February 22nd '06: Stefan Felsner, "Two Algorithms for Bipartite Cardinality Matching"
February 8th '06: Mareike Massow, "Bar 1-Visibility Graphs - Introduction and First Results"
February 1st '06: Stefan Felsner, "Counting Linear Extensions"
January 25th '06: Georg Melamed, "Skelette 3-dimensionaler Ordnungen"
January 18th '06: Cornelia Dangelmayr, "A Representation of the Subset "VPT" of Chordal Graphs as Intersection Graphs of Pseudosegments"
January 11th '06: Patrick Baier, "The Upper Bound for Online Chain Covering of Upgrowing Interval Posets"
December 14th '05: Florian Zickfeld, "Schnyder Woods and Pairs of Non-Crossing Dyck Paths"
December 7th '05: Stefan Felsner, "Box Graphs and Graph Dimension"
November 23rd '05: Viktor Blåsjö, "On the Braid Page of Gauss' Handbook 7"
November 23rd '05: Sarah Kappes, "Realizers for d-polytopes with d+2 vertices"
November 16th '05: Cornelia Dangelmayr, "Relations within the class of intersection graphs"
November 9th '05: Patrick Baier, "A special case of online chain covering of posets"
November 2nd '05: Stefan Felsner, "Dualization in Products of Chains"
October 26th '05: Florian Pfender, "Visibility Graphs on Point Sets"
October 5th '05: Mareike Massow, "What makes the treewidth large?"
September 21st '05: Viktor Blåsjö, "Enumeration of Reduced Words in Combinatorial Group Theory "
September 14th '05: Krisztián Tichler, "Lies and Hypercubes "
August 31st '05: Florian Zickfeld, "A Schnyder Wood with no rigid AND coplanar embedding"
August 24th '05: Sarah Kappes, "Orthogonal Surfaces - A combinatorial definition for characteristic points"
August 17th '05: Eric Fusy, "Enumeration of d-polytopes with d+3 vertices"
August 10th '05: Stefan Felsner, "Poset Polytopes and Linear Extensions"
July 13th '05: Cornelia Dangelmayr, "Intersection Graphs"
July 6th '05: Patrick Baier, "An upper bound for online chain covering"
June 29th '05: Florian Pfender, "Closure and Hamiltonian Properties in Claw-free Graphs"
June 22nd '05: Kamil Kloch, "Partial Orders - fooling Alice"
June 15th '05: Sarah Kappes, "What is an orthogonal complex?"
June 8th '05: Krisztián Tichler, "A Combinatorial Property of Databases"
May 25th '05: Dan Kral, "Claws and Paws"