Schedule and abstracts 2022/2023
23.08.2023 |
Chaoliang Tang (Fudan Univiersity)
|
Turán number of the linear 3-graph Crown
|
Abstract: Let the crown C13 be the linear 3-graph on 9 vertices {a,b,c,d,e,f,g,h,i} with edges E = {{a,b,c}, {a, d,e}, {b, f, g}, {c, h,i}}. Proving a conjecture of Gyárfás et. al., we show that for any crown-free linear 3-graph G on n vertices, its number of edges satisfy |E(G)| ≤ 3(n - s)/2, where s is the number of vertices in G with degree at least 6. This result, combined with previous work, essentially completes the determination of linear Turán number for linear 3-graphs with at most 4 edges. The result is the joint work with my tutor Hehui Wu and my fellow Zeyu Zheng. It is also simutaneously proved by Shengtong Zhang.
|
19.07.2023 |
Silas Rathke (FU Berlin) |
The asymptotics of R(4,t) |
Abstract: The Ramsey number R(4,t) is the minimum number n of vertices such that each 2-colouring of K_n either contains a red K_4 or a blue K_t. Erdős conjectured that this should essentially grow with the order t^3. For forty years, there has not been any progress on that problem. Until last month, when Mattheus and Verstraete proved this conjecture. In the talk, I will present their proof. It combines a concrete algebraic construction with some probabilistic arguments.
|
11.07.2023
|
Anand Srivastav (Christian-Albrechts-Universität zu Kiel) |
A new Bound for the Maker-Breaker Triangle Game |
Abstract: TBA
|
06.07.2023 |
Patrick Morris (Universitat Politècnica de Catalunya) |
The canonical Ramsey theorem in random graphs: even cycles and list constraints |
Abstract: The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of Kn gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of Kn. We will discuss a theorem that pins down this threshold when we focus on colourings that are constrained by some prefixed lists and also a related result on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle. This represents joint work with José D. Alvarado, Yoshiharu Kohayakawa and Guilherme O. Mota.
|
21.06.2023 |
Olaf Parczyk (FU Berlin) |
Graphs with large minimum degree and no small odd cycles are 3-colourable |
Abstract: Let Ƒ be a fixed family of graphs. The homomorphism threshold of Ƒ is the infimum of those α for which there exists an Ƒ-free graph H=H(Ƒ, α), such that every Ƒ-free graph on n vertices of minimum degree αn is homomorphic to H. Letzter and Snyder showed that the homomorphism threshold of {C3,C5} is 1/5. They also found explicit graphs H({C3,C5}, α), for α > 1/5, which were in addition 3-colourable. Thus, their result also implies that {C3,C5}-free graphs of minimum degree at least (1/5+ ε)n are 3-colourable. For longer cycles, Ebsen and Schacht showed that the homomorphism threshold of {C3,C5,…,C2l-1} is 1/(2l-1). However, their proof does not imply a good bound on the chromatic number of{C3,C5,…,C2l-1}-free graphs of minimum degree n/(2l-1). Answering a question of Letzter and Snyder, we prove that such graphs are 3-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree. This is joint work with Julia Böttcher, Nóra Frankl, Domenico Mergoni Cecchelli, and Jozef Skokan.
|
17.05.2023 |
Dingyuan Liu (FU Berlin) |
On the number of sets with bounded sumset |
Abstract: We will study the counting problem of sets with bounded sumset. More precisely, let m,n be natural numbers, for an n-element subset Y of an arbitrary abelian group, we give upper bounds on the number of sets A ⊆Y with |A+A| ≤ m according to the range of m. Furthermore, we also give an upper bound for the refined version of this problem, improving the previous result of Campos and confirming an earlier conjecture of Alon, Balogh, Morris, and Samotij in a certain range. This is joint work with Leticia Mattos and Tibor Szabó.
|
10.05.2023 |
Ákos Magyar (University of Gerorgia) |
On a conjecture of Graham in geometric Ramsey theory |
Abstract: Let's call a finite point configuration F in a Euclidean space "Ramsey" if any finite coloring of a sufficiently high dimensional Euclidean space contains a monochromatic isometric copy of F. After some initial investigations of Erdos, Graham at al., Graham conjectured that a set F is Ramsey if and only if it is spherical, i.e. if it can be inscribed into a sphere. We outline a new approach and some new results based on some modern tools of additive combinatorics, such as the use of (geometric) uniformity norms and arithmetic regularity lemmas both in the context of Euclidean spaces as well as in the model case of vector spaces over finite fields.
|
04.05.2023 |
Avi Wigderson (IAS, Princeton) |
Approximate Sylvester-Gallai, and applications |
Abstract: Assume you have a finite set of points in real space, with the property that every line through any pair of these points meets a third point. This property is satisfied when all points are colinear, and the (so called) Sylvester-Gallai theorem states that this is the only way! In this talk we explore approximate versions of the assumption, in which the hypothesis holds "on average". I'll motivate this question from applications in coding theory and algebraic complexity. I'll then prove bounds on the dimension of the point set under such relaxed hypothesis. The proof in interesting in that in combines combinatorial, algebraic and analytic arguments, each of them simple to explain. Based on (old) joint works with Barak, Dvir, Saraf and Yehudayoff. The talk is self contained - no special background is assumed.
|
03.05.2023 |
Adam Schweitzer (TU Berlin) |
The Chow ring of matroids and the Rota-Welsh conjecture - Part II |
Abstract: Recently methods in combinatorial Hodge theory have been used successfully to settle long standing conjectures about certain characteristic sequences of matroids. This talk will introduce some of the central concepts and theorems of this theory for the case of matroids, without delving into the underlying algebraic geometry, and use it to give parts of June Huh's proof of the Rota-Welsh conjecture.
|
27.04.2023 |
Adam Schweitzer (TU Berlin) |
The Chow ring of matroids and the Rota-Welsh conjecture - Part I |
Abstract: Recently methods in combinatorial Hodge theory have been used successfully to settle long standing conjectures about certain characteristic sequences of matroids. This talk will introduce some of the central concepts and theorems of this theory for the case of matroids, without delving into the underlying algebraic geometry, and use it to give parts of June Huh's proof of the Rota-Welsh conjecture.
|
15.03.2023 |
Gregory Sorkin (London School of Economics and Political Science) |
Extremal Cuts and Isoperimetry in Random Cubic Graphs |
Abstract: The minimum bisection width of random cubic (3-regular) graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics. An additional reason is that the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal. It is known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. (The Hamilton cycle approach had also decreased the upper bound on maximum cut, but this has since been improved upon by making rigorous a 2010 conjecture from statistical physics.)
|
01.03.2023 |
Stefanie Gerke (Royal Holloway, University of London) |
The k-th shortest s-t path in a weighted complete graph |
Abstract: Suppose we weight the edges of the complete graph Kn with independent exponential Exp(1) random weights, pick two distinct vertices s and t,and then successively construct and then remove the edges of minimal weight s-t paths. We describe asymptotically the distributions of the weights of the first k paths obtained in this process. In particular we show that the mean weight of the k-th path is
(log n + γ + 2ζ(3) + 2ζ(5) + ... + 2ζ(2k − 1) + o(1))/n
as n → when k is a constant, and where γ is the Euler--Mascheroni constant and ζ is the Riemann zeta function.
This is joint work with P. Balister.
|
08.02.2023 |
Silas Rathke (FU Berlin) |
Pseudorandom Ramsey graphs |
Abstract: In recent years, the theory of pseudorandom graphs have received considerable attention in combinatorial research. One question raised was, how pseudorandom Ks-free graphs can be. A note by Mubayi and Verstraëte published in 2019 describes a link between pseudorandom graphs and Ramsey numbers: They show that if pseudorandom Ks-free graphs exist, then the Ramsey number r(s,t) can be bounded from below. In this talk, we will look at this note. We will try to understand the link in detail. Could pseudorandom graphs really be the "the central tool required to determine classical graph Ramsey numbers" as the authors suggest?
|
25.01.2023 |
Yamaan Attwa (FU Berlin) |
Towards the Erdős-Hajnal conjecture for P5 |
Abstract: The Erdős-Hajnal Conjecture is one of the most well-known problems in extremal combinatorics. It states that in contrast to the general n-vertex graph, if one forbids any fixed graph H as an induced subgraph, instead of a tight guarantee of a logarithmic-size homogeneous set, one can guarantee a homogeneous set of polynomial size. While the conjecture is far from being fully resolved, it is known to be true for some forbidden subgraphs of small order. The smallest forbidden subgraph for which the conjecture remains open is the path on five vertices. In this talk I intend to review a recent paper by Blanco and Bucić guaranteeing a homogeneous set of size 2Ω(log(n)^2/3) in P5-free graphs. This result is an improvement to the 2Ω(log(n)^1/2) size of a homogeneous set guaranteed by a result of Erdős and Hajnal for any forbidden subgraph.
|
19.01.2023 |
Alberto Espuny Díaz (TU Ilmenau) |
Threshold for (some) spanning trees in random geometric graphs |
Abstract: Consider the following model of random graphs: a total of n vertices are assigned to uniformly random positions on the unit square, independently of each other, and any two vertices are then joined by an edge if the distance between their positions is less than a given parameter r. This is called the random geometric graph G(n,r) and, similarly to the binomial random graph G(n,p), increasing properties exhibit thresholds (with respect to the parameter r) which we wish to understand. The behaviour of random geometric graphs, however, is very different from the behaviour of G(n,p).
In this talk, I will highlight some of these differences and eventually focus on the case of balanced s-ary trees, for which we have established the threshold. This is based on joint work with Lyuben Lichev, Dieter Mitsche and Alexandra Wesolek.
|
19.01.2023 |
Tibor Szabó (FU Berlin) |
Results, problems, and a couple of proofs from Oberwolfach |
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
Notes:
For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de
Archives
Schedule and abstracts 2022/2023
Schedule and abstracts 2021/2022
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