Resilience of Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Abstract: Consider a random 3-uniform hypergraph H ~ H^{3}(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ć.
Resilience of Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Abstract: Consider a random 3-uniform hypergraph H ~ H^{3}(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 G_{0}:=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_{0} ⊃ G_{1} ⊃ G_{2} ⊃ ... 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.
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 n^{2}/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^{2}/23.5 edges improving the previously best bound of n^{2}/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 D_{n,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.