Abstract: Alon and Krivelevich proved that for every n-vertex subcubic graph H and every integer q ≥ 2 there exists a (smallest) integer f = f(H,q) such that every K_f-minor contains a subdivision of H in which the length of every subdivision-path is divisible by q. Improving their superexponential bound, we show that f(H, q) ≤ 10.5qn + 8n + 14q, which is optimal up to a constant multiplicative factor.

This is joint work with Nemanja Draganić and Raphael Steiner.

Abstract: A graph G is r-Ramsey for a graph H, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property.

In 1976, Burr, Erdős and Lovász introduced the study of the smallest minimum degree s_r(k) of a graph G such that G is r-Ramsey-minimal for a complete graph of size k. They were able to show the rather surprising exact result, that with two colours, then s₂(k) = (k-1)². The behaviour of this function is still not so well understood for more than 2 colours. In 2016, Fox, Grinshpun, Liebenau, Person, and Szabó showed that for r > 2, s_r(k) is at most 8(k-1)⁶r³. The speaker, together with John Bamberg and Anurag Bishnoi, have recently used a group theoretic model of generalised quadrangles introduced by Kantor in 1980, coupled with a probabilistic approach, to improve this bound.

Abstract: Katona's intersection theorem states that every intersecting family ℱ ⊆ [n]^(k) satisfies |∂ℱ| ≥ |ℱ|, where ∂ℱ = {F\x : x∊F∊ℱ} is the shadow of ℱ. Frankl conjectured that for n>2k and every intersecting family ℱ⊆ [n]^(k), there is some i∊[n] such that |∂ℱ(i)| ≥  |ℱ(i)|.

Here, we prove this conjecture in a very strong form for n > (k+1)k/2. In particular, our result implies that for any j∊[k], there is a sequence a₁,...,a_j∊[n] such that |∂ℱ(a₁,...,a_j)| ≥  |ℱ(a₁,...,a_j)|.

Further, Frankl conjectured that for n > k+ℓ and cross-intersecting families G⊆ [n]^(ℓ) and ℋ⊆ [n]^(k), there is some i∊[n] such that |∂G(i)| ≥ |G(i)| or |∂ℋ(i)| ≥ |ℋ(i)|. We prove this conjecture again in a very strong form for n > kℓ.

This is joint work with Marcelo Sales.

Abstract: The single-player board game (Peg) Solitaire has been around for centuries and eventually attracted researchers from mathematics and computer science. Recently, but certainly very naturally, peg solitaire was extended to graphs. The game rules are as follows: Place pegs on all vertices but one of a (connected) finite simple graph G. If u,v and w are vertices of G such that uv and vw are edges of G and there are pegs on u and v but not on w, then it is possible to jump with the peg from u onto w removing the peg from v in the process. Usually one tries to eliminate all but one peg from the graphs vertices by using such jumps, calling a graph solvable if that is possible.

This talk serves as an introduction to the game and provides an overview of major developments and open problems. Moreover, typical methods used in the proofs of known results will be presented. Several variations of the game, for example a misère version, were also considered recently, some of which will be discussed in this talk as well.

Abstract: Given two graphs, G and H, let us denote by V(G), V(H) and E(G), E(H) their vertex and edge sets respectively. Define the Xor product, s the graph with the vertex set V=V(G) × V(H), and two vertices (g,h) and (g',h') are connected if and only if among the statements gg' ∊ E(G) and hh' ∊ E(H) exactly one occurs.

In this talk we examine the clique number of the Xor product of two isomorphic KG(N,k) Kneser graphs, denote this number with f(k,N). We discuss the background of the problem and we give lower and upper bounds on f(k,N). Furthermore we determine f(k,N) up to a constant deviation depending only on k, and find the exact value for f(2,N) if N is large enough. We also compute that f(k,k²) is asymptotically equivalent to k².

Abstract: Gerencsér and Gyárfás proved in 1967 that for any 2-colouring of the edges of the complete graph with n vertices, K_n, it is possible to partition V(K_n) into two monocromatic paths. This result, which has a straightforward proof, motivated many other challenging problems that have been extensively studied in the last years. For instance, an open conjecture of Erdős, Gyárfás and Pyber from 1991 states that for any r-colouring of the edges of K_n there are r monochromatic paths partitioning V(K_n). We can also find in the literature other versions of the problem where instead of partitioning into paths, we are interested in partitioning into trees, cycles, or even power of cycles.

