Springe direkt zu Inhalt

2021/2022

Talks normally take place Wednesdays or Thursdays.

DateSpeakerTitle
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
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.