Springe direkt zu Inhalt

2021/2022

Talks normally take place Wednesdays or Thursdays.

DateSpeakerTitle
05.05.2022 Anita Liebenau
(UNSW)
Uncommon and Sidorenko systems of equations
04.05.2022 Patrick Morris
(UPC)
Schur properties of randomly perturbed sets
21.04.2022 Guilherme Oliveira Mota
(USP)
Constrained colourings of random graphs
13.04.2022 András Imolay
(Eötvös Loránd University)
Multicolor Turán Numbers
13.04.2022 Dávid Matolcsi
(Eötvös Loránd University)
Avoiding right angles and certain Hamming distances
17.02.2022 Simona Boyadzhiyska
(FU Berlin)
Fixed-point cycles and envy-free division
09.02.2022 Benjamin Aram Berendsohn
(FU Berlin)
The Diameter of Graph Associahedra
02.02.2022 Samuel Mohr
(Masaryk University)
Uniform Turán density
26.01.2022 Kalina Petrova
(ETHZ)
Resilience of Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
20.01.2022 Tibor Szabó
(FU Berlin)
Improved Integrality Gap in Restricted Max-Min Allocation
12.01.2022 Amedeo Sgueglia
(LSE)
Multi-round Maker-Breaker Games
05.01.2022 Felix Clemen
(UIUC)
Max cuts in triangle-free graphs
16.12.2021 Olaf Parczyk
(FU Berlin)
Density of triangles and independent sets of size three
08.12.2021 Alberto Espuny Díaz
(TU Ilmenau)
Path decompositions of random directed graphs
01.12.2021 Simón Piga
(Universität Hamburg)
Codegree threshold for cycle decompositions in 3-uniform hypergraphs
24.11.2021 Pedro Araújo
(Czech Academy of Sciences)
Tight Hamilton cycles in uniformly dense hypergraphs
18.11.2021 Leticia Mattos
(FU Berlin)
Hitting all maximum independent sets
10.11.2021 Michael Anastos
(FU Berlin)
Determining the Hamiltonicity of sparse graphs in polynomial expected time
21.10.2021 Leticia Mattos
(FU Berlin)
Clique packings in random graphs
05.05.2022
Anita Liebenau (UNSW)
Uncommon and Sidorenko systems of equations

Abstract: A system of linear equations L over the finite field Fq is common if the number of solutions to L in any two-colouring of Fqn is asymptotically (as n→∞) at least the expected number of monochromatic solutions in a random colouring of Fqn. For example, a Schur triple x+y=z was shown to be common by Cameron, Cilleruelo and Serra in 2007. Another heavily studied specific example is that of an arithmetic progression of length four (4-AP), which can be described by two equations of the form x - 2y + z = 0 and y - 2z + w = 0. Wolf showed that these are uncommon (over Zand over F5).

Motivated by these existing results on specific systems, as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Building on earlier work of Cameron, Cilleruelo and Serra, common linear equations have been fully characterised by Fox, Pham and Zhao.

In this talk, we discuss recent progress towards characterising common systems of two or more equations. In particular, we prove that any system containing a 4-AP is uncommon, confirming a conjecture of Saad and Wolf. We also discuss the related concept of Sidorenko systems of equations.

Joint work with Nina Kamčev and Natasha Morrison.

04.05.2022
Patrick Morris (UPC)
Schur properties of randomly perturbed sets

Abstract: A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We discuss the following problem: how many random integers from [n] need to be added to some A ⊆ [n] to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when |A| > ⌈4n/5⌉, no random integers are needed, as A is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers A ⊆ [n], adding ω(n1/3) random integers suffices, noting that this is optimal for sets A with |A| ≤ ⌈n/2⌉.

We close the gap between these two results by showing that if A ⊆ [n] with |A| = ⌈n/2⌉+t <⌈4n/5⌉, then adding ω(min{n1/3,nt-1}) random integers will with high probability result in a set that is Schur. Our result is optimal for all t, and we further initiate the study of perturbing sparse sets of integers A by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.

Joint work with Shagnik Das and Charlotte Knierim.

21.04.2022
Guilherme Oliveira Mota (USP)
Constrained colourings of random graphs

Abstract: Given graphs G, H1 and H2, let G --> (H1,H2) denote the property that in every edge-colouring of G there is a monochromatic copy of H1 or a rainbow copy of H2. The constrained Ramsey number, defined as the minimum n such that Kn --> (H1,H2), exists if and only if H1 is a star or H2 is a forest.

We determine the threshold for the property G(n,p) --> (H1,H2) when H2 is a forest.

This is a joint work with Maurício Collares, Yoshiharu Kohayakawa and Carlos Gustavo Moreira.

13.04.2022
András Imolay (Eötvös Loránd University)
Multicolor Turán Numbers

Abstract: We consider a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem by studying the maximum number exF(n,G) of edge-disjoint copies of a fixed graph F can be placed on an n-vertex ground set without forming a subgraph G whose edges are from different F-copies. We determine the pairs {F,G} for which the order of magnitude of exF(n,G) is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.

