Department Seminars & Colloquia




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

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

A loose cycle is a cyclic ordering of edges such that every two consecutive edges share exactly one vertex. A cycle is Hamilton if it spans all vertices. A codegree of a $k$-uniform hypergraph is the minimum nonnegative integer $t$ such that every subset of vertices of size $k-1$ is contained in $t$ distinct edges. We prove "robust" versions of Dirac-type theorems for Hamilton cycles and optimal matchings. Let $\mathcal{H}$ be a $k$-uniform hypergraph on $n$ vertices with $n \in (k-1)\mathbb{N}$ and codegree at least $n/(2k-2)$, and let $\mathcal{H}_p$ be a spanning subgraph of $\mathcal{H}$ such that each edge of $\mathcal{H}$ is included in $\mathcal{H}_p$ with probability $p$ independently at random. We prove that a.a.s. $\mathcal{H}_p$ contains a loose Hamilton cycle if $p = \Omega(n^{-k+1} \log n)$, which is asymptotically best possible. We also present similar results for Hamilton $\ell$-cycles for $\ell \geq 2$. Furthermore, we prove that if $\mathcal{H}$ is a $k$-uniform hypergraph on $n$ vertices with $n \notin k \mathbb{N}$ and codegree at least $\lfloor n/k \rfloor$, then a.a.s. $\mathcal{H}_p$ contains a matching of size $\lfloor n/k \rfloor$ if $p = \Omega(n^{-k+1} \log n)$. This is also asymptotically best possible. This is joint work with Michael Anastos, Debsoumya Chakraborti, Abhishek Methuku, and Vincent Pfenninger.
Host: Sang-il Oum     English     2023-07-02 18:56:05
In a rainbow variant of the Turán problem, we consider $k$ graphs on the same set of vertices and want to determine the smallest possible number of edges in each graph, which guarantees the existence of a copy of a given graph $F$ containing at most one edge from each graph. In other words, we treat each of the $k$ graphs as a graph in one of the $k$ colors and consider how many edges in each color force a rainbow copy of a given graph $F$. In the talk, we will describe known results on the topic, as well as present recent developments, obtained jointly with Sebastian Babiński and Magdalen Prorok, solving the rainbow Turán problem for a path on 4 vertices and a directed triangle with any number of colors.
Host: Sang-il Oum     English     2023-06-01 23:27:10
The well-known 1-2-3 Conjecture by Karoński, Łuczak and Thomason states that the edges of any connected graph with at least three vertices can be assigned weights 1, 2 or 3 so that for each edge $uv$ the sums of the weights at $u$ and at $v$ are distinct. The list version of the 1-2-3 Conjecture by Bartnicki, Grytczuk and Niwczyk states that the same holds if each edge $e$ has the choice of weights not necessarily from $\{1,2,3\}$, but from any set $\{x(e),y(e),z(e)\}$ of three real numbers. The goal of this talk is to survey developments on the 1-2-3 Conjecture, especially on the list version of the 1-2-3 Conjecture.
Host: Sang-il Oum     English     2023-05-28 08:27:34
A theoretical dynamical system is a pair (X,T) where X is a compact metric space and T is a self homeomorphism of X. The topological entropy of a theoretical dynamical system (X,T), first introduced in 1965 by Adler, Konheim and McAndrew, is a nonnegative real number that measures the complexity of the system. Systems with positive entropy are random in certain sense, and systems with zero entropy are said to be deterministic. To distinguish between deterministic systems, Huang and Ye (2009) introduced the concept of maximal pattern entropy of a theoretical dynamical system. At the heart of their argument is a Sauer-Shelah-type lemma. We will discuss this lemma and its surprising connection to a recent breakthrough in communication complexity. Joint work with Guorong Gao, Jie Ma, and Mingyuan Rong.
Host: Sang-il Oum     English     2023-06-27 14:49:54
Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. Given a graph $G$, its hat guessing number $HG(G)$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ possible colors. In 2008, Butler, Hajiaghayi, Kleinberg, and Leighton asked whether the hat guessing number of the complete bipartite graph $K_{n,n}$ is at least some fixed positive (fractional) power of $n$. We answer this question affirmatively, showing that for sufficiently large $n$, $HG(K_{n,n})\ge n^{0.5-o(1)}$. Our guessing strategy is based on some ideas from coding theory and probabilistic method. Based on a joint work with Noga Alon, Omri Ben-Eliezer, and Itzhak Tamo.
Host: Sang-il Oum     English     2023-06-01 23:28:59
An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in uniformly dense hypergraphs. In precise, we will mention the uniform Turan density of some hypergraphs.
Host: Sang-il Oum     To be announced     2023-06-12 10:08:41
A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its complement has $K_{m, m}$ as a subgraph where $m \geq \left\lfloor c|V(G)| \right\rfloor$. We prove that the class of chordal graphs satisfies SEH-property with constant $c = 2/9$. On the other hand, a strengthening of SEH-property which we call the colorful Erdős-Hajnal property was discussed in geometric settings by Alon et al.(2005) and by Fox et al.(2012). Inspired by their results, we show that for every pair $F_1, F_2$ of subtree families of the same size in a tree $T$ with $k$ leaves, there exist subfamilies $F'_1 \subseteq F_1$ and $F'_2 \subseteq F_2$ of size $\theta \left( \frac{\ln k}{k} \left| F_1 \right|\right)$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal. Joint work with Andreas Holmsen, Jinha Kim and Minki Kim.
Host: Sang-il Oum     English     2023-06-01 11:20:56
TBD
ZOOM ID: 997 8258 4700 (Biomedical Mathematics Online Colloquium), (pw: 1234)
Host: Jae Kyoung Kim     English     2023-03-06 17:08:05
To understand nonparametric regression, we should know first what the parametric model is. Simply speaking, the parametric regression model consists of many assumptions and the nonparametric regression model eases the assumptions. I will introduce what assumptions the parametric regression model has and how the nonparametric regression model relieves them. In addition, their pros and cons will be also presented.
Host: Jae Kyoung Kim     To be announced     2023-06-01 10:52:23