Department Seminars & Colloquia




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

When you're logged in, you can subscribe seminars via e-mail

We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming space and symmetric groups decays exponentially as their centers drift apart. To verify condition (iii), we prove some deviation inequalities `on the slice’ for functions with Lipschitz conditions. We then use these estimates on intersection volumes to obtain a sharp lower bound on list-decodability of random q-ary codes, confirming a conjecture of Li and Wootters [IEEE Trans. Inf. Theory 2021]; and improve sphere-covering bound from the 70s on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy [IEEE Trans. Inf. Theory 2004]. Our probabilistic point of view also offers a unified framework to obtain improvements on other sphere-covering bounds, giving conceptually simple and calculation-free proofs for q-ary codes, permutation codes, and spherical codes. This is joint work with Jaehoon Kim and Hong Liu.
Host: Sang-il Oum     English     2021-11-29 20:46:14
The independent domination number of a graph $G$, denoted $i(G)$, is the minimum size of an independent dominating set of $G$. In this talk, we prove a series of results regarding independent domination of graphs with bounded maximum degree. Let $G$ be a graph with maximum degree at most $k$ where $k \ge 1$. We prove that if $k = 4$, then $i(G) \le \frac{5}{9}|V(G)|$, which is tight. Generalizing this result and a result by Akbari et al., we suggest a conjecture on the upper bound of $i(G)$ for $k \ge 1$, which is tight if true. Let $G'$ be a connected $k$-regular graph that is not $K_{k, k}$ where $k\geq 3$. We prove that $i(G')\le \frac{k-1}{2k-1}|V(G')|$, which is tight for $k \in \{3, 4\}$, generalizing a result by Lam, Shiu, and Sun. This result also answers a question by Goddard et al. in the affirmative. In addition, we show that $\frac{i(G')}{\gamma(G')} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, \v Skrekovski, and Tepeh, where $\gamma(G')$ is the domination number of $G'$. Moreover, if we restrict $G'$ to be a cubic graph without $4$-cycles, then we prove that $i(G') \le \frac{4}{11}|V(G')|$, which improves a result by Abrishami and Henning. This talk is based on joint work with Ilkyoo Choi, Hyemin Kwon, and Boram Park.
Host: Sang-il Oum     English     2021-11-01 22:50:16
What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollob\'as and Thomason and independently by Koml\'os and Szemer\'edi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph with the almost same average degree, for example, one copy of $K_{d,d}$. In 2017, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact, they conjectured that for small enough $\varepsilon>0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6,(\log \log c_{\varepsilon}(G))^6\}$-term. As a corollary, for every graph $F$, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term. This is joint work with Jaehoon Kim, Youngjin Kim, and Hong Liu.
Host: Sang-il Oum     English     2021-11-22 14:28:40
Simple mathematical models have had remarkable successes in biology, framing how we understand a host of mechanisms and processes. However, with the advent of a host of new experimental technologies, the last ten years has seen an explosion in the amount and types of quantitative data now being generated. This sets a new challenge for the field – to develop, calibrate and analyse new models to interpret these data. In this talk I will use examples relating to intracellular transport and cell motility to showcase how quantitative comparisons between models and data can help tease apart subtle details of biological mechanisms.
This talk will be presented online. Zoom link: 709 120 4849 (pw: 1234)
The poset Ramsey number $R(Q_{m},Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of~$Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2},Q_{n})\le2n+2$. Recently, Lu and Thompson improved the upper bound to $\frac{5}{3}n+2$. In this paper, we solve this problem asymptotically by showing that $R(Q_{2},Q_{n})=n+O(n/\log n)$. Joint work with Dániel Grósz and Abhishek Methuku.
Host: 엄상일     English     2021-11-22 14:27:15
Abstract: From fertilization to birth, successful mammalian reproduction relies on interactions of elastic structures with a fluid environment. Sperm flagella must move through cervical mucus to the uterus and into the oviduct, where fertilization occurs. In fact, some sperm may adhere to oviductal epithelia, and must change their pattern of oscillation to escape. In addition, coordinated beating of oviductal cilia also drive the flow. Sperm-egg penetration, transport of the fertilized ovum from the oviduct to its implantation in the uterus and, indeed, birth itself are rich examples of elasto-hydrodynamic coupling. We will discuss successes and challenges in the mathematical and computational modeling of the biofluids of reproduction.
This talk will be presented online. Zoom link: 709 120 4849 (pw: 1234)
A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
Host: Sang-il Oum     English     2021-09-13 08:19:27
A family F of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from F has a common element, and moreover, no set can be added to F while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. This is joint work with Kevin Hendrey, Casey Tompkins, and Tuan Tran.
Host: Sang-il Oum     English     2021-10-27 16:30:10