Program

■ January 4 (Saturday), Ewha Campus Complex (ECC) B321

10:00 – 10:50 Andrzej Grzesik, Jagiellonian University, Poland

11:00 – 11:50 Abhishek Methuku, IBS , Daejeon, South Korea

12:00 – 14:00 Lunch

14:00 – 14:50 Bernard Lidicky, Iowa State University, USA

15:00 – 15:50 Joonkyung Lee, University of Hamburg, Germany

15:50 – 16:20 Coffee break

16:20 – 17:10 Peter Pach, Budapest University of Technology and Economics, Hungary

18:00 – 20:00 Dinner

■ Talk information

Talk 1. The Turán number of blow-ups of trees (Andrzej Grzesik, Jagiellonian University, Poland)

Abstract:

A conjecture of Erdős from 1967 asserts that any graph on n vertices which does not contain a fixed r-degenerate bipartite graph F has at most Cn^{2−1/r} edges, where C is a constant depending only on F. We show that this bound holds for a large family of r-degenerate bipartite graphs, including all r-degenerate blow-ups of trees. Our results generalize many previously proven cases of the Erdős conjecture, including the related results of Furedi and Alon, Krivelevich and Sudakov. Joint work with Oliver Janzer and Zoltán Lóránt Nagy.

Talk 2. Bipartite Turán problems for ordered graphs (Abhishek Methuku, IBS , Daejeon, South Korea)

Abstract:

A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$.

A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $ex(n,A)<n^{2-\frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method.

Results about the extremal numbers of zero-one matrices translate into results about the Tur\'an numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of F\"uredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $\ex(n,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Istvan Tomon.

Talk 3. Decomposing graphs into edges and triangles (Bernard Lidicky, Iowa State University, USA)

Abstract:

We prove the following 30-year old conjecture of Gyori and Tuza: the edges of every $n$-vertex

graph $G$ can be decomposed into complete graphs $C_1,...,C_l$ of orders two and three such

that $|C_1|+\cdots+|C_l| \leq (1/2 + o(1))n^2$. This result implies the asymptotic version of the

old result of Erd\H{o}s, Goodman and Posa that asserts the existence of such a decomposition

with $l \leq n^2/4$. We also discuss removing $o(1)$ term sharpening the result and possible

extensions. The talk is based on joint works with Blumenthal, Kr\'al', Martins, Pehova, Pikhurko,

Pfender, Volec.

Talk 4. Convex graphon parameters and graph norms (Joonkyung Lee, University of Hamburg, Germany)

Abstract:

Sidorenko's conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K_{5,5}∖C_{10}. It was even unknown whether this graph possesses the strictly stronger, weakly norming property.

We take a step towards understanding the graph K_{5,5}∖C_{10} by proving that it is not weakly norming. More generally, we show that 'twisted' blow-ups of cycles, which include K_{5,5}∖C_{10} and C_{6}□K_{2}, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that K_{t,t} minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t>3.

Talk 5. On some questions about multiplicative bases (Peter Pach, Budapest University of Technology and Economics, Hungary)

Abstract:

We will discuss some problems about additive and multiplicative bases.