Grinshpun and Sárközy studied a more general version of the problem where they were interested in partitioning V(K_n) into few monochromatic subgraphs which are copies of a given family of bounded degree graphs. They proved that for any family of graphs S = {F₁, F₂, F₃, ...} such that F_i has exactly i vertices and maximum degree at most D, the following holds: for any 2-colouring of edges of K_n, there is a partition of V(K_n) into at most exp(O(D log D)) monochromatic subgraphs that are copies of graphs from S. They conjectured that for any r-colouring of the edges of K_n, it is possible to partition V(K_n) into exp(D^C) monochromatic subgraphs that are copies of graphs from S, where C=C(r) is a constant that only depends on r. In this talk, we present the first progress towards Grinshpun-Sárközy conjecture by establishing a super-exponential bound.

Abstract: Turán-type problems for hypergraphs are famously interesting and difficult. For example, for 3-uniform hypergraphs, the Turán density of F is known for very few hypergraphs F. The topic of this talk are Turán-type problems for 3-uniform tight cycles C_k, where the number of vertices k is not divisible by 3.

The Turán density of a family of 3-graphs F, denoted π(F) , is the limit of the maximum density of an n-vertex 3-graph not containing a member of F. There is an iterated construction of a C₅-free 3-graph H_n with edge density asymptotic to 2√3−3 ≈ 0.464 due to Mubayi and Rödl. Razborov showed that π(C₅) ≤ 0.468, indicating that H_n might be optimal for C₅. We show that H_n is asymptotically optimal for an enlarged family of graphs - namely, π(F_K) = 2√3−3, where F_K is the family of tight cycles whose length k is not divisible by 3 and is bounded by an absolute constant K. One of our main tools, which may be of independent interest, is a 3-uniform analogue of the statement `a graph is bipartite if and only if it does not contain an odd cycle'.

Joint work with Shoham Letzter and Alexey Pokrovskiy.

Abstract: A simple random greedy algorithm can almost perfectly pack graphs with bounded degeneracy and almost linear maximum degree into the complete graph. I will explain how the algorithm works and sketch the analysis.

In some situations, one can add further ideas to get from almost perfect packings to perfect packings. I will describe two ways, which together prove the Gýarfás Tree Packing Conjecture (which says that T₁,...,T_n pack into K_n, where each T_i has i vertices) with a restriction cn/log n on the maximum degree of the trees.

This is joint work with Julia Böttcher, Dennis Clemens, Jan Hladký, Diana Piguet and Anusch Taraz.

Abstract: A system of linear equations L over the finite field F_q is common if the number of solutions to L in any two-colouring of F_qⁿ is asymptotically (as n→∞) at least the expected number of monochromatic solutions in a random colouring of F_qⁿ. 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 Z_N and over F₅).

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.

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 ω(n^1/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{n^1/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.

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

We determine the threshold for the property G(n,p) --> (H₁,H₂) when H₂ is a forest.

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

Abstract: We consider a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem by studying the maximum number ex_F(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 ex_F(n,G) is quadratic and prove several asymptotic results using various tools from the regularity lemma and supersaturation to graph packing results.

Abstract: In this paper we show that the largest possible size of a subset of F_qⁿ 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(n^q−2). This improves on the previously best known bound due to Naslund and refutes a conjecture of Ge and Shangguan. A lower bound of n^q/3 is also presented.

It is also shown that a subset of F_qⁿ avoiding triangles with all right angles can have size at most O(n^2q−2). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset A ⊂ F_qⁿ 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.

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.

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.

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 K₄^(3)- and K₄⁽³⁾. 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 K₄^(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_ℓ⁽³⁾, ℓ ≥ 5.

Abstract: Consider a random 3-uniform hypergraph H ~ H³(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ć.

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.

Abstract: We consider a new procedure, which we call Multi-round Maker-Breaker Game. Maker and Breaker start from G₀:=K_n 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 G_i-1 until all edges are distributed, and then they set G_i to be the graph consisting only of Maker's edges. They will then play the next round on G_i.

This creates a sequence of graphs G₀ ⊃ G₁ ⊃ G₂ ⊃ ... 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 G_k 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.

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 n²/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 n²/23.5 edges improving the previously best bound of n²/18. Time permitting, we will discuss related questions. This is joint work with József Balogh and Bernard Lidický.

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.

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 D_n,p for a large range of p.

This is joint work with Viresh Patel and Fabian Stroh.

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.

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.

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.

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.

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.