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.

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.

Since the introduction of cluster algebras by Fomin and Zelevinsky in 2002, there has been significant interest in cluster algebras of surface type. These algebras are particularly noteworthy due to their ability to construct various combinatorial structures like snake graphs, T-paths, and posets, which are useful for proving key structural properties such as positivity or the existence of bases. In this talk, we will begin by presenting a cluster expansion formula that integrates the work of Musiker, Schiffler, and Williams with contributions from Wilson, utilizing poset representatives for arcs on triangulated surfaces. Using these posets and the expansion formula as tools, we will demonstrate skein relations, which resolve intersections or incompatibilities between arcs. Topologically, a skein relation replaces intersecting arcs or arcs with self-intersections with two sets of arcs that avoid the intersection differently. Additionally, we will show that all skein relations on punctured surfaces include a term that is not divisible by any coefficient variable. Consequently, we will see that the bangles and bracelets form spanning sets and exhibit linear independence. This work is done in collaboration with Esther Banaian and Elizabeth Kelley.

In this talk, we will discuss the paper, “Computational screen for sex-specific drug effects in a cardiac fibroblast signaling network model”, by K.M. Watts, W. Nichols and W.J. Richardson, Scientific Reports, 2023. Abstract Heart disease is the leading cause of death in both men and women. Cardiac fibrosis is the uncontrolled accumulation of extracellular matrix proteins, which can exacerbate the progression of heart failure, and there are currently no drugs approved specifically to target matrix accumulation in the heart. Computational signaling network models (SNMs) can be used to facilitate discovery of novel drug targets. However, the vast majority of SNMs are not sex-specific and/or are developed and validated using data skewed towards male in vitro and in vivo samples. Biological sex is an important consideration in cardiovascular health and drug development. In this study, we integrate a cardiac fibroblast SNM with estrogen signaling pathways to create sex-specific SNMs. The sex-specific SNMs demonstrated high validation accuracy compared to in vitro experimental studies in the literature while also elucidating how estrogen signaling can modulate the effect of fibrotic cytokines via multi-pathway interactions. Further, perturbation analysis and drug screening uncovered several drug compounds predicted to generate divergent fibrotic responses in male vs. female conditions, which warrant further study in the pursuit of sex-specific treatment recommendations for cardiac fibrosis. Future model development and validation will require more generation of sex-specific data to further enhance modeling capabilities for clinically relevant sex-specific predictions of cardiac fibrosis and treatment.

We provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs defined by polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs associated with Diophantine tuples and their generalizations from number theory. As an application, we provide new lower bounds on the clique number and independence number of general quasi-random graphs. In particular, we give a sufficient condition for the clique number of quasi-random graphs of order $n$ to be at least $(1-o(1))\log_{3.008}n$. Such a condition applies to many classical quasi-random graphs, including Paley graphs and Paley sum graphs, as well as some new Paley-like graphs we construct. If time permits, we also discuss some problems of diophantine tuples arising from number theory, which is our original motivation. This is joint work with Seoyoung Kim and Chi Hoi Yip.

In this talk, we discuss the paper, “Powerful and accurate detection of temporal gene expression patterns from multi-sample multi-stage single-cell transcriptomics data with TDEseq” by Y. Fan, L. Li and S. Sun, Genome Biology, 2024. Abstract We present a non-parametric statistical method called TDEseq that takes full advantage of smoothing splines basis functions to account for the dependence of multiple time points in scRNA-seq studies, and uses hierarchical structure linear additive mixed models to model the correlated cells within an individual. As a result, TDEseq demonstrates powerful performance in identifying four potential temporal expression patterns within a specific cell type. Extensive simulation studies and the analysis of four published scRNA-seq datasets show that TDEseq can produce well-calibrated p-values and up to 20% power gain over the existing methods for detecting temporal gene expression patterns. 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.

We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth at least t. This is joint work with Sepher Hajebi and Sophie Spirkl.

"CausalXtract: a flexible pipeline to extract causal effects from live-cell time-lapse imaging data”, by Franck Simon et.al., bioRxiv, 2024, will be discussed in the Journal Club. The abstract is the following : Live-cell microscopy routinely provides massive amount of time-lapse images of complex cellular systems under various physiological or therapeutic conditions. However, this wealth of data remains difficult to interpret in terms of causal effects. Here, we describe CausalXtract, a flexible computational pipeline that discovers causal and possibly time-lagged effects from morphodynamic features and cell-cell interactions in live-cell imaging data. CausalXtract methodology combines network-based and information-based frameworks, which is shown to discover causal effects overlooked by classical Granger and Schreiber causality approaches. We showcase the use of CausalXtract to uncover novel causal effects in a tumor-on-chip cellular ecosystem under therapeutically relevant conditions. In particular, we find that cancer associated fibroblasts directly inhibit cancer cell apoptosis, independently from anti-cancer treatment. CausalXtract uncovers also multiple antagonistic effects at different time delays. Hence, CausalXtract provides a unique computational tool to interpret live-cell imaging data for a range of fundamental and translational research applications. 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.

A vertex colouring of a hypergraph is $c$-strong if every edge $e$ sees at least $\min\{c, |e|\}$ distinct colours. Let $\chi(t,c)$ denote the least number of colours needed so that every $t$-intersecting hypergraph has a $c$-strong colouring. In 2012, Blais, Weinstein and Yoshida introduced this parameter and initiated study on when $\chi(t,c)$ is finite: they showed that $\chi(t,c)$ is finite whenever $t \geq c$ and unbounded when $t\leq c-2$. The boundary case $\chi(c-1, c)$ has remained elusive for some time: $\chi(1,2)$ is known to be finite by an easy classical result, and $\chi(2,3)$ was shown to be finite by Chung and independently by Colucci and Gyárfás in 2013. In this talk, we present some recent work with Kevin Hendrey, Freddie Illingworth and Nina Kamčev in which we fill in this gap by showing that $\chi(c-1, c)$ is finite in general.