KAIST

The extremal number ${\rm ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [0,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, \frac{7}{5}, 2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$.

We discuss some progress on the conjecture of Erdős and Simonovits. First, we show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

This is joint work with Jaehoon Kim and Hong Liu.

With the advent of large-scale data and the concurrent development of robust scientific tools to analyze them, important discoveries are being made in a wider range of scientific disciplines than ever before. A field of research that has gained substantial attention recently is the analytical, large-scale study of human behavior, where many analytical and statistical techniques are applied to various behavioral data from online social media, markets, and mobile communication, enabling meaningful strides in understanding the complex patterns of humans and their social actions.

The importance of such research originates from the social nature of humans, an essential human nature that clearly needs to be understood to ultimately understand ourselves. Another essential human nature is that they are creative beings, continually expressing inspirations or emotions in various physical forms such as a picture, sound, or writing. As we are successfully probing the social behaviors humans through science and novel data, it is natural and potentially enlightening to pursue an understanding of the creative nature of humans in an analogous way. Further, what makes such research even more potentially beneficial is that human creativity has always been in an interplay of mutual influence with the scientific and technological advances, being supplied with new tools and media for creation, and in return providing valuable scientific insights.

In this talk I will present two recent ongoing works on the mathematical analysis of color contrast in painting and measuring novelty in piano music.