Springe direkt zu Inhalt

Research Seminar Combinatorics

Next Talk

Wednesday, January 26th, 2022 at 16:15
Webex (2730 660 4511)
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ć.

<iframe src="https://calendar.google.com/calendar/embed?mode=agenda&height=600&wkst=1&bgcolor=%23FFFFFF&src=dq5vbd4jmriuttn2k4c12s228c%40group.calendar.google.com&color=%23711616&ctz=Europe%2FBerlin" style="border-width:0" width="800" height="350" frameborder="0" scrolling="no"></iframe>

Google Calendar

Schedule and abstracts 2021/2022

DateSpeakerTitle
23.02.2022 Guilherme Mota
(USP)
TBA
16.02.2022 Simona Boyadzhiyska
(FU Berlin)
TBA
09.02.2022 Benjamin Aram Berendsohn
(FU Berlin)
TBA
02.02.2022 Samuel Mohr
(Masaryk University)
TBA
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
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.


Links

Mailing list:

To subscribe to the mailing-list of the seminar, please follow this link:
https://lists.fu-berlin.de/listinfo/combinatorics-seminar

Seminar calendar:

To add the .ics file of the calendar to your favorite calendar reader (that supports the ICal format), please follow this link:
ICal calendar.

To add the calendar feeds to your favorite feed reader, please follow this link:
Calendar feeds.

Notes:

For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de

Archives

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