On November 30 and December 2, 2020, Joonkyung Lee (이준경) from University College London gave two online talks on the Ramsey multiplicity and common graphs at the Discrete Math Seminar organized by Jaehoon Kim at KAIST. The titles of his talks are “On Ramsey multiplicity” and “On common graphs“.

(The photo above was taken earlier in his other seminar talk.)

A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdős, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s.

Despite its importance, the full classification of common graphs is still a wide open problem and has not seen much progress since the early 1990s. In this lecture, I will present some old and new techniques to prove whether a graph is common or not.

Ramsey’s theorem states that, for a fixed graph $H$, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey’s theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question, let the Ramsey multiplicity $M(H;n)$ be the minimum number of labelled copies of monochromatic $H$ over all 2-edge-colouring of $K_n$. We define the Ramsey multiplicity constant $C(H)$ is defined by $C(H):=\lim_{n\rightarrow\infty}\frac{M(H,n)}{n(n-1)\cdots(n-v+1)}$. I will discuss various bounds for C(H) that are known so far.

On October 21, 2020, Joonkyung Lee (이준경) from University College London gave a talk at the Discrete Math Seminar on norms defined from graphs motivated by Sidorenko’s conjecture and Gowers norms on extremal combinatorics, unifying two seemingly different concepts of real-norming graphs and complex-norming graphs. The title of his talk was “On graph norms for complex-valued functions“. Joonkyung Lee will stay at the IBS discrete mathematics group for several weeks from October 19.

For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $\|.\|_H$ (resp. there is $\alpha$ such that $\|.\|_{H,\alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. This generalises Gowers norms, a widely used tool in extremal combinatorics to quantify quasirandomness.

We unify these two seemingly different notions of graph norms in real- and complex-valued settings, by proving that $H$ is complex-norming if and only if it is real-norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $\alpha$ but obtain its existence and uniqueness, which may be of independent interest.

As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which answers the only question appeared in Hatami’s pioneering work in the area that remained untouched. This is joint work with Alexander Sidorenko.

For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm.

We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that ‘twisted’ blow-ups of cycles, which include $K_{5,5}\setminus C_{10}$ and $C_6\square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. Secondly, we prove that $\|.\|_{r(H)}$ is not uniformly convex nor uniformly smooth, provided that $H$ is weakly norming. This answers another question of Hatami, who estimated the modulus of convexity and smoothness of $\|.\|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe, Jan Hladký, and Bjarne Schülke.

Joonkyung Lee (이준경) from University of Hamburg gave a talk at Discrete Math Seminar on January 3, 2019. The title of his talk was “Sidorenko’s conjecture for blow-ups”. (This was the first talk at the room B232.)

A celebrated conjecture of Sidorenko and Erdős–Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.

Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up H_{A}^{p} formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.