21.11.2024

Aldo Kiem (Zuse-Institut Berlin)

Forcing Graphs and Graph Algebra Operators (Part II)

14.11.2024

Aldo Kiem (Zuse-Institut Berlin)

Forcing Graphs and Graph Algebra Operators

21.10.2024
(14:15 - 15:45 in T9/046)

Victor Falgas-Ravry (Umea University)

17.10.2024

Joseph Fehribach (Worcester Polytechnic Institute)

22.08.2024

Anita Liebenau (UNSW Sydney)

22.08.2024

Michael Anastos (Institute of Science and Technology Austria)

22.08.2024

Shagnik Das (National Taiwan University)

22.08.2024

Gregory Sorkin (London School of Economics and Political Science)

03.07.2024

Jie Han (Beijing Institute of Technology)

26.06.2024

Tibor Szabó (Freie Universität Berlin)

05.06.2024

Dhruv Mubayi
(University of Illinois)

28.05.2024
(10:00-12:00, A7/031)

Richard Lang
(University Hamburg)

14.02.2024

Yannick Mogge
(TUHH)

Michael Krivelevich
(Tel Aviv University)

Peter Martin
(FU Berlin)

Alexandra Wesolek
(TU Berlin)

Michael Krivelevich
(Tel Aviv University)

Raphael Steiner
(ETH Zürich)

Jan Volec
(Czech Technical University in Prague)

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.   

Michael Krivelevich (Tel Aviv University)

Improving graph's parameters through random perturbation

Abstract: Let G be a graph on n vertices, and assume that its minimum degree is at least k, or its independence number is at most t. What can be said then about various graph-theoretic parameters of G, such as connectivity, large minors and subdivisions, diameter, etc.? Trivial extremal examples (disjoint cliques, unbalanced complete bipartite graphs, random graphs and their disjoint unions) supply rather prosaic bounds for these questions. We show that the situation is bound to change dramatically if one adds relatively few random edges on top of G (the so called randomly perturbed graph model, launched in a paper by Bohman, Frieze and Martin from 2003). Here are representative results, in a somewhat approximate form:
- Assuming delta(G)>=k, and for s<ck, adding about Cns*log (n/k)/k random edges to G results with high probability in an s-connected graph;
- Assuming alpha(G)<= t and adding cn random edges to G typically produces a graph containing a minor of a graph of average degree of order n/sqrt{t}.

In this talk I will introduce and discuss the model of randomly perturbed graphs, and will present our results.

A joint work with Elad Aigner-Horev and Dan Hefetz.

Peter Martin (FU Berlin)

Lower bounds on Ramsey multiplicity of cliques..

Abstract: Ramsey theory asks how many vertices a complete graph needs to have to guarantee a monochromatic (m.c.) clique of size t in any 2-colouring of the edges. Ramsey multiplicity studies how many of such m.c. cliques are guaranteed beyond that. In this talk we will see central definitions and simple bounds by Erdős. Conlon improved the asymptotic (w.r.t. n) lower bound on the guaranteed number of m.c. cliques of size t in a complete graph of size n (together with any edge 2-colouring) from being a 4^{-t^2(1+o(1))} fraction of all t-sets to being a (2\sqrt(2))^{-(t^2(1+o(1)))} fraction and further to a C^{-(t^2(1+o(1)))} fraction, where C is around 2.18.

Alexandra Wesolek (TU Berlin)

Cops and Robber Game on Surfaces.

Abstract: The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuit-evasion games. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces. We obtain the surprising result that on surfaces of constant curvature two cops have a strategy to come arbitrarily close to the robber, independently of the genus of the surface.
Joint work with Vesna Iršič and Bojan Mohar.

Michael Krivelevich (Tel Aviv University)

Percolation through isoperimetry.

Abstract: Let G be a d-regular graph of growing degree on n vertices, and form a random subgraph G_p of G by retaining edge of G independently with probability p=p(d). Which conditions on G suffice to observe a phase transition at p=1/d, similar to that in the binomial random graph G(n,p), or, say, in a random subgraph of the binary hypercube Q^d?
We argue that in the supercritical regime p=(1+epsilon)/d, epsilon>0 being a small constant, postulating that every vertex subset S of G of at most n/2 vertices has its edge boundary at least C|S|, for some large enough constant C=C(\epsilon)>0, suffices to guarantee likely appearance of the giant component in G_p. Moreover, its asymptotic order is equal to that in the random graph G(n,(1+\epsilon)/n), and all other components are typically much smaller.
We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

