# Department Seminars & Colloquia

2021-09
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4
5 6 7 1 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 1 29 30
2021-10
Sun Mon Tue Wed Thu Fri Sat
1 2
3 4 5 1 6 7 1 8 9
10 11 12 1 13 14 15 16
17 18 19 20 21 1 22 23
24 25 26 1 27 1 28 29 30
31

You can get notification if you subscribe the calendar in Google Calendar or iPhone calendar etc.

This talk will be presented online. Zoom link: 709 120 4849 (pw: 1234)
Host: Jae Kyoung Kim         To be announced     2021-10-05 14:19:57
Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$, which generalizes a graphic delta-matroid. For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid, which we call a $\Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$. This is joint work with Duksang Lee and Sang-il Oum.
Host: Sang-il Oum     English     2021-10-23 20:50:37
Within a given species, fluctuations in egg or embryo size is unavoidable. Despite this, the gene expression pattern and hence the embryonic structure often scale in proportion with the body length. This scaling phenomenon is very common in development and regeneration and has long fascinated scientists. I will first discuss a generic theoretical framework to show how scaling gene expression pattern can emerge from non-scaling morphogen gradients. I will then demonstrate that the Drosophila gap gene system achieves scaling in a way that is entirely consistent with our theory. Remarkably, a parameter-free model based on the theory quantitatively accounts for the gap gene expression pattern in nearly all morphogen mutants. Furthermore, the regulation logic and the coding/decoding strategy of the gap gene system can be revealed. Our work provides a general theoretical framework on a large class of problems where scaling output is induced by non-scaling input, as well as a unified understanding of scaling, mutants’ behavior and regulation in the Drosophila gap gene and related systems.
This talk will be presented online. Zoom link: 709 120 4849 (pw: 1234)
Host: Jae Kyoung Kim         To be announced     2021-10-05 14:18:47
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erd\H{o}s--R\'enyi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $\lambda' n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda'>0$.
Host: Sang-il Oum     English     2021-09-22 08:28:45
Immune sentinel cells must initiate the appropriate immune response upon sensing the presence of diverse pathogens or immune stimuli. To generate stimulus-specific gene expression responses, immune sentinel cells have evolved a temporal code in the dynamics of stimulus responsive transcription factors. I will present recent works 1) using an information theoretic approach to identify the codewords, termed “signaling codons”, 2) using a machine learning approach to characterize their reliability and points of confusion, and 3) dynamical systems modeling to characterize the molecular circuits that allow for their encoding. I will present progress on how the temporal code may be decoded to specify immune responses. Further, I will discuss to what extent such a code may be harnessed to achieve greater pharmacological specificity when therapeutically targeting pleiotropic signaling hubs. NFκB Signaling: information theory, signaling codons
This talk will be presented online. Zoom link: 709 120 4849 (pw: 1234)
Host: Jae Kyoung Kim         To be announced     2021-10-05 14:17:31
I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time $2^{O(\sqrt{k})}(n + m)$, where $n$ and $m$ denote the numbers of vertices and edges, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].
Host: Sang-il Oum     English     2021-09-22 08:25:36
The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, $c(H) = (1+o(1))\max (v(H)/2, v(H)-\alpha(H)),$ extending recent results of Haslegrave, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.
Host: Sang-il Oum     To be announced     2021-09-02 08:55:46
A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.