Seminars and Colloquia Schedule

Induced Ramsey numbers for a star versus a fixed graph

Series
Graph Theory Seminar
Time
Tuesday, March 2, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Maria AxenovichKarlsruhe Institute of Technology

We write $F \rightarrow (H,G)$ for graphs $F$, $G$, and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let the induced Ramsey number $IR(H,G)$ be the smallest number of vertices in a graph $F$ such that $F \rightarrow (H,G)$. Deuber showed in 1975 that $IR(H,G)$ is well-defined for any graphs $H$ and $G$. Still, the determination of $IR(H,G)$ remains a challenge for most graphs. A striking contrast between induced and non-induced Ramsey numbers was demonstrated by Fox and Sudakov in 2008 by showing that $IR(H,G)$ is superlinear in $n$ when $H$ is a matching on $n$ edges and $G$ is a star on $n$ edges.

In this talk, I will address the case when $G= K_{1,n}$, a star on $n$ edges, for large $n$, and $H$ is a fixed graph. We prove that $$ (\chi(H)-1) n \leq IR(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$, sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.

This is a joint work with Izolda Gorgol.

Tautological Bundles of Matroids

Series
Algebra Seminar
Time
Wednesday, March 3, 2021 - 15:30 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Chris EurStanford University

Matroid theory has seen fruitful developments arising from different algebro-geometric approaches, such as the K-theory of Grassmannians and Chow rings of wonderful compactifications. However, these developments have remained somewhat disjoint. We introduce "tautological bundles of matroids" as a new geometric framework for studying matroids. We show that it unifies, recovers, and extends much of these recent developments including log-concavity statements, as well as answering some open conjectures. This is an on-going work with Andrew Berget, Hunter Spink, and Dennis Tseng.

BlueJeans link: https://bluejeans.com/569437095

Synchronization in Markov random networks

Series
CDSNS Colloquium
Time
Friday, March 5, 2021 - 13:00 for 1 hour (actually 50 minutes)
Location
Zoom (see add'l notes for link)
Speaker
Shirou WangU Alberta

Zoom link: https://zoom.us/j/97732215148?pwd=Z0FBNXNFSy9mRUx3UVk4alE4MlRHdz09

Many complex biological and physical networks are naturally subject to both random influences, i.e., extrinsic randomness, from their surrounding environment, and uncertainties, i.e., intrinsic noise, from their individuals. Among many interesting network dynamics, of particular importance is the synchronization property which is closely related to the network reliability especially in cellular bio-networks. It has been speculated that whereas extrinsic randomness may cause noise-induced synchronization, intrinsic noises can drive synchronized individuals apart. This talk presents an appropriate framework of (discrete-state and discrete time) Markov random networks to incorporate both extrinsic randomness and intrinsic noise into the rigorous study of such synchronization and desynchronization scenario.  By studying the asymptotics of the Markov perturbed stationary distributions, probabilistic characterizations of the alternating pattern between synchronization and desynchronization behaviors is given.  More precisely, it is shown that if a random network without intrinsic noise perturbation is synchronized, then after intrinsic noise perturbation high-probability synchronization and low-probability desynchronization can occur intermittently and alternatively in time, and moreover, both the probability of (de)synchronization and the proportion of time spent in (de)synchrony can be explicitly estimated.

Dynamics of movement in complex environments

Series
Mathematical Biology Seminar
Time
Friday, March 5, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Sarah OlsonWorcester Polytechnic Institute

In this talk, we will highlight two different types of movement in viscosity dominated environments: sperm navigation and centrosome clustering in dividing cells.  Sperm often interact with chemicals and other proteins in the fluid, changing force generation and emergent swimming trajectories. Recently developed computational methods and asymptotic analysis allow for insight into swimming efficiency and hydrodynamic interactions of swimmers in different fluid environments. We will also show how parameter estimation techniques can be utilized to infer fluid and/or swimmer properties. For the case of centrosome movement, we explore how cancer cells can cluster additional centrosomes and proceed through either a bipolar or multipolar division. The models focus on understanding centrosome movement during cell division, which is the result of complex interactions between stochastic microtubule dynamics and motor proteins in the viscous cytoplasm of the cell.

Meeting Link: https://gatech.bluejeans.com/348270750

Rotor-routing reachability is easy, chip-firing reachability is hard

Series
Combinatorics Seminar
Time
Friday, March 5, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Speaker
Lilla TóthmérészEötvös Loránd University

Chip-firing and rotor-routing are two well-studied examples of Abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a simple characterization of when a chip-and-rotor configuration is reachable from another one. For chip-firing, it has been known that the reachability problem is in P if we have a class of graphs whose period length is polynomial (for example, Eulerian digraphs). Here we show that in the general case, chip-firing reachability is hard in the sense that if the chip-firing reachability problem were in P for general digraphs, then the polynomial hierarchy would collapse to NP.

Talk based on https://arxiv.org/abs/2102.11970