Raphael Steiner (ETH Zürich)

Hadwiger's conjecture and topological bounds.

Abstract: The Odd Hadwiger's conjecture, formulated by Gerards and Seymour in 1995, is a substantial strengthening of Hadwiger's famous coloring conjecture from 1943. We investigate whether the hierarchy of topological lower bounds on the chromatic number, introduced by Matoušek and Ziegler (2003) and refined recently by Daneshpajouh and Meunier (2023), forms a potential avenue to a disproof of Hadwiger's conjecture or its odd-minor variant.
In this direction, we prove that, in a very general sense, every graph G that admits a topological lower bound of t on its chromatic number, contains K⌊t/2⌋+1 as an odd-minor. This solves a problem posed by Simonyi and Zsbán [European Journal of Combinatorics, 31(8), 2110--2119 (2010)]. We also prove that if for a graph G the Dol'nikov-Kříž lower bound on the chromatic number (one of the lower bounds in the aforementioned hierarchy) attains a value of at least t, then G contains Kt as a minor.
Finally, extending results by Simonyi and Zsbán, we show that the Odd Hadwiger's conjecture holds for Schrijver and Kneser graphs for any choice of the parameters. The latter are canonical examples of graphs for which topological lower bounds on the chromatic number are tight.

Jan Volec (Czech Technical University in Prague)

On the minimum eigenvalue of regular triangle-free graphs.

Abstract: Motivated by two well-known conjectures of Erdős on triangle-free graphs, Brandt asked in 1994 whether the smallest eignvalue of an n-vertex d-regular triangle-free graph is at most 4n/25 - d. In this talk, we confirm the conjecture of Brandt in a stonger sense: we show that the smallest eigenvalue of the signless Laplacian of any n-vertex triangle-free graph G is at most 15n/94 < 0.1596n. In particular, if G is d-regular, then its smallest eigenvalue is at most 15n/94 - d.
This is a joint work with Jozsi Balogh, Felix Clemen, Bernard Lidický and Sergey Norin.

Yamaan Attwa (FU Berlin)

Erdős-Hajnal is true for an infinite family of prime graphs.

Abstract: We say that a graph H has the Erdős-Hajnal property if there exists some ε = ε(H)>0 such that every H-free graph G has a homogeneous set of size at least |G|^ε. Erdős and Hajnal conjectured that every graph H has the EH-property. The conjecture is known to be true for the set F of graphs on at most 5 vertices except P₅ and its complement. Alon, Pach and Solymosi proved that if H₁ and H₂ have the EH-property then H constructed by substituting H₁ into a vertex of H₂ also has the EH-property. Until recently, our knowledge of graphs with the EH-property was limited to the smallest family C of graphs containing F and is closed under substitutions. This talk is an exposition of a paper by Nguyen, Scott and Seymour proving for every n ≥ 4 the existence of a graph G_n on n vertices having the EH-property and is unconstructible from smaller graphs by vertex substitutions.

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.

In this talk, I present a new proof of this result with an alternative quantification and then discuss generalisations to hypergraphs.

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.

In this talk, we will prove the conjecture under the additional assumption that $|F| = o(n^{1/3})$ for all $F \in \mathcal{F}$, obtaining sharp bounds on the possible size of the $\theta$-intersecting family for certain values of $\theta$. We will also present some outstanding open problems in this direction.

This is joint work with Niranjan Balachandran and Brahadeesh Sankarnarayanan.

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. 
What if one allows the state of an edge (open or closed) to depend on that of neighbouring edges? Could one use such local dependencies to delay the emergence of an infinite component? Such questions lead to fascinating problems at the interface between extremal combinatorics and percolation theory.  In this talk, I will present recent work related to one such decade-old and still open problem of Balister and Bollobás on 1-independent percolation on high-dimensional integer lattices.
Joint work with Vincent Pfenninger (TU Graz)

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.