"Phenotypic switching in gene regulatory networks", PNAS. (2014) will be discussed in this Journal Club. Noise in gene expression can lead to reversible phenotypic switching. Several experimental studies have shown that the abundance distributions of proteins in a population of isogenic cells may display multiple distinct maxima. Each of these maxima may be associated with a subpopulation of a particular phenotype, the quantification of which is important for understanding cellular decision-making. Here, we devise a methodology which allows us to quantify multimodal gene expression distributions and single-cell power spectra in gene regulatory networks. Extending the commonly used linear noise approximation, we rigorously show that, in the limit of slow promoter dynamics, these distributions can be systematically approximated as a mixture of Gaussian components in a wide class of networks. The resulting closed-form approximation provides a practical tool for studying complex nonlinear gene regulatory networks that have thus far been amenable only to stochastic simulation. We demonstrate the applicability of our approach in a number of genetic networks, uncovering previously unidentified dynamical characteristics associated with phenotypic switching. Specifically, we elucidate how the interplay of transcriptional and translational regulation can be exploited to control the multimodality of gene expression distributions in two-promoter networks. We demonstrate how phenotypic switching leads to birhythmical expression in a genetic oscillator, and to hysteresis in phenotypic induction, thus highlighting the ability of regulatory networks to retain memory. 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 say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to B if and only if A maps homomorphically to Γ(B). If this is the case Λ is called the left adjoint to Γ and Γ the right adjoint to Λ. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We shall present several recent advances in this direction including a new approach based on the notion of Datalog Program borrowed from logic.

"Pathspace Kalman Filters with Dynamic Process Uncertainty for Analyzing Time-course Data", ArXiv. (2023) will be discussed in this Journal Club. In this study, we obtain an exact time-dependent solution of the chemical master equation (CME) of an extension of the two-state telegraph model describing bursty or non-bursty protein expression in the presence of positive or negative autoregulation. Using the method of spectral decomposition, we show that the eigenfunctions of the generating function solution of the CME are Heun functions, while the eigenvalues can be determined by solving a continued fraction equation. Our solution generalizes and corrects a previous time-dependent solution for the CME of a gene circuit describing non-bursty protein expression in the presence of negative autoregulation [Ramos et al., Phys. Rev. E 83, 062902 (2011)]. In particular, we clarify that the eigenvalues are generally not real as previously claimed. We also investigate the relationship between different types of dynamic behavior and the type of feedback, the protein burst size, and the gene switching rate. 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 family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies of graphs in $\mathcal F$ within $G$ such that any vertex of $G$ is contained in at most 2, respectively at most 4, of these copies, or there exists a vertex set $A$ of size at most $f(k)$ such that $G - A$ contains no copies of graphs in $\mathcal F$. Very recently we showed that even dicycles have the quarter-integral Erdős-Pósa property [STOC'24] via the proof of a structure theorem for digraphs without large packings of even dicycles. In this talk we discuss our current effort to improve this approach towards the half-integral Erdős-Pósa property, which would be best possible, as even dicycles do not have the integral Erdős-Pósa property. Complementing the talk given by Sebastian Wiederrecht in this seminar regarding our initial result, we also shine a light on some of the particulars of the embedding we use in lieu of flatness and how this helps us to move even dicycles through the digraph. In the process of this, we highlight the parts of the proof that initially caused the result to be quarter-integral. (This is joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht.)

---

ZOOM ID: 997 8258 4700(pw: 1234)

In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉. In this talk, we prove that Aharoni’s conjecture holds up to an additive constant. Specifically, we show that for each fixed r, there exists a constant c such that if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most n/r+c. This is joint work with Patrick Hompe.

---

ZOOM ID: 997 8258 4700(pw: 1234)

A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. A cross-cap drawing of a graph G with g cross-caps can be used to represent an embedding of G on a non-orientable surface of genus g. Mohar conjectured that any triangulation of a non-orientable surface of genus g admits a cross-cap drawing with g cross-caps in which each edge of the triangulation enters each cross-cap at most once. Motivated by Mohar’s conjecture, Schaefer and Stefankovic provided an algorithm that computes a cross-cap drawing with a minimal number of cross-caps for a graph G such that each edge of the graph enters each cross-cap at most twice. In this talk, I will first outline a connection between cross-cap drawings and an algorithm coming from computational biology to compute the signed reversal distance between two permutations. This connection will then be leveraged to answer two computational problems on graphs embedded on surfaces. First, I show how to compute a “short” canonical decomposition for a non-orientable surface with a graph embedded on it. Such canonical decompositions were known for orientable surfaces, but the techniques used to compute them do not generalize to non-orientable surfaces due to their more complex nature. Second, I explain how to build a counter example to a stronger version of Mohar’s conjecture that is stated for pseudo-triangulations. This is joint work with Alfredo Hubard and Arnaud de Mesmay.

Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid is a pair $D=(V,\mathcal F)$ where $\mathcal F$ is a collection of subsets of V known as "feasible sets." (They can be thought of as generalizing the set of bases of a matroid, while relaxing the condition that all bases must have the same cardinality.) Like with matroids, an important class of delta-matroids are linear delta-matroids, where the feasible sets are represented via a skew-symmetric matrix. Prominent examples of linear delta-matroids include linear matroids and matching delta-matroids (where the latter are represented via the famous Tutte matrix). However, the study of algorithms over delta-matroids seems to have been much less developed than over matroids. In this talk, we review recent results on representations of and algorithms over linear delta-matroids. We first focus on classical polynomial-time aspects. We present a new (equivalent) representation of linear delta-matroids that is more suitable for algorithmic purposes, and we show that so-called delta-sums and unions of linear delta-matroids are linear. As a result, we get faster (randomized) algorithms for Linear Delta-matroid Parity and Linear Delta-matroid Intersection, improving results from Geelen et al. (2004). We then move on to parameterized complexity aspects of linear delta-matroids. We find that many results regarding linear matroids which have had applications in FPT algorithms and kernelization directly generalize to linear delta-matroids of bounded rank. On the other hand, unlike with matroids, there is a significant difference between the "rank" and "cardinality" parameters - the structure of bounded-cardinality feasible sets in a delta-matroid of unbounded rank is significantly harder to deal with than feasible sets in a bounded-rank delta-matroid.

---

ZOOM ID: 997 8258 4700(pw: 1234)

The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) - p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is a $d$-regular graph on $n$ vertices and $d = O(n^{1/9})$, then the positive discrepancy of $G$ is at least $c d^{1/2}n$ for some constant $c$. We extend this result by proving lower bounds for the positive discrepancy with average degree d when $d < (1/2 - \epsilon)n$. We prove that the same lower bound remains true when $d < n^(2/3)$, while in the ranges $n^{2/3} < d < n^{4/5}$ and $n^{4/5} < d < (1/2 - \epsilon)n$ we prove that the positive discrepancy is at least $n^2/d$ and $d^{1/4}n/log(n)$ respectively. Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when $d < n^{3/4}$, thus demonstrating a change in the behaviour around $d = n^{2/3}$ when a random graph no longer minimises the positive discrepancy. As a by-product, we also present lower bounds for the second largest eigenvalue of a $d$-regular graph when $d < (1/2 - \epsilon)n$, thus extending the celebrated Alon-Boppana theorem. This is joint work with Benjamin Sudakov and István Tomon.

---

ZOOM ID: 997 8258 4700(pw: 1234)

Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs $\ell$ and $k$. We precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$. This is joint work with Ervin Győri, Binlong Li, Nika Salia, Kitti Varga and Manran Zhu.