13.04.2022
Dávid Matolcsi (Eötvös Loránd University)
Avoiding right angles and certain Hamming distances

Abstract: In this paper we show that the largest possible size of a subset of Fqn avoiding right angles, that is, distinct vectors x,y,z such that x−z and y−z are perpendicular to each other is at most O(nq−2). This improves on the previously best known bound due to Naslund and refutes a conjecture of Ge and Shangguan. A lower bound of nq/3 is also presented.

It is also shown that a subset of Fqn avoiding triangles with all right angles can have size at most O(n2q−2). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset A ⊂ Fqn for which x−y is not self-orthogonal for any distinct x,y ∊ A. The exact answer is determined for q=3 and n ≡ 2 (mod 3).
Our methods can also be used to bound the maximum possible size of a binary code where no two codewords have Hamming distance divisible by a fixed prime q. Our lower- and upper bounds are asymptotically tight and both are sharp in infinitely many cases.

17.02.2022
Simona Boyadzhiyska (FU Berlin)
Fixed-point cycles and envy-free division

Abstract: Given an edge-labeling of the complete bidirected graph K⃡n with functions from [d] to itself, we call a cycle in K⃡n a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point; the labeling is fixed-point-free if no fixed-point cycle exists. In this talk we will consider the following question: for a given d, what is the largest value of n for which there exists a fixed-point-free edge-labeling of K⃡n with functions from [d] to itself? This problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra and has close connections to fair allocation in social choice theory. We will also discuss the special case where the edges are labeled with permutations of [d], which is related to a problem recently studied by Alon and Krivelevich and by Mészáros and Steiner.

This is joint work with Benjamin Aram Berendsohn and László Kozma.

09.02.2022
Benjamin Aram Berendsohn (FU Berlin)
The Diameter of Graph Associahedra

Abstract: Graph Associahedra are a family of polytopes that generalize several well-known polytopes such as Associahedra, Permutohedra, and Cyclohedra. The skeleton of a Graph Associahedron corresponds to the rotation graph of the elimination trees on a fixed graph.

In this talk, we study the diameter of Graph Associahedra, or, in other words, the maximum rotation distance between two elimination trees on a fixed graph G. We survey several known results and then focus on the case where G is a caterpillar tree, calculating the diameter of each Caterpillar Associahedron up to a constant factor.

02.02.2022
Samuel Mohr (Masaryk University)
Uniform Turán density

Abstract: In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K4(3)- and K4(3). The former question was solved only recently in [Israel J. Math. 211 (2016), 349--366] and [J. Eur. Math. Soc. 97 (2018), 77--97], while the latter still remains open for almost 40 years. In addition to K4(3)- , the only 3-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht~[J. London Math. Soc. 97 (2018), 77--97] and a specific family with uniform Turán density equal to 1/27.

In this talk, we give an introduction to the concept of uniform Turán densities, present a way to obtain lower bounds using color schemes, and give a glimpse of the proof for determining the uniform Turán density of the tight 3-uniform cycle C(3), ℓ ≥ 5.

26.01.2022
Kalina Petrova (ETHZ)
Resilience of Loose Hamilton Cycles in Random 3-Uniform Hypergraphs

Abstract: Consider a random 3-uniform hypergraph H ~ H3(np) on n vertices, where each triple of vertices form a hyperedge with probability p. In this work, we prove a resilience result for H with respect to the property of containing a loose Hamilton cycle, that is, a cycle in which consecutive edges overlap in one vertex. More specifically, we show that there is a C s.t. if p >= C n-3/2 log(n), H is with high probability such that any spanning subgraph of H with minimum degree at least (7/16 + o(1)) p (n-1) (n-2) / 2 has a loose Hamilton cycle. This is optimal with respect to the resilience constant, but presumably not with respect to p. We also show a corresponding result about minimum co-degree, which is optimal with respect to both the resilience constant and p. Namely, there is a C s.t. if p >= C n-1 log(n), H is with high probability such that any spanning subgraph of H in which each pair of vertices is in at least (1/4 + o(1)) p (n-2) edges has a loose Hamilton cycle. This is joint work with Miloš Trujić.

20.01.2022
Tibor Szabó (FU Berlin)
Improved Integrality Gap in Restricted Max-Min Allocation

Abstract: In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Our main innovation is to introduce the use of topological methods for the restricted max-min allocation problem, to replace the combinatorial ones. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.

12.01.2022
Amedeo Sgueglia (LSE)
Multi-round Maker-Breaker Games

Abstract: We consider a new procedure, which we call Multi-round Maker-Breaker Game. Maker and Breaker start from G0:=Kn and play several rounds of a usual Maker-Breaker game, where, for i ≥ 1, the i-th round is played as follows. They claim edges of Gi-1 until all edges are distributed, and then they set Gi to be the graph consisting only of Maker's edges. They will then play the next round on Gi.

This creates a sequence of graphs G0 ⊃ G1 ⊃ G2 ⊃ ... and, given a monotone graph property, the question is how long Maker can maintain it, i.e. what is the largest k such that Maker has a strategy to guarantee that Gk satisfies such property. We will answer this question for several graph properties.

