Seminars in 2022

Thursday 8.9.2022 at 10:00 ICS, room 419 (and on ZOOM), Nina Kamčev (University of Zagreb): Canonical colourings in random graphs

Abstract: Rödl and Ruciński have extended Ramsey’s Theorem to random graphs, showing that there is a constant C such that with high probability, any two-colouring of the edges of G(n, p) with edge probability p = Cn^{−2/(t+1)} contains a monochromatic copy of K_t (the complete t-vertex graph). We investigate how this statement extends to arbitrary colourings of G(n, p). Namely, when no assumptions are made on the edge colouring, one can only hope to find one of the four canonical colourings of K_t, as in the well-known canonical version of Ramsey’s Theorem due to Erdős and Rado. We show that indeed, any colouring of G(n,p) with p = Cn^{−2/(t+1)} contains a canonically coloured copy of K_t. A crucial tool in the proof is the transference principle due to Conlon and Gowers. Joint work with Mathias Schacht.

Monday 27.6.2022 at 10:00 ICS, room 419 (and on ZOOM), Camila Zárate (University of Chile): Antidirected trees in oriented graphs of large semidegree

Abstract: Using the Diregularity Lemma, we prove that a sufficiently large oriented graph with minimum semidegree at least (1+p)k/2 contains a copy of every balanced antidirected tree of k edges and bounded maximum degree.
This is a thesis work under the supervision of Prof. Maya Stein.

Monday 23.5.2022 at 10:00 ICS, room 419 (and on ZOOM), Alberto Espuny Díaz (TU Ilmenau): Hamiltonicity of random subgraphs of the hypercube

Abstract: Finding thresholds for different monotone properties is one of the main goals in random graph theory, but these are easier to determine in some models of random graphs than others. In the case of (binomial) random subgraphs of the hypercube, a longstanding conjecture stated that the threshold for Hamiltonicity should be 1/2. We have recently confirmed this conjecture and obtained several generalisations. In this talk, I will present our results and describe the main ingredients of their proofs.

This is joint work with Padraig Condon, António Girão, Daniela Kühn and Deryk Osthus.

Monday 11.4.2022 at 10:00 ICS, room 318 (and on ZOOM), Oliver Cooley (Graz University of Technology): Paths and cycles in random hypergraphs

Abstract: j-tight paths and cycles, in which consecutive edges intersect in precisely j vertices, are a staple of extremal hypergraph theory, but have seen relatively little attention in the random setting. We present an overview of some recent results concerning the length of the longest j-tight path or cycle in a binomial k-uniform hypergraph. These include phase transition results, analysis via core-type structures, and the sprinkling method. Some arguments are obvious generalisations of known graph proofs, while others require significant additional work. Parts of this talk are based on joint work with Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolás Sanhueza-Matamala and Julian Zalla.

Monday 21.3.2022 at 10:00 ICS, room 419, Pedro Araújo (ICS CAS): Tight Hamiltonian cycles in uniformly dense hypergraphs

Abstract: We discuss several notions of quasirandomness in hypergraphs and their interplay with tight Hamiltonicity.

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|^3) and H has minimum vertex degree at least \Omega(|V|^2), then H contains a tight Hamilton cycle. A probabilistic construction shows that the constant 1/4 is optimal in this context.

We explore possible generalizations for higher uniformities.

This is joint work with Simón Piga and Mathias Schacht.

Monday 14.3.2022 at 10:00 ICS, room 262, Jan Volec (Czech Technical University): On Brandt conjecture on the minimum eigenvalue of regular triangle-free graph

Abstract: Motivated by two well-known conjectures of Erdős on triangle-free graphs, Brandt asked in 1994 whether the smallest eigenvalue of an n-vertex d-regular triangle-free graph is at most 4n/25 - d. In this talk, we confirm the conjecture of Brandt. This is a joint work with Sergey Norin.

Monday 28.2.2022 at 10:00 ICS, room 262 (next to the office of the speaker), Diana Piguet (ICS CAS): Perfect packing of degenerate graphs

Abstract: A family of graphs packs into a host graph if there are edge-disjoint copies of every element of the family in the host graph. I shall talk about perfectly packing degenerate graphs of sublinear maximum degree into complete graphs. This work has been motivated by two beautiful tree-packing conjectures — one of Ringel from 1963 and one of Gyárfás from 1976. This is joint work with Peter Allen, Julia Böttcher, Dennis Clemens, Jan Hladký, and Anusch Taraz.

Monday 14.2.2022 at 10:00 ICS, room 419, Eng Keat Hng (ICS CAS): Minimum degree conditions for powers of cycles and paths

Abstract: We study minimum degree conditions under which a graph G contains kth powers of paths and cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of $G$ is large. This extends a result of Allen, Böttcher and Hladký [J. Lond. Math. Soc. (2) 84(2) (2011), 269--302] concerning the containment of squares of paths and squares of cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative.

Monday 7.2.2022 at 10:00 ICS, room 419, Mykhaylo Tyomkyn (Charles University): Limiting constants for weak saturation of hypergraphs

Abstract: For two r-uniform hypergraphs G and H we say that G is weakly H-saturated if the missing edges in G can be filled one by one, creating a new copy of H at every step. The quantity wsat(n,H) measures the smallest size of a weakly H-saturated r-graph of order n. For r=2 a short argument due to Alon (1985) shows that for any graph H, wsat(n,H)/n tends to a limit as n increases. Tuza conjectured in 1992 that for arbitrary r the quantity wsat(n,H)/n^{r-1} similarly has a limit c(H). I will present a recent proof of Tuza's conjecture.

Joint work with Asaf Shapira (Tel Aviv University).

Wednesday 12.1.2022 at 10:00 ICS, room 318, Jan Grebík (Warwick): Local problems on bounded degree graphs

Abstract: I will discuss some recent progress on connections between distributed computing and descriptive combinatorics. The connection is phrased in the language of local problems, i.e., coloring problems where a correctness of a given candidate coloring can be checked locally. In both fields, the goal is to understand how difficult is to produce a coloring that solves a given local problem. I will focus on the case of oriented paths, however, if time permits we might discuss other classes of graphs. This is joint work Vasek Rozhon.