We give an overview of the interplay between structural graph theory, first-order logic, and parameterized complexity. We focus on introducing the subject. Time permitting, one particular topic will be the neighborhood complexity of monadically stable graph classes.
A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set, called the {\em ground set} of $M$, and $\mathcal{I}$ is a non-empty collection of subsets of $E$, called {\em independent sets} of $M$, such that (1) a subset of an independent set is independent; and (2) if $I$ and $J$ are independent sets with $|I| < |J|$, then exists $x \in J \backslash I$ such that $I \cup \{x\}$ is independent.
A graph $G$ gives rise to a matroid $M(G)$ where the ground set is $E(G)$ and a subset of $E(G)$ is independent if it spans a forest. Another example is a matroid that comes from a matrix over a field $F$: the ground set $E$ is the set of all columns and a subset of $E$ is independent if it is linearly independent over $F$.
Tutte's Wheel and Whirl Theorem and Seymour's Splitter Theorem are two well-known inductive tools for proving results for 3-connected graphs and matroids. In this talk, we will give a survey on induction theorems for various versions of 4-connected matroids and graphs.
Given graphs G and H and a positive integer q, an (H,q)-coloring of G is an edge-coloring in which each copy of H receives at least q colors. Erdős and Shelah raised the question of determining the minimum number of colors, f(G,H,q), which are required for an (H,q)-coloring of G. Determining f(K_n,K_p,2) for all n and p is equivalent to determining the classical multicolor Ramsey numbers. Recently, Mubayi and Joos introduced the use of a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the values of f(K_{n,n},C_4,3) and f(K_n,K_4,5). In this talk, we will show how to generalize their approach to give bounds on the generalized Ramsey numbers for several families of graphs. This is joint work with Deepak Bal, Patrick Bennett, and Shira Zerbib.
For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $\alpha(G-S)\geq \alpha(G)-\ell$ for every
$S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J.
Discrete Math. 36 (2022) 229--240] shows that every $(k,\ell)$-stable
graph $G$ satisfies $\alpha(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$.
In this talk, we first prove that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative. \\
This is joint work with Xiaonan Liu and Zhiyu Wang.
Many problems in rigidity theory and matrix completion boil down to finding a nice combinatorial description of some matroid supported on the edge set of a complete (bipartite) graph. In this talk, I will give many such examples. My goal is to convince you that a general theory of matroids supported on graphs is needed and to give you a sense of what that could look like.
Corrine Yap: The Ising model is a classical model originating in statistical physics; combinatorially it can be viewed as a probability distribution over 2-vertex-colorings of a graph. We will discuss a fixed-magnetization version—akin to fixing the number of, say, blue vertices in every coloring—and a natural Markov chain sampling algorithm called the Kawasaki dynamics. We show some surprising results regarding the existence and location of a fast/slow mixing threshold for these dynamics. (joint work with Aiya Kuchukova, Marcus Pappik, and Will Perkins)
Changxin Ding: For trees on a fixed number of vertices, the path and the star are two extreme cases. Many graph parameters attain its maximum at the star and its minimum at the path among these trees. A trivial example is the number of leaves. I will introduce more interesting examples in the mini talk.
Jing Yu: We show that all simple outerplanar graphs G with minimum degree at least 2 and positive Lin-Lu-Yau Ricci curvature on every edge have maximum degree at most 9. Furthermore, if G is maximally outerplanar, then G has at most 10 vertices. Both upper bounds are sharp.
For a graph $H$ and an $n$-vertex graph $G$, the $H$-bootstrap percolation process on $G$ is the process which starts with $G$ and, at every time step, adds any missing edges on the vertices of $G$ that complete a copy of $H$. This process eventually stabilises and we are interested in the extremal question raised by Bollob\'as, of determining the maximum \emph{running time} (number of time steps before stabilising) of this process, over all possible choices of $n$-vertex graph $G$. We initiate a systematic study of this parameter, denoted $M_H(n)$, and its dependence on properties of the graph $H$. In a series of works we determine the precise running time for cycles and asymptotic running time for several other important classes. In general, we study necessary and sufficient conditions on $H$ for fast, i.e. sublinear or linear $H$-bootstrap percolation, and in particular explore the relationship between running time and minimum vertex degree and connectivity. Furthermore we also obtain the running time of the process for typical $H$ and discover several graphs exhibiting surprising behavior. The talk represents joint work with David Fabian and Patrick Morris.
A graph is called k-critical if its chromatic number is k but any proper subgraph has chromatic number less than k. There have been extensive reseaches on k-critical graphs over the past decades, yet several basic problems remain widely open. One of such problems is to determine the maximum number of edges in an n-vertex k-critical graph. In this talk, we will discuss some recent results on extremal aspects of k-critical graphs, including improvments on the extremal number of edges/cliques/critical subgraphs in k-critical graphs. This is based on some joint works with Jun Gao, Cong Luo and Tianchi Yang.
The study of Ramsey properties of the binomial random graph G_{n,p} was initiated in the 80s by Frankl & Rödl and Łuczak, Ruciński & Voigt. In this area we are often interested in establishing what function f(n) governs G_{n,p} having a particular Ramsey-like property P or not, i.e. when p is sufficiently larger than f(n) then G_{n,p} a.a.s. has P and when p is sufficiently smaller than f(n) then G_{n,p} a.a.s. does not have P (the former we call a 1-statement, the latter a 0-statement). I will present recent results on this topic from two different papers.
In the first, we almost completely resolve an outstanding conjecture of Kohayakawa and Kreuter on asymmetric Ramsey properties. In particular, we reduce the 0-statement to a necessary colouring problem which we solve for almost all pairs of graphs. Joint work with Candy Bowtell and Robert Hancock.
In the second, we prove similar results concerning so-called anti- and constrained-Ramsey properties. In particular, we (essentially) completely resolve the outstanding parts of the problem of determining the threshold function for the constrained-Ramsey property, and we reduce the anti-Ramsey problem to a necessary colouring problem which we prove for a specific collection of graphs. Joint work with Natalie Behague, Robert Hancock, Shoham Letzter and Natasha Morrison.