This is joint work with Juri Barkey, Dennis Clemens, Fabian Hamann, and Mirjana Mikalački.

05.01.2022
Felix Clemen (UIUC)
Max cuts in triangle-free graphs

Abstract: A well-known conjecture by Erdős states that every triangle-free graph on n vertices can be made bipartite by removing at most n2/25 edges. This conjecture is known to be true for graphs with edge density at least 0.4 and also for graphs with edge density at most 0.172. We present progress on this conjecture; we prove the conjecture for graphs with edge density at most 0.2486 and for graphs with edge density at least 0.3197. Further, we prove that every triangle-free graph can be made bipartite by removing at most n2/23.5 edges improving the previously best bound of n2/18. Time permitting, we will discuss related questions. This is joint work with József Balogh and Bernard Lidický.

16.12.2021
Olaf Parczyk (FU Berlin)
Density of triangles and independent sets of size three

Abstract: The triangle-density of a graph G is the number of triangles in G divided by the number of possible triangles. In this talk we will characterise all pairs (x,y), where x is the triangle-density in G and y the triangle-density in the complement of G. This is based on two papers of Huang, Linial, Naves, Peled, and Sudakov.

08.12.2021
Alberto Espuny Díaz (TU Ilmenau)
Path decompositions of random directed graphs

Abstract: In this talk we consider the problem of decomposing the edges of a directed graph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph.

The problem of determining the path number is generally NP-hard. However, there is a simple lower bound for the path number of a digraph in terms of its degree sequence, and a conjecture of Alspach, Mason, and Pullman from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular, I will discuss some of the ingredients of a recent result showing that the conjecture holds with high probability for the random directed graph Dn,p for a large range of p.

This is joint work with Viresh Patel and Fabian Stroh.

01.12.2021
Simón Piga (Universität Hamburg)
Codegree threshold for cycle decompositions in 3-uniform hypergraphs

Abstract: We show that 3-graphs on n vertices whose codegree is at least (2/3+o(1))n can be decomposed into tight cycles of fixed length, subject to the trivial necessary divisibility conditions. We also provide a construction showing this result is best possible up to the o(1) term. All together, our results solve a recent conjecture by Glock, Kühn, and Osthus.

24.11.2021
Pedro Araújo (Czech Academy of Sciences)
Tight Hamilton cycles in uniformly dense hypergraphs

Abstract: We study Hamiltonicity in quasirandom hypergraphs. We show that if an n-vertex 3-uniform hypergraph H=(V,E) has the property that for any set of vertices X and for any collection P of pairs of vertices, the number of hyperedges composed by a pair belonging to P and one vertex from X is at least (1/4+o(1))|X||P| - o(|V|³) and H has minimum vertex degree at least Ω(|V|²), then H contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context.

We will also discuss possible extensions to higher uniformities.

18.11.2021
Leticia Mattos (FU Berlin)
Hitting all maximum independent sets

Abstract: For a graph G on n vertices and independence number a(G) = an, let a'(G)=a'n denote the average value of the independence number of the induced subgraph of G on a uniform random set of vertices. Very recently, Friedgut, Kalai and Kindler (FKK) raised the following conjecture: for any a < 1/2 there is an c(a)>0 so that for every graph G with n vertices and independence number an, we have a'(G) < a - c(a). In this literature seminar, we will show a result of Alon which proves the FKK conjecture in the range where a > 1/4. We will also show his other result which states that the FKK conjecture holds for regular graphs when a > 1/8. If time allows, we will also show Alon's counterexamples for another related conjecture raised by FKK.

10.11.2021
Michael Anastos (FU Berlin)
Determining the Hamiltonicity of sparse graphs in polynomial expected time

Abstract: The Hamilton cycle problem asks to determines whether a given graph G has a Hamilton cycle. It belongs to the list of Karp’s 21 NP-complete problems and if P ≠ NP then there does not exist an algorithm that determines the Hamiltonicity of G in poly(n) time for every graph G on n vertices. On the other hand Gurevich and Shelah gave an algorithm that determines the Hamiltonicity of an n-vertex graph in poly(n) time on average. Equivalently the expected running time of their algorithm over the input distribution G ∼ G(n, p) is polynomial in n when p = 1/2. The last statement raises the question for which values of p there exist an algorithm that solves the Hamilton cycle problem in polynomial expected running time over the input distribution G ∼ G(n, p). Gurevich and Shelah, Thomason and Alon and Krivelevich gave such an algorithm for p ∈ [0, 1] being constant, p ≥ 12n−1/3 and p ≥ 70n-1/2 respectively. In this talk we present an algorithm which solves the Hamilton cycle problem in polynomial expected running time over the input distribution G ∼ G(n, p) for p ≥ 500/n.

21.10.2021
Leticia Mattos (FU Berlin)
Clique packings in random graphs

Abstract: Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p ∈ (0,1) and k = k(n,p) - O(1).

In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p ∈ (0,1) and k = k(n,p) - O(1). To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris.