Springe direkt zu Inhalt

Research Seminar Combinatorics

Next Talk

Wednesday, July 6th, 2022 at 16:15
A3 SR120
Bjarne Schülke (Caltech)
A local version of Katona's intersection theorem

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 a1,...,aj∊[n] such that |∂ℱ(a1,...,aj)| ≥  |ℱ(a1,...,aj)|.

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.

<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
06.07.2022 Bjarne Schülke
(Caltech)
A local version of Katona's intersection theorem
22.06.2022 Jan-Hendrik de Wiljes
(FU Berlin)
Peg Solitaire on Graphs
15.06.2022 Adam Schweitzer
(Berlin Mathematical School)
Clique number of Xor products of Kneser graphs
08.06.2022 Walner Mendonça
(ISTA)
Tiling edge-coloured graphs with few monochromatic bounded-degree graphs
01.06.2022 Nina Kamčev
(University of Zagreb)
The Turán density of 3-uniform tight cycles
25.05.2022 Peter Allen
(LSE)
Packing degenerate graphs
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
06.07.2022
Bjarne Schülke (Caltech)
A local version of Katona's intersection theorem

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 a1,...,aj∊[n] such that |∂ℱ(a1,...,aj)| ≥  |ℱ(a1,...,aj)|.

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.

22.06.2022
Jan-Hendrik de Wiljes (FU Berlin)
Peg Solitaire on Graphs

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.

15.06.2022
Adam Schweitzer (Berlin Mathematical School)
Clique number of Xor products of Kneser graphs

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,k2) is asymptotically equivalent to k2.

08.06.2022
Walner Mendonça (ISTA)
Tiling edge-coloured graphs with few monochromatic bounded-degree graphs

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, Kn, it is possible to partition V(Kn) 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 Kn there are r monochromatic paths partitioning V(Kn). 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(Kn) into few monochromatic subgraphs which are copies of a given family of bounded degree graphs. They proved that for any family of graphs S = {F1, F2, F3, ...} such that Fi has exactly i vertices and maximum degree at most D, the following holds: for any 2-colouring of edges of Kn, there is a partition of V(Kn) 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 Kn, it is possible to partition V(Kn) into exp(DC) 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.

01.06.2022
Nina Kamčev (University of Zagreb)
The Turán density of 3-uniform tight cycles

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 Ck, 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 C5-free 3-graph Hn with edge density asymptotic to 2√3−3 ≈ 0.464 due to Mubayi and Rödl. Razborov showed that π(C5) ≤ 0.468, indicating that Hn might be optimal for C5. We show that Hn is asymptotically optimal for an enlarged family of graphs - namely, π(FK) = 2√3−3, where FK 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.

25.05.2022
Peter Allen (LSE)
Packing degenerate graphs

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 T1,...,Tn pack into Kn, where each Ti 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.

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.


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