For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One of the most common ways to obtain an interesting family F is to fix another family H of graphs and let F be the set of graphs that do not contain any graph H as some notion of a subgraph, including (standard) subgraph, induced subgraph, and minor. This framework captures numerous basic graph problems, including Vertex Cover, Feedback Vertex Set, and Treewidth Deletion, and provides an interesting forum where ideas from approximation and parameterized algorithms influence each other. In this talk, I will give a brief survey on the state of the art on the F-Deletion Problems for the above three notions of subgraphs, and talk about a recent result on Weighted Bond Deletion.

Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and the theory of sparsity. In this talk, we will survey structural and algorithmic results that concern width and depth parameters of matroids. We will particularly focus on matroid depth parameters and discuss the relation of the presented concepts to discrete optimization. As an application, we will present matroid based algorithms that uncover a hidden Dantzig-Wolfe-like structure of an input instance (if such structure is present) and transform instances of integer programming to equivalent ones, which are amenable to the existing tools in integer programming. The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.

For the past few years, I’ve been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I’ll talk about what formalization looks like in practice from the perspective of a combinatorialist.

In some sense, matroids are generalisations of graphs. The idea of graph minors extends to matroids, and so does the idea of a minor-closed class. We can think of a minor-closed class of matroids as being an analogue to the class of graphs embeddable on a surface. Any such class of graphs has a corresponding class of minimal forbidden minors, and these forbidden minors characterise the class. A minor-closed class of matroids is characterised by its minimal forbidden minors in the same way. Rota’s conjecture is the most famous problem in matroid theory. It says that when F is a finite field, there is a finite number of minimal forbidden minors for the class of matroids that can be represented by vectors over the field of scalars F. A proof has been announced by Geelen, Gerards, and Whittle. Gain-graphic matroids are analogues to matroids represented by vectors: instead of representing the matroid using numbers from a field, we use elements from a group. So we can ask for an analogue of Rota’s conjecture, except for gain-graphic matroids. In this talk I will outline our intended path towards Rota’s conjecture for gain-graphic matroids. This is joint work with Daryl Funk.

Phenotypic selection occurs when genetically identical cells are subject to different reproductive abilities due to cellular noise. Such noise arises from fluctuations in reactions synthesizing proteins and plays a crucial role in how cells make decisions and respond to stress or drugs. We propose a general stochastic agent-based model for growing populations capturing the feedback between gene expression and cell division dynamics. We devise a finite state projection approach to analyze gene expression and division distributions and infer selection from single-cell data in mother machines and lineage trees. We use the theory to quantify selection in multi-stable gene expression networks and elucidate that the trade-off between phenotypic switching and selection enables robust decision-making essential for synthetic circuits and developmental lineage decisions. Using live-cell data, we demonstrate that combining theory and inference provides quantitative insights into bet-hedging–like response to DNA damage and adaptation during antibiotic exposure in Escherichia coli.

Stochastic models of gene expression are routinely used to explain large variability in measured mRNA levels between cells. These models typically predict the distribution of the total mRNA level per cell but ignore compartment-specific measurements which are becoming increasingly common. Here we construct a two-compartment model that describes promoter switching between active and inactive states, transcription of nuclear mRNA and its export to the cytoplasm where it decays. We obtain an analytical solution for the joint distribution of nuclear and cytoplasmic mRNA levels in steady-state conditions. Based on this solution, we build an efficient and accurate parameter inference method which is orders of magnitude faster than conventional methods. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H.$ In $1995,$ Kahn conjectured that if $H$ is a $d$-regular linear $k$-uniform hypergraph, the probability that $M$ does not cover $v$ is $(1 + o_d(1))d^{-1/k}$ for all vertices $v\in V(H)$. This conjecture was proved for $k = 2$ by Kahn and Kim in 1998. In this paper, we disprove this conjecture for all $k \geq 3.$ For infinitely many values of $d,$ we construct $d$-regular linear $k$-uniform hypergraph $H$ containing two vertices $v_1$ and $v_2$ such that $\mathcal{P}(v_1 \notin M) = 1 – \frac{(1 + o_d(1))}{d^{k-2}}$ and $\mathcal{P}(v_2 \notin M) = \frac{(1 + o_d(1))}{d+1}.$ The gap between $\mathcal{P}(v_1 \notin M)$ and $\mathcal{P}(v_2 \notin M)$ in this $H$ is best possible. In the course of proving this, we also prove a hypergraph analog of Godsil’s result on matching polynomials and paths in graphs, which is of independent interest.

Tropical geometry replaces usual addition and multiplication with tropical addition (the min) and tropical multiplication (the sum), which offers a polyhedral interpretation of algebraic variety. This talk aims to pitch the usefulness of tropical geometry in understanding classical algebraic geometry. As an example, we introduce the tropicalization of the variety of symmetric rank 2 matrices. We discuss that this tropicalization has a simplicial complex structure as the space of symmetric bicolored trees. As a result, we show that this space is shellable and delve into its matroidal structure. It is based on the joint work with May Cai and Josephine Yu.