## Seminars and Colloquia by Series

### Constructing non-bipartite $k$-common graphs

Series
Graph Theory Seminar
Time
Tuesday, May 4, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Fan WeiPrinceton University

A graph $H$ is $k$-common if the number of monochromatic copies of $H$ in a $k$-edge-coloring of $K_n$ is asymptotically minimized by a random coloring. For every $k$, we construct a connected non-bipartite $k$-common graph. This resolves a problem raised by Jagger, Stovicek and Thomason. We also show that a graph $H$ is $k$-common for every $k$ if and only if $H$ is Sidorenko and that $H$ is locally $k$-common for every $k$ if and only if H is locally Sidorenko.

### Maximum number of almost similar triangles in the plane

Series
Graph Theory Seminar
Time
Tuesday, April 27, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Bernard LidickýIowa State University

A triangle $T'$ is $\varepsilon$-similar to another triangle $T$ if their angles pairwise differ by at most $\varepsilon$. Given a triangle $T$, $\varepsilon >0$ and $n \in \mathbb{N}$, Bárány and Füredi asked to determine the maximum number of triangles $h(n,T,\varepsilon)$ being $\varepsilon$-similar to $T$ in a planar point set of size $n$. We show that for almost all triangles $T$ there exists $\varepsilon=\varepsilon(T)>0$ such that $h(n,T,\varepsilon)=n^3/24 (1+o(1))$. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Felix Christian Clemen.

### Universal graph product structures

Series
Graph Theory Seminar
Time
Tuesday, April 20, 2021 - 17:45 for 1 hour (actually 50 minutes)
Location
Speaker
David WoodMonash University

Please Note: Note the unusual time: 5:45pm.

This talk will survey recent results that describe graphs as subgraphs of products of simpler graphs. The starting point is the following theorem: every planar graph is a subgraph of the strong product of some treewidth 7 graph and a path. This result has been the key to solving several open problems, for example, regarding the queue-number and nonrepetitive chromatic number of planar graphs. The result generalises to provide a universal graph for planar graphs. In particular, if $T^7$ is the universal treewidth 7 graph (which is explicitly defined), then every countable planar graph is a subgraph of the strong product of $T^7$ and the infinite 1-way path. This result generalises in various ways for many sparse graph classes: graphs embeddable on a fixed surface, graphs excluding a fixed minor, map graphs, etc. For example, we prove that for every fixed graph $X$, there is an explicitly defined countable graph $G$ that contains every countable $X$-minor-free graph as a subgraph, and $G$ has several desirable properties such as every $n$-vertex subgraph of $G$ has a $O(\sqrt{n})$-separator. On the other hand, as a lower bound we strengthen a theorem of Pach (1981) by showing that if a countable graph $G$ contains every countable planar graph, then $G$ must contain an infinite complete graph as a minor.

### Description:Chromatic index of dense quasirandom graphs

Series
Graph Theory Seminar
Time
Tuesday, April 13, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Songling ShanIllinois State University

Let $G$ be a simple graph with maximum degree $\Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>\Delta(G)\lfloor |V(H)|/2 \rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ on $n$ vertices with $\Delta(G)>n/3$ has chromatic index $\Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, Kühn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. We show that the conjecture of Glock, Kühn and Osthus is affirmative.

### Coloring graphs with forbidden bipartite subgraphs

Series
Graph Theory Seminar
Time
Tuesday, April 6, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
James AndersonGeorgia Institute of Technology

A conjecture by Alon, Krivelevich, and Sudakov in 1999 states that for any graph $H$, there is a constant $c_H > 0$ such that if $G$ is $H$-free of maximum degree $\Delta$, then $\chi(G) \leq c_H \Delta / \log\Delta$. It follows from work by Davies et al. in 2020 that this conjecture holds for $H$ bipartite (specifically $H = K_{t, t}$), with the constant $c_H = (t+o(1))$. We improve this constant to $1 + o(1)$ so it does not depend on $H$, and extend our result to the DP-coloring (also known as correspondence coloring) case introduced by Dvořák and Postle. That is, we show for every bipartite graph $B$, if $G$ is $B$-free with maximum degree $\Delta$, then $\chi_{DP}(G) \leq (1+o(1))\Delta/\log(\Delta)$.

This is joint work with Anton Bernshteyn and Abhishek Dhawan.

### Intersecting families of sets are typically trivial

Series
Graph Theory Seminar
Time
Tuesday, March 30, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Lina LiUniversity of Waterloo

A family of subsets of $[n]$ is intersecting if every pair of its members has a non-trivial intersection. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independently showed that for $n \geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Significantly improving their results, we show that the same conclusion holds for $n \geq 2k + 100 \ln k$. Our proof uses the Sapozhenko’s graph container method and the Das-Tran removal lemma.

This is joint work with József Balogh, Ramon I. Garcia and Adam Zsolt Wagner.

### Speeds of hereditary properties and mutual algebricity

Series
Graph Theory Seminar
Time
Tuesday, March 23, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Caroline TerryOhio State University

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete "jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

### Degree conditions for Hamilton cycles

Series
Graph Theory Seminar
Time
Tuesday, March 9, 2021 - 23:30 for 1 hour (actually 50 minutes)
Location
Speaker
Richard LangHeidelberg University

Please Note: Note the unusual time!

A classic theorem of Dirac (1952) states that a graph in which every vertex is connected to half of the other vertices contains a Hamilton cycle. Over the years this result has been generalized in many interesting ways. In this talk, I will give an overview of these efforts and then explore some of the more recent developments.

### Induced Ramsey numbers for a star versus a fixed graph

Series
Graph Theory Seminar
Time
Tuesday, March 2, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Maria AxenovichKarlsruhe Institute of Technology

We write $F \rightarrow (H,G)$ for graphs $F$, $G$, and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let the induced Ramsey number $IR(H,G)$ be the smallest number of vertices in a graph $F$ such that $F \rightarrow (H,G)$. Deuber showed in 1975 that $IR(H,G)$ is well-defined for any graphs $H$ and $G$. Still, the determination of $IR(H,G)$ remains a challenge for most graphs. A striking contrast between induced and non-induced Ramsey numbers was demonstrated by Fox and Sudakov in 2008 by showing that $IR(H,G)$ is superlinear in $n$ when $H$ is a matching on $n$ edges and $G$ is a star on $n$ edges.

In this talk, I will address the case when $G= K_{1,n}$, a star on $n$ edges, for large $n$, and $H$ is a fixed graph. We prove that $$(\chi(H)-1) n \leq IR(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$, sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.

This is a joint work with Izolda Gorgol.

### Constructing minimally 3-connected graphs

Series
Graph Theory Seminar
Time
Tuesday, February 23, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex of degree at least 4. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G'$ from the cycles of $G$, where $G'$ is obtained from $G$ by one of the two operations above.  We eliminate isomorphic duplicates using certificates generated by McKay's isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with $n$ vertices and $m$ edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges. In this talk I will focus primarily on the theorems behind the algorithm. This is joint work with Joao Costalonga and Robert Kingan.