# 학과 세미나 및 콜로퀴엄

####
Room B332, IBS (기초과학연구원)
이산수학
Robert Hickingbotham (Monash University)
Powers of planar graphs, product structure, and blocking partitions

Room B332, IBS (기초과학연구원)

이산수학

Graph product structure theory describes complex graphs in terms of products of simpler graphs. In this talk, I will introduce this subject and talk about some of my recent results in this area. The focus of my talk will be on a new tool in graph product structure theory called `blocking partitions.’ I’ll show how this tool can be used to prove stronger product structure theorems for powers of planar graphs as well as k-planar graphs, resolving open problems of Dujmović, Morin and Wood, and Ossona de Mendez.

####
B378 Seminar room, IBS / ZOOM
수리생물학
Tetsuya J. Kobayashi (Institute of Industrial Science, the University of)
Optimality of Biological Information Processing

B378 Seminar room, IBS / ZOOM

수리생물학

Almost all biological systems possess the ability to gather environmental information and modulate their behaviors to adaptively respond to changing environments. While animals excel at sensing odors, even simple bacteria can detect faint chemicals using stochastic receptors. They then navigate towards or away from the chemical source by processing this sensed information through intracellular reaction systems.
In the first half of our talk, we demonstrate that the E. coli chemotactic system is optimally structured for sensing noisy signals and controlling taxis. We utilize filtering theory and optimal control theory to theoretically derive this optimal structure and compare it to the quantitatively verified biochemical model of chemotaxis.
In the latter half, we discuss the limitations of traditional information theory, filtering theory, and optimal control theory in analyzing biological systems. Notably, all biological systems, especially simpler ones, have constrained computational resources like memory size and energy, which influence optimal behaviors. Conventional theories don’t directly address these resource constraints, likely because they emerged during a period when computational resources were continually expanding. To address this gap, we introduce the “memory-limited partially observable optimal control,” a new theoretical framework developed by our group, and explore its relevance to biological problems.

ZOOM ID: 997 8258 4700 (Biomedical Mathematics Online Colloquium), (pw: 1234) + Google Map

ZOOM ID: 997 8258 4700 (Biomedical Mathematics Online Colloquium), (pw: 1234) + Google Map

####
Room B332, IBS (기초과학연구원)
이산수학
Matija Bucić (Princeton University)
Essentially tight bounds for rainbow cycles in proper edge-colourings

Room B332, IBS (기초과학연구원)

이산수학

An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of $(\log n)^{2+o(1)}$ for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the $o(1)$ term in Tomon's bound. We show that the answer to the question is equal to $(\log n)^{1+o(1)}$.
A key tool we use is the theory of robust sublinear expanders. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non-abelian groups.
Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.

####
Room B332, IBS (기초과학연구원)
이산수학
Domagoj Bradač (ETH Zürich)
Effective bounds for induced size-Ramsey numbers of cycles

Room B332, IBS (기초과학연구원)

이산수학

The k-color induced size-Ramsey number of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles these numbers are linear for any constant number of colours, i.e., for some C=C(k), there is a graph with at most Cn edges whose any k-edge-coloring contains a monochromatic induced cycle of length n. The value of C comes from the use of the sparse regularity lemma and has a tower-type dependence on k. In this work, we obtain nearly optimal bounds for the required value of C. Joint work with Nemanja Draganić and Benny Sudakov.

####
Room B332, IBS (기초과학연구원)
이산수학
Carl R. Yerger (Davidson College)
Solving Problems in Graph Pebbling using Optimization and Structural Techniques

Room B332, IBS (기초과학연구원)

이산수학

Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration of pebbles, at least one pebble can be moved to a specified target vertex.
In this talk, we will give a survey of several streams of research in pebbling, including describing a theoretical and computational framework that uses mixed-integer linear programming to obtain bounds for the pebbling numbers of graphs. We will also discuss improvements to this framework through the use of newly proved weight functions that strengthen the weight function technique of Hurlbert. Finally, we will discuss some open extremal problems in pebbling, specifically related to Class 0 graphs and describe how structural graph theoretic techniques such as discharging can be used to obtain results.
Collaborators on these projects include Dan Cranson, Dominic Flocco, Luke Postle, Jonad Pulaj, Chenxiao Xue, Marshall Yang, Daniel Zhou.

####
B378 Seminar room, IBS
수리생물학
Eui Min Jeong (KAIST)
Noise properties of adaptation-conferring biochemical control modules

B378 Seminar room, IBS

수리생물학

A key goal of synthetic biology is to establish functional biochemical modules with network-independent properties. Antithetic integral feedback (AIF) is a recently developed control module in which two control species perfectly annihilate each other’s biological activity. The AIF module confers robust perfect adaptation to the steady-state average level of a controlled intracellular component when subjected to sustained perturbations. Recent work has suggested that such robustness comes at the unavoidable price of increased stochastic fluctuations around average levels. We present theoretical results that support and quantify this trade-off for the commonly analyzed AIF variant in the idealized limit with perfect annihilation. However, we also show that this trade-off is a singular limit of the control module: Even minute deviations from perfect adaptation allow systems to achieve effective noise suppression as long as cells can pay the corresponding energetic cost. We further show that a variant of the AIF control module can achieve significant noise suppression even in the idealized limit with perfect adaptation. This atypical configuration may thus be preferable in synthetic biology applications.

####
B378 Seminar room, IBS
수리생물학
Sebastian Walcher (Mathematik A, RWTH Aachen, Germany)
Reaction networks: Reduction of dimension and critical parameters

B378 Seminar room, IBS

수리생물학

Typically, the mathematical description of reaction networks involves a system of parameter-dependent ordinary differential equations. Generally, one is interested in the qualitative and quantitative behavior of solutions in various parameter regions. In applications, identifying the reaction parameters is a fundamental task. Reduction of dimension is desirable from a practical perspective, and even necessary when different timescales are present. For biochemical reaction networks, a classical reduction technique assumes quasi-steady state (QSS) of certain species. From a general mathematical perspective, singular perturbation theory – involving a small parameter – is often invoked. The talk is mathematically oriented. The following points will be discussed: Singular perturbation reduction in general coordinates. (“How does one compute reductions?”) Critical parameters for singular perturbations. (“How does one find small parameters?”) Quasi-steady state and singular perturbations. (“What is applicable, what is correct?”)

Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$, and we say such an even delta-matroid is representable over the field $K$. Interestingly, a matroid is representable over $K$ in the usual manner if and only if it is representable over $K$ in the sense of even delta-matroids. The representability of matroids got much interest and was extensively studied such as excluded minors and representability over more than one field. Recently, Baker and Bowler (2019) integrated the notions of $K$-representable matroids, oriented matroids, and valuated matroids using tracts that are commutative ring-like structures in which the sum of two elements may output no element or two or more elements.
We generalize Baker-Bowler's theory of matroids with coefficients in tracts to orthogonal matroids that are equivalent to even delta-matroids. We define orthogonal matroids with coefficients in tracts in terms of Wick functions, orthogonal signatures, circuit sets, and orthogonal vector sets, and establish basic properties on functoriality, duality, and minors. Our cryptomorphic definitions of orthogonal matroids over tracts provide proofs of several representation theorems for orthogonal matroids. In particular, we give a new proof that an orthogonal matroid is regular (i.e., representable over all fields) if and only if it is representable over $\mathbb{F}_2$ and $\mathbb{F}_3$, which was originally shown by Geelen (1996), and we prove that an orthogonal matroid is representable over the sixth-root-of-unity partial field if and only if it is representable over $\mathbb{F}_3$ and $\mathbb{F}_4$.
This is joint work with Tong Jin.

####
B378 Seminar room, IBS
수리생물학
Dongju Lim (KAIST)
Unveiling Bias in Sequential Decision Making: A Causal Inference Approach for Stochastic Service Systems

B378 Seminar room, IBS

수리생물학

In many stochastic service systems, decision-makers find themselves making a sequence of decisions, with the number of decisions being unpredictable. To enhance these decisions, it is crucial to uncover the causal impact these decisions have through careful analysis of observational data from the system. However, these decisions are not made independently, as they are shaped by previous decisions and outcomes. This phenomenon is called sequential bias and violates a key assumption in causal inference that one person’s decision does not interfere with the potential outcomes of another. To address this issue, we establish a connection between sequential bias and the subfield of causal inference known as dynamic treatment regimes. We expand these frameworks to account for the random number of decisions by modeling the decision-making process as a marked point process. Consequently, we can define and identify causal effects to quantify sequential bias. Moreover, we propose estimators and explore their properties, including double robustness and semiparametric efficiency. In a case study of 27,831 encounters with a large academic emergency department, we use our approach to demonstrate that the decision to route a patient to an area for low acuity patients has a significant impact on the care of future patients.

####
Room B332, IBS (기초과학연구원)
이산수학
김석진 (건국대)
The square of every subcubic planar graph of girth at least 6 is 7-choosable

Room B332, IBS (기초과학연구원)

이산수학

The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner's conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) = 3$, at most $\Delta(G)+5$ if $4 \leq \Delta(G) \leq 7$, and at most $\lfloor \frac{3 \Delta(G)}{2} \rfloor$ if $\Delta(G) \geq 8$. Wegner's conjecture is still wide open. The only case for which we know tight bound is when $\Delta(G) = 3$. Thomassen (2018) showed that $\chi(G^2) \leq 7$ if $G$ is a planar graph with $\Delta(G) = 3$, which implies that Wegner's conjecture is true for $\Delta(G) = 3$. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph, where $\chi_{\ell}(G^2)$ is the list chromatic number of $G^2$. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6. This is joint work with Xiaopan Lian (Nankai University).

####
B378 Seminar room, IBS
수리생물학
Abbas Abbasli (KAIST)
Assumptions on decision making and environment can yield multiple steady states in microbial community models

B378 Seminar room, IBS

수리생물학

Background
Microbial community simulations using genome scale metabolic networks (GSMs) are relevant for many application areas, such as the analysis of the human microbiome. Such simulations rely on assumptions about the culturing environment, affecting if the culture may reach a metabolically stationary state with constant microbial concentrations. They also require assumptions on decision making by the microbes: metabolic strategies can be in the interest of individual community members or of the whole community. However, the impact of such common assumptions on community simulation results has not been investigated systematically.
Results
Here, we investigate four combinations of assumptions, elucidate how they are applied in literature, provide novel mathematical formulations for their simulation, and show how the resulting predictions differ qualitatively. Our results stress that different assumption combinations give qualitatively different predictions on microbial coexistence by differential substrate utilization. This fundamental mechanism is critically under explored in the steady state GSM literature with its strong focus on coexistence states due to crossfeeding (division of labor). Furthermore, investigating a realistic synthetic community, where the two involved strains exhibit no growth in isolation, but grow as a community, we predict multiple modes of cooperation, even without an explicit cooperation mechanism.
Conclusions
Steady state GSM modelling of microbial communities relies both on assumed decision making principles and environmental assumptions. In principle, dynamic flux balance analysis addresses both. In practice, our methods that address the steady state directly may be preferable, especially if the community is expected to display multiple steady states.

####
B378 Seminar room, IBS
수리생물학
Jonathan Rubin (University of Pittsburgh)
Multiple timescale modeling for neural systems

B378 Seminar room, IBS

수리생물학

Mathematical models of biological systems, including neurons, often feature components that evolve on very different timescales. Mathematical analysis of these multi-timescale systems can be greatly simplified by partitioning them into subsystems that evolve on different time scales. The subsystems are then analyzed semi-independently, using a technique called fast-slow analysis. I will briefly describe the fast-slow analysis technique and its application to neuronal bursting oscillations and basic coupled neuron modeling. After this, I will discuss fancier forms of dynamics such as canard oscillations, mixed-mode oscillations, and three-timescale dynamics. Although these examples all involve neural systems, the methods can and have been applied to other biological, chemical, and physical systems.

Pluripotential theory, namely positive closed and positive ddc-closed currents,
is a fundamental tool in the theory of iteration of holomorphic maps and the theory of foliations.
We will start with a crash course on positive closed and positive ddc-closed currents focusing on
some recent progress of the pluripotential theory. We then discuss applications in complex dynamics.
We will explain how the pluripotential theory allows to obtain equidistribution results, the unique
ergodicity or other fine statistical properties. (2 of 2)

####
Room B332, IBS (기초과학연구원)
이산수학
Sebastian Wiederrecht (IBS 이산수학그룹)
Delineating half-integrality of the Erdős-Pósa property for minors

Room B332, IBS (기초과학연구원)

이산수학

In 1986, Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minor if and only if it is planar. In particular, for every non-planar graph $H$ they gave examples showing that the Erdős-Pósa property does not hold for $H$. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors.
In this talk, we start the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph $H$ there exists a finite family $\mathfrak{F}_H$ of parametric graphs such that $H$ has the Erdős-Pósa property in a minor-closed graph class $\mathcal{G}$ if and only if $\mathcal{G}$ excludes a minor of each of the parametric graphs in $\mathfrak{F}_H$. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\in\mathcal{H}$ the family $\mathfrak{F}_H$ can be chosen to be precisely the two families of Robertson-Seymour counterexamples to the Erdős-Pósa property of $H$.

Pluripotential theory, namely positive closed and positive ddc-closed currents,
is a fundamental tool in the theory of iteration of holomorphic maps and the theory of foliations.
We will start with a crash course on positive closed and positive ddc-closed currents focusing on
some recent progress of the pluripotential theory. We then discuss applications in complex dynamics.
We will explain how the pluripotential theory allows to obtain equidistribution results, the unique
ergodicity or other fine statistical properties.
(1 of 2)

####
B378 Seminar room, IBS
수리생물학
Hyeongjun Jang (KAIST)
Generalized Michaelis–Menten rate law with time-varying molecular concentrations

B378 Seminar room, IBS

수리생물학

The Michaelis–Menten (MM) rate law has been the dominant paradigm of modeling biochemical rate processes for over a century with applications in biochemistry, biophysics, cell biology, and chemical engineering. The MM rate law and its remedied form stand on the assumption that the concentration of the complex of interacting molecules, at each moment, approaches an equilibrium much faster than the molecular concentrations change. Yet, this assumption is not always justified. Here, we relax this quasi-steady state requirement and propose the generalized MM rate law for the interactions of molecules with active concentration changes over time. Our approach for time-varying molecular concentrations, termed the effective time-delay scheme (ETS), is based on rigorously estimated time-delay effects in molecular complex formation. With particularly marked improvements in protein– protein and protein–DNA interaction modeling, the ETS provides an analytical framework to interpret and predict rich transient or rhythmic dynamics (such as autogenously-regulated cellular adaptation and circadian protein turnover), which goes beyond the quasi-steady state assumption.