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.

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.

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.

TBD

---

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

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.

The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$.

We propose a kernel-based estimator to predict the mean response trajectory for sparse and irregularly measured longitudinal data. The kernel estimator is constructed by imposing weights based on the subject-wise similarity on L2 metric space between predictor trajectories, where we assume that an analogous fashion in predictor trajectories over time would result in a similar trend in the response trajectory among subjects. In order to deal with the curse of dimensionality caused by the multiple predictors, we propose an appealing multiplicative model with multivariate Gaussian kernels. This model is capable of achieving dimension reduction as well as selecting functional covariates with predictive significance. The asymptotic properties of the proposed nonparametric estimator are investigated under mild regularity conditions. We illustrate the robustness and flexibility of our proposed method via the simulation study and an application to Framingham Heart Study

Stochasticity in gene expression is an important source of cell-to-cell variability (or noise) in clonal cell populations. So far, this phenomenon has been studied using the Gillespie Algorithm, or the Chemical Master Equation, which implicitly assumes that cells are independent and do neither grow nor divide. This talk will discuss recent developments in modelling populations of growing and dividing cells through agent-based approaches. I will show how the lineage structure affects gene expression noise over time, which leads to a straightforward interpretation of cell-to-cell variability in population snapshots. I will also illustrate how cell cycle variability shapes extrinsic noise across lineage trees. Finally, I outline how to construct effective chemical master equation models based on dilution reactions and extrinsic variability that provide surprisingly accurate approximations of the noise statistics across growing populations. The results highlight that it is crucial to consider cell growth and division when quantifying cellular noise.

---

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

We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also optimal up to the constant hidden in the $O(.)$ notation, and resolves a conjecture of Verstraëte. Joint work with Benny Sudakov and Istvan Tomon.

TBD

---

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

Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n, thus answering a question of Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhar and by Falgas-Ravry, Kittipassorn, Korandi, Letzter, and Narayanan. Our proof is elementary and self-contained.

The Ramsey number $R(k)$ is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices contains a monochromatic copy of $K_k$. It has been known since the work of Erdős and Szekeres in 1935, and Erdős in 1947, that $2^{k/2} < R(k) < 4^k$, but in the decades since the only improvements have been by lower order terms. In this talk I will sketch the proof of a very recent result, which improves the upper bound of Erdős and Szekeres by a (small) exponential factor. Based on joint work with Marcelo Campos, Simon Griffiths and Julian Sahasrabudhe.