Research Seminar Combinatorics
Schedule and abstracts 2023/2024
Date | Speaker | Title |
---|---|---|
04.12.2024 |
Milos Stojakovic (University of Novi Sad) |
|
28.11.2024 |
Christoph Spiegel (Zuse-Institut Berlin) |
|
21.11.2024 |
Aldo Kiem (Zuse-Institut Berlin) |
|
14.11.2024 |
Aldo Kiem (Zuse-Institut Berlin) |
|
21.10.2024 |
Victor Falgas-Ravry (Umea University) |
1-independent percolation on high dimensional lattices |
17.10.2024 |
Joseph Fehribach (Worcester Polytechnic Institute) |
Families of Kirchhoff Graphs |
22.08.2024 |
Anita Liebenau (UNSW Sydney) |
Ramsey with purple edges |
22.08.2024 |
Michael Anastos (Institute of Science and Technology Austria) |
Climbing up a random subgraph of the hypercube |
22.08.2024 |
Shagnik Das (National Taiwan University) |
Fractionally Intersecting Families |
22.08.2024 |
Gregory Sorkin (London School of Economics and Political Science) |
Matchings and Loose Cycles in the Semirandom Hypergraph Model |
03.07.2024 |
Jie Han (Beijing Institute of Technology) |
Graph Theory theorems in random graphs |
26.06.2024 |
Tibor Szabó (Freie Universität Berlin) |
Global rigidity of random graphs in R |
|
Dhruv Mubayi |
New bounds for the Erdős-Rogers problem |
|
Richard Lang |
A hypergraph bandwidth theorem |
14.02.2024 |
Yannick Mogge |
Creating a tree universal graph in positional games |
08.02.2024 |
Michael Krivelevich |
Improving graph's parameters through random perturbation |
01.02.2024 |
Peter Martin |
Lower bounds on Ramsey multiplicity of cliques. |
25.01.2024 |
Alexandra Wesolek |
Cops and Robber Game on Surfaces. |
17.01.2024 |
Michael Krivelevich |
Percolation through isoperimetry. |
11.01.2024 |
Raphael Steiner |
Hadwiger's conjecture and topological bounds. |
17.11.2023 |
Jan Volec |
On the minimum eigenvalue of regular triangle-free graphs. |
02.11.2023 |
Yamaan Attwa |
Erdős-Hajnal is true for an infinite family of prime graphs. Part II |
26.10.2023 | Yamaan Attwa (FU Berlin) |
Erdős-Hajnal is true for an infinite family of prime graphs. Part I |
Yannick Mogge (TUHH) |
Creating a tree universal graph in positional games |
Abstract: In this talk we consider positional games, where the winning sets are tree universal graphs, which contain copies of all spanning trees with a certain maximum degree. In particular, we show that in the unbiased Maker-Breaker and Waiter-Client game on the complete graph $K_n$, Maker/Waiter has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. This is a joint work with Grzegorz Adamski, Sylwia Antoniuk, Małgorzata Bednarska-Bzdȩga, Dennis Clemens, and Fabian Hamann. |
Richard Lang (Univiersity Hamburg) |
A hypergraph bandwidth theorem |
Abstract: A classic result of Dirac states a graph has a Hamilton cycle provided that every vertex is adjacent to at least half of the other vertices. The Bandwidth Theorem asserts that under mildly stronger assumptions one can even embed all bipartite graphs with sublinear bandwidth and constant maximum degree. Analogous statements are known to hold for embedding graphs with higher chromatic number. |
Tibor Szabó (Freie Universität Berlin) |
Global rigidity of random graphs in R |
Abstract: Consider the Erd\H os-R\'enyi random graph process in which we start with an empty graph $G_0$ on the vertex set $[n]$, and in each step form $G_i$ from $G_{i-1} by adding one new edge chosen uniformly at random. Resolving a conjecture by Benjamini and Tzalik, we give a simple proof that w.h.p. as soon as $G_m$ has minimum degree $2$ it is globally rigid in the sense that any injective embedding of $[n]$ into $\mathbb{R}$ can be uniquely reconstructed (up to isometry) from the length of the segments corresponding to the edges of $G_m$. We also resolve a related question of Girao, Illingworth, Michel, Powierski, and Scott in the sparse regime of the random graph and offer open problems. Joint work with Richard Montgomery, Rajko Nenadov, and Julien Portier. |
Jie Han (Beijing Institute of Technology) |
Graph Theory theorems in random graphs |
Abstract: There has been a growing interest in extending graph theory theorems into the random graph setting. We will survey this line of problems and mention some recent developments. |
Gregory Sorkin (London School of Economics and Political Science) |
Matchings and Loose Cycles in the Semirandom Hypergraph Model |
Abstract: The "semirandom graph process", introduced in 2020, has attracted a good deal of study. I will discuss the 2-offer 3-uniform semirandom hypergraph model on $n$ vertices. Here, at each step, we are presented with 2 uniformly random vertices. We choose any other vertex, thus creating a hyperedge of size 3. We show a strategy that constructs a perfect matching, and another that constructs a loose Hamilton cycle, both succeeding asymptotically almost surely within $\Theta(n)$ steps. Our methods are qualitatively different from those that have been used for semirandom graphs. Much of the analysis is done on an auxiliary graph that is a uniform $k$-out subgraph of a random bipartite graph, and this tool may be useful in other contexts. |
Shagnik Das (National Taiwan University) |
Fractionally Intersecting Families |
Abstract: Introduced by Balachandran, Mathew and Mishra, a $\theta$-intersecting family, where $\theta \in (0,1)$, is a family $\mathcal{F}$ of subsets of $[n]$ such that for any distinct sets $F, G\in \mathcal{F}$, we have $|F \cap G| \in \{ \theta |F|, \theta |G| \}$. Balachandran, Mathew and Mishra proved that any $\theta$-intersecting family has size $O(n \log n)$, and conjectured that this could be improved to $O(n)$, which would be tight. |
Michael Anastos (Institute of Science and Technology Austria) |
Climbing up a random subgraph of the hypercube |
Abstract:The d-dimensional hypercube, Q^d , is the graph whose vertex set is {0, 1}^d , and where two vertices are adjacent if they differ in exactly one coordinate. The hypercube and its subgraphs rise naturally in many contexts and have received much attention in combinatorics, probability, and computer science. The random subgraph Q^d_p is obtained by retaining each edge in E(Q^d ) independently with probability p. Several phase transitions have been observed in Q^d_p . For example, Ajtai, Komlos, and Szemeredi proved that if dp < 1 then all the complements of Q^d_p are of logarithmic size whereas if dp > 1 then Q^d_p spans a linear (in the number of vertices) size component. In this talk, we will discuss another phase transition in the hypercube, which occurs when p = e/d and is marked by the likely appearanced of an ‘increasing’ path from the all-zeros vertex to the all-ones vertex. This talk is based on joint work with Sahar Diskin, Dor Elboim, and Michael Krivelevich. |
Anita Liebenau (UNSW Sydney) |
Ramsey with purple edges |
Abstract: Motivated by a question of David Angell, we study a variant of Ramsey numbers where some edges are coloured both red and blue, or: purple. Specifically, we are interested in the largest number g = g(s, t, n), for some s and t and n < R(s, t), such that there exists a red-blue-purple colouring of Kn with g purple edges, without a red-purple K_s and without a blue-purple K_t. We determine g asymptotically for a large family of parameters. The talk will be introductory in nature. Joint work with Thomas Lesgourgues and Nye Taylor. |
Joseph Fehribach (Worcester Polytechnic Institute) |
Families of Kirchhoff Graphs |
Abstract: Given a set of n vectors in any vector space over the rationals, suppose that k<n are linear independent. Kirchhoff graphs are vector graphs (graphs whose edges are these vectors), whose cycles represent the dependencies of these vectors and whose vertex cuts are orthogonal to these cycles. This presentation discusses the uniformity of vector 2-connected Kirchhoff graphs, and how graph tiling can generate families of Kirchhoff graphs. These families are composed of prime graphs (those having no Kirchhoff subgraphs), and composite graphs (not prime), all generated by a set of fundamental Kirchhoff graphs (smallest prime Kirchhoff graphs that can generate other prime and composite graphs for our set of vectors). |
Victor Falgas-Ravry (Umea University) |
1-independent percolation on high dimensional lattices |
Abstract: The celebrated Harris-Kesten theorem states that if each edge of the square integer lattice is open with probability p, independently of all other edges, then for p at most 1/2 almost surely all connected components of open edges are finite, while if p>1/2 almos surely there exists a unique infinite connected component of open edges. |
Aldo Kiem (Zuse-Institut Berlin) |
Forcing Graphs and Graph Algebra Operators |
Abstract: We report on recent progress on Sidorenko's conjecture and the forcing conjecture. Our main observation is that graph operators such as subdivisions, blow-ups or adding disjoint vertices correspond to order-preserving operators on Graph Algebras. This way we easily obtain some new results, in particular that the proper balanced blow-ups of Sidorenko graphs are forcing. This is joint work with Olaf Parczyk and Christoph Spiegel. The talk will survey our results and assume no prerequisites with graph algebras and categories. |
Christoph Spiegel (Zuse-Institut Berlin) |
An Unsure Talk on an Un-Schur Problem |
Abstract: Graham, Rödl, and Ruciński originally posed the problem of determining the minimum number of monochromatic Schur triples that must appear in any 2-coloring of the first $n$ integers. This question was subsequently resolved independently by Datskovsky, Schoen, and Robertson and Zeilberger. In this talk we will study a natural anti-Ramsey variant of this question and establish the first non-trivial bounds by proving that the maximum fraction of Schur triples that can be rainbow in a given $3$-coloring of the first $n$ integers is at least $0.4$ and at most $0.66656$. We conjecture the lower bound to be tight. This question is also motivated by a famous analogous problem in graph theory due to Erdős and Sós regarding the maximum number of rainbow triangles in any $3$-coloring of $K_n$, which was settled by Balogh et al. The contents of this talk are joint work with Olaf Parczyk. |
Milos Stojakovic (University of Novi Sad) |
Maker-Breaker games on random boards |
Abstract: In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph H). Breaker wins otherwise. |
Links
Mailing list:
To subscribe to the mailing-list of the seminar, please follow this link:
https://lists.fu-berlin.de/listinfo/combinatorics-seminar
Notes:
For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de
Archives
Schedule and abstracts 2024/2025
Schedule and abstracts 2023/2024
Schedule and abstracts 2022/2023
Schedule and abstracts 2021/2022
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