Springe direkt zu Inhalt

Research Seminar Combinatorics

Next Talk

Thursday, December 8th, 2022 at 16:15
A6 SR025/026
Leticia Mattos (FU Berlin)
Bounds For Essential Covers Of The Cube

Abstract: An essential cover of the vertices of the n-cube {-1,1}n by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with n/2+1 hyperplanes and showed that √n hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the n-cube contains at least n0.52 hyperplanes. In this talk, we show that n5/9 hyperplanes are needed. This is based on a joint work with Araujo and Balogh.

<iframe src="https://calendar.google.com/calendar/embed?mode=agenda&height=600&wkst=1&bgcolor=%23FFFFFF&src=dq5vbd4jmriuttn2k4c12s228c%40group.calendar.google.com&color=%23711616&ctz=Europe%2FBerlin" style="border-width:0" width="800" height="350" frameborder="0" scrolling="no"></iframe>

Google Calendar

Schedule and abstracts 2022/2023

DateSpeakerTitle
08.12.2022 Leticia Mattos
(FU Berlin)
Bounds For Essential Covers Of The Cube
24.11.2022 Aldo Kiem
(ZIB)
Flag Algebras for Edge-Colored Graphs
16.11.2022 Olaf Parczyk
(FU Berlin)
A general approach to transversal versions of Dirac-type theorems
09.11.2022 Giulia Codenotti
(FU Berlin)
Flatness constants and lattice-reduced convex bodies
02.11.2022 David Fabian
(FU Berlin)
Graph bootstrap percolation of random graphs
19.10.2022 Michaela Borzechowski
(FU Berlin)
A Universal Construction for Unique Sink Orientations
08.12.2022
Leticia Mattos (FU Berlin)
Bounds For Essential Covers Of The Cube

Abstract: An essential cover of the vertices of the n-cube {-1,1}n by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with n/2+1 hyperplanes and showed that √n hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the n-cube contains at least n0.52 hyperplanes. In this talk, we show that n5/9 hyperplanes are needed. This is based on a joint work with Araujo and Balogh.

24.11.2022
Aldo Kiem (ZIB)
Flag Algebras for Edge-Colored Graphs

Abstract: Flag Algebras is a highly successive formalism to study problems in extremal combinatorics. It has achieved the best known bounds for Turán’s (3,4)-problem as well as tight bounds for the three color Ramsey multiplicity of the triangle, Erdös’s Pentagon conjecture and a conjecture of Erdös and Sós on the asymptotic frequency of Rainbow triangles. What is special about Flag Algebras is that a significant amount of work in finding a Flag Algebra proof certificate can be automated by relaxing the given problem to a semidefinite program (SDP).

In this talk, we will formally define Flag Algebras with many examples from the theory of c-edge-colored complete graphs. We will then see how to set up a Flag Algebra SDP and will discuss methods, old and new, to reduce the size of the SDP as well as splitting it up into smaller blocks. Finally, we will present our newest calculation for the four color Ramsey multiplicity of the triangle.

This is joint work with Prof. Pokutta (TU Berlin and ZIB) and Dr. Christoph Spiegel (ZIB).

16.11.2022
Olaf Parczyk (FU Berlin)
A general approach to transversal versions of Dirac-type theorems

Abstract: Given a collection of m hypergraphs on the same vertex set, an m-edge graph F is a transversal if there is each edge comes from a different graph of the collection. How large does the minimum degree of each graph in the collection need to be so that it necessarily contains a copy of F that is a transversal? Each graph in the collection could be the same hypergraph, hence the minimum degree of each of them needs to be large enough to ensure that it individually contains F. In this talk, we discuss a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles.

This is joint work with Pranshu Gupta, Fabian Hamann, Alp Müyesser, and Amedeo Sgueglia.

09.11.2022
Giulia Codenotti (FU Berlin)
Flatness constants and lattice-reduced convex bodies

Abstract: The lattice width of a convex body measures how "thin" the body is in lattice directions. The so-called flatness theorem states that in each fixed dimension there is an upper bound for the lattice width of a special class of convex bodies, those which are hollow. In this talk we introduce these definitions and certain generalizations thereof and look at the few known extremal hollow convex bodies achieving maximum lattice width. This leads us to a conjecture about extremal convex bodies, namely that they are lattice-reduced. This class of convex bodies has not been previously studied, and we present (many) questions and (some) answers about such lattice-reduced convex bodies. 

02.11.2022
David Fabian (FU Berlin)
Graph bootstrap percolation of random graphs

Abstract: Given graphs H and G the H-bootstrap process on G is the process that starts with G and in which at each step every edge that is the only missing edge in a copy of H is added. Any such process stabilises after a finite number of steps. The maximum running time MH(n) is the largest number of steps of an H-bootstrap process when H is fixed and G ranges over all graphs on n vertices. In this talk we investigate MH(n) when H is distributed as the random graph G(k,p). We will show that for p = ω(log(k)/k) the maximum running time is bounded from below by ckn² for some ck>0.

This is joint work with Patrick Morris and Tibor Szabó.

19.10.2022
Michaela Borzechowski (FU Berlin)
A Universal Construction for Unique Sink Orientations

Abstract: A Unique Sink Orientation (USO) is an orientation of the hypercube graph, such that the induced subgraph of every non-empty subcube contains exactly one sink. USOs can be used to capture the combinatorial structure of many essential algebraic and geometric problems. Unfortunately, there is no known algorithm that verifies if a given orientation is actually USO and which runs in polynomial time in the dimension of the cube. Out of the many possible orientations for a given cube only few of them are USO. But still, for a cube of a fixed dimension, the number of USOs is exponential in the dimension. To generate bounds on the total number of USOs, construction techniques are needed. They are also useful to find counterexamples to suspected properties of USOs. Furthermore, families of ''bad'' USOs provide examples to show lower bounds for the worst-case runtime of algorithms. While there are some construction methods for USOs, until now they have not been able to generate all possible USOs.

In this talk we present a new construction framework which can be applied to all USOs and with which we can generate every n-dimensional USO using only USOs of dimension n-1 or lower. Our universal construction was inspired by techniques from cube tilings of space.

This is joint work with Joseph Doolittle (TU Graz) and Simon Weber (ETH Zürich)

Links

Mailing list:

To subscribe to the mailing-list of the seminar, please follow this link:
https://lists.fu-berlin.de/listinfo/combinatorics-seminar

Seminar calendar:

To add the .ics file of the calendar to your favorite calendar reader (that supports the ICal format), please follow this link:
ICal calendar.

To add the calendar feeds to your favorite feed reader, please follow this link:
Calendar feeds.

Notes:

For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de

Archives

Schedule and abstracts 2020/2021

Schedule and abstracts 2019/2020

Schedule and abstracts 2018/2019

Schedule and abstracts 2017/2018

Schedule and abstracts 2016/2017

Schedule and abstracts 2015/2016

Schedule and abstracts 2014/2015

Schedule and abstracts 2013/2014

Schedule and abstracts 2012/2013

Schedule and abstracts 2011/2012

Schedule and abstracts 2010/2011

Schedule and abstracts 2009/2010