Heidelberg University, Germany
MSK, UTC +3
Joint work with Mateusz Górski
The generalized Turán problem asks for the largest number of copies of a graph $H$ in an $n$-vertex graph not containing a graph $F$ as a subgraph. In the talk we will discuss this problem in the case when both $H$ and $F$ are cycles by presenting known bounds and recent developments. In particular, we will sketch the proof providing the first exact solution for the generalized Turán problem for cycles in the sparse setting.
MSK, UTC +3
Katona and Kierstead initiated the research on degree conditions guaranteeing the existence of Hamilton cycles in hypergraphs. Subsequently, Rödl, Ruciński, and Szemerédi showed an analogue of Dirac's theorem, namely that for large $n$, every $k$-uniform hypergraph on $n$ vertices and with minimum $(k-1)$-degree at least $(1/2+o(1))n$ contains a Hamilton cycle.
In the recent years, together with my co-authors, I have made some further progress in this area.
Together with Polcyn, Reiher, and Rödl, I obtained the $k$-uniform analogue of Dirac's theorem for the $(k-2)$-degree (this was shown independently by Lang and Sanhueza-Matamala).
Further, I proved a $3$-uniform analogue of a result on Hamilton cycles in graphs due to Pósa.
In addition, together with Joos and Kühn, I showed certain decomposition and packing results.
For instance, for large $n$, every regular $k$-uniform hypergraph on $n$ vertices and with minimum $(k-1)$-degree at least $(1/2+o(1))n$ actually allows a decomposition into Hamilton cycles.
MSK, UTC +3
Let $s\ge2$ and $t\ge2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $\chi(G[S ]) \ge s$ and $\chi(G[T ]) \ge t$. The Erdős-Lovász Tihany Conjecture from 1968 states that every graph $G$ with $\omega(G) < \chi(G) = s + t - 1$ is $(s,t)$-splittable. In this talk we will survey the history of the Erdős-Lovász Tihany Conjecture and the main ideas of recent results.
MSK, UTC +3
This is a joint work with Yair Caro and Rafael Yuster.
A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let $s(H)$ be the smallest integer $N$ such that there is a sum-distinguishing labeling of $H$ with each label at most $N$. The largest value of $s(H)$ over all hypergraphs on $n$ vertices and $m$ hyperedges is denoted $s(n,m)$. We prove that $s(n,m)$ is almost-quadratic in $m$ as long as $m$ is not too large.
One application of our result is an answer to a question of Gyarfas et al. whether there are $n$-vertex hypergraphs with irregularity strength greater than $2n$. In fact we show that there are $n$-vertex hypergraphs with irregularity strength at least $n^{2-o(1)}$.
MSK, UTC +3
In 1987, Alon–Kleitman–Thomassen–Saks–Seymour showed that for every $k\in \mathbb N$, any graph with chromatic number $Ck^3$ must contain a subgraph which is $k$-connected and has chromatic number at least $k$. More recently, Chudnovsky–Penev–Scott–Trotignon were able to reduce the bound to $C'k^2$. In a joint paper with Narayanan, we were able to show that for each $k\in \mathbb N$, there exists an $f(k)\le 7k$ such that every graph $G$ with chromatic number at least $f(k) + 1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$, thus resolving a problem of Norin. It is easy to see this result is best-possible up to multiplicative constants.
MSK, UTC +3
The past decade has seen a flurry of activity on sparse analogues of the classical regularity method. The key difficulty in applying this method in a sparse context is to establish appropriate counting lemmas. In this talk, we will describe how such counting lemmas, though not true in general, can be salvaged in certain situations. In particular, we will discuss recent work with Fox, Sudakov and Zhao on counting lemmas relative to graphs with no 4-cycles and its many applications in extremal and additive combinatorics.
MSK, UTC +3
According to the crossing lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton (1981), the crossing number of any graph with $n$ vertices and $e>4n$ edges is at least $c\frac{e^3}{n^2}$, where $c>0$ is an absolute constant This result, which is tight up to the constant factor, has been successfully applied to a variety of problems in discrete and computational geometry, additive number theory, algebra, and elsewhere. The lemma easily extends to multigraphs: if the multiplicity of every edge is at most $m$, then the crossing number of the graph is at least $c\frac{e^3}{mn^2}$. However, much better bounds can be established for multigraphs in which no two parallel edges are homotopic.
We discuss a number of recent results of this kind, joint with Tardos and Tóth, and with Fox and Suk, respectively.
MSK, UTC +3
Joint work with Benny Sudakov
It is a central problem in graph theory to find explicit constructions of graphs with good Ramsey properties (that is, graphs containing only very small cliques and independent sets). One natural approach is to construct such graphs algebraically. We say that a graph is algebraic of complexity $(n,d,m)$ if its vertices are elements of an $n$ dimensional space over some field, and its edges are defined by the zero-patterns of $m$ polynomials of degree at most $d$. I will discuss the Ramsey properties of such graphs and talk about related results for algebraic hypergraphs as well.
MSK, UTC +3
Joint work with Dániel Gerbner
Alon and Shikhelman started the systematic investigation of the maximum number $ex(n,H,F)$ of copies of a graph $H$ that an $n$-vertex $F$-free graph may contain. In this talk, I will survey recent results on $ex(n,K_{a,b},K_{s,t})$ and $ex(n,K_t,B_{r,s})$, where $B_{r,s}$ denotes the graph consisting of two cliques of size $r$ sharing $s$ common vertices.
MSK, UTC +3
MSK, UTC +3
Joint work with Chaya Keller, Bruno Jartoux and Shakhar Smorodinsky.
The multicolor hypergraph Ramsey number $R_k(s,r)$ is the minimal $n$, such that in any $k$-coloring of all $r$-element subsets of $[n]$, there is a subset of size $s$, all whose r-subsets are monochromatic. We present a new "stepping-up lemma" for $R_k(s,r)$: If $R_k(s,r)>n$, then $R_{k+3}(s+1,r+1)>2^n$. Using the lemma, we improve some known lower bounds on multicolor hypergraph Ramsey numbers. Furthermore, given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of coloring all $r$-subsets of $V$ such that no hyperedge of size $>r$ is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $chi(H)$. In particular, we show that this number is $O(log^{(r-1)} (r \chi(H)) + r)$, where $log^{(m)}$ denotes $m$-fold logarithm.
MSK, UTC +3
It is not hard to see that any Chebyshev system of functions defines a convex curve in d-dimensional Euclidean space. In this talk we consider ф generalization of the sign changes Hurwitz theorem for convex curves in $\mathbb R^d$. The convex hull of any finite set of points on a convex curve is a polytope which is combinatorially equivalent to a cyclic polytope. We will consider a construction defining an alternative centrally symmetric polytope. Using this polytope, a proof of Ky Fan's theorem and its extension can be obtained directly from the Hopf degree theorem.
MSK, UTC +3
Joint mostly with Joseph Briggs
Given sets of edges in a hypergraph, a "rainbow matching" is a choice function from these sets, whose image consists of disjoint edges. I will tell about some tantalizing conjectures and some progress on some of them.
MSK, UTC +3
A Euclidean subset X is called an s-distance set if the number of distances between two distinct points in X is equal to s. An s-distance set with large size sometimes has a good combinatorial structure like association schemes. A major problem for s-distance sets is to determine the largest possible s-distance set for given s and dimension.
The dodecahedron conjecture is that the largest possible 5-distance set in 3-dimensional Euclidean space is the vertices of the regular dodecahedron, which was long standing open problem. In this talk, we introduce several results of s-distance sets relating algebraic combinatorics and show some properties for substructures of the regular dodecahedron to prove the dodecahedron conjecture. We also give only a sketch of the proof of the conjecture, the following speaker Dr. Shinohara will explain the main idea in detail.
MSK, UTC +3
A previous speaker Dr. Nozaki will introduce some problems for distance sets and the dodecahedron conjecture for distance sets. In this talk, we will give a proof of the conjecture in detail. In particular, we will introduce the diameter graphs of subsets of a 3-dimensional Euclidean space and discuss the independence numbers of diameter graphs.
MSK, UTC +3
Joint work with Alexander Barg and Maya Stoyanova
Upper and lower bounds on the sum of distances of a spherical code of size $N$ in $n$ dimensions when $N\sim n^\alpha$, $0 < \alpha \le 2$, are obtained by specializing recent general, universal bounds on energy of spherical sets. The asymptotic behavior of our bounds along with examples of codes whose sum of distances closely follows the upper bound are discussed.
MSK, UTC +3
I will talk about recent joint work with Henry Cohn, Abhinav Kumar, Stephen D. Miller, and Maryna Viazovska in which we prove that the E8 root lattice and the Leech lattice are universally optimal. I will also try to explain the main ingredient in the proof, a novel interpolation formula for Fourier eigenfunctions, and some open problems related to it.
MSK, UTC +3
MSK, UTC +3
Joint work with Jens Marklof
The three distance theorem states that, if x is any real number and N is any positive integer, the points x, 2x, … , Nx modulo 1 partition the unit interval into component intervals having at most 3 distinct lengths. We present a generalization of this problem for rotations on higher dimensional tori, and we explain how to reformulate it as a problem about lattices in Euclidean space. For the two-dimensional torus, we are able to prove a five distance theorem, which is best possible. In higher dimensions we do not know the best possible bounds. Determining them can be viewed as an extremal problem in discrete geometry. The best currently known bounds are given by the kissing number, but these are likely far from the truth.
MSK, UTC +3
In 1973 Stolarsky proved a remarkable identity relating the quadratic spherical cap discrepancy and the sum of Euclidean distances on the sphere. We shall discuss various extensions and generalizations of this interesting principle (including a recent very general form for compact spaces with invariant measures) as well as their applications to various problems in discrete geometry and optimal measures.
MSK, UTC +3
Joint work with H. Edelsbrunner
If a unit circle in the plane is approximated with a fine square grid, the perimeter of the approximation converges to 8, instead of the perimeter of the circle. We prove that the same ratio holds on average for any piecewise-smooth curve, and for any Delaunay mosaic instead of the square grid; and extend the result beyond two dimensions.
MSK, UTC +3
Joint work with Joonkyung Lee and Alexey Pokrovskiy
A family of graphs is said to be chi-bounded, if there is a function $f$ such that for every graph H in the family the chromatic number of $H$ is at most $f(w)$, where $w$ is the clique number of $H$. We show that the family of graphs that do not have a cycle with exactly $k$ chords is chi-bounded, for every large $k$. This proves a conjecture of Aboulker and Bousquet (2015).
MSK, UTC +3
Joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe
Let $A$ be drawn uniformly at random from the set of all $n \times n$ symmetric matrices with entries in $\{-1,1\}$. We show that the singularity probability of $A$ is exponentially small, thereby resolving a well-known conjecture.
MSK, UTC +3
Joint work with Robin Thomas
Linklessly embeddable graphs are 3-dimensional analogues of planar graphs which include apex planar graphs. While there is no known analogue of Euler's formula for linkless embeddings, a tight bound of $4n-10$ on the number of edges in linklessly embeddable graphs can be obtained from their excluded minor characterization and a theorem of Mader on the extremal functions for graphs with no $K_p$ minor for small $p$. We prove an analogue of Mader's theorem for triangle-free graphs, and also show that apex planar graphs satisfy the edge bound of $3n-9+\frac{t}{3}$, where $t$ is the number of triangles. This bound is conjectured to hold for all linklessly embeddable graphs.
MSK, UTC +3
Joint work with Jacob Fox.
The graph removal lemma, a fundamental result in extremal graph theory, says that if a large graph $G$ has "few" copies of a fixed graph $H$, then $G$ can be made $H$-free by deleting "few" edges. The statement is so simple that one might hope to prove it via a simple averaging argument, but this seems impossible—all known proofs use techniques related to Szemerédi's regularity lemma, and consequently yield very poor quantitative control.
Another important, and seemingly unrelated, topic of study in extremal graph theory is the structure of dense $H$-free graphs. It turns out that if one imposes an appropriate minimum degree condition on an $H$-free graph $G$, then its structure becomes extremely rigid. Moreover, there are two thresholds, called the chromatic and homomorphism thresholds, that determine this minimum degree condition: above the thresholds there is rigid structure, while below them there is unbounded complexity.
In this talk, I'll discuss a surprising connection between these disparate topics. We prove the existence of a minimum degree threshold for the removal lemma: above this threshold, the removal lemma has linear bounds and a simple proof through averaging arguments, while below the threshold, the behavior is essentially the same as it is in general graphs.
MSK, UTC +3
Joint work with Maxime Larcher, Anders Martinsson and Andreas Noever
In this talk I show a connection between heavy cycles and cycle decompositions. We prove that every directed Eulerian graph can be decomposed into at most O(n log Δ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott, and matching the best known upper bound from the undirected case. This also implies the existence of long cycles differing to the Erdős–Gallai bound for undirected graphs in only a log factor Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least 1, there exists a cycle with weight at least Ω(log log n/log n), thus resolving a question by Bollobás and Scott. Aditionally we discuss how our methods transfer to finding long directed paths.
MSK, UTC +3
In 1988, Erdős wrote about a problem he proposed with Nešetřil:
One could perhaps try to determine the smallest integer $h_t(\Delta)$ so that every $G$ of $h_t(\Delta)$ edges each vertex of which has degree $\le \Delta$ contains two edges so that the shortest path joining these edges has length $\ge t$ ... This problem seems to be interesting only if there is a nice expression for $h_t(\Delta)$.
This problem can be considered as the edge version of the famous (and hard) degree--diameter problem.
It was the inspiration for a series of research papers on variants of this problem, where one is mainly dealing with the case $t=2$. We will mention part of the history here that resulted in the strong edge colouring conjecture, which is still widely open.
At the end, we will look again to the initial inspirational question of all of this and say more about the cases where $t$ is at least $3$ and have a discussion about it.
MSK, UTC +3
Based on joint work with Tom Johnston, Alex Scott and Jane Tan
The graph reconstruction conjecture states that each graph G on at least 3 vertices can be reconstructed from the multiset of all induced subgraphs on n-1 vertices. Although this conjecture is notoriously difficult, it is easy to reconstruct some information about the graph, e.g. the degree sequence of G and whether G is connected. Moreover, some graphs with extra structure can be reconstructed, such as trees. We study a set-up with smaller induced subgraphs ('small cards'). We use a surprising algebraic tool and introduce several counting techniques.
MSK, UTC +3
MSK, UTC +3
We tie together two natural but, a priori, different themes. As a starting point consider Erdős and Simonovits's classical edge stability for an $(r + 1)$-chromatic graph $H$. This says that any $n$-vertex $H$-free graph with $(1 - 1/r + o(1))\binom{n}{2}$ edges is close to (within $o(n^2)$ edges of) $r$-partite. This is false if $1 - 1/r$ is replaced by any smaller constant. However, instead of insisting on many edges, what if we ask that the $n$-vertex graph has large minimum degree? This is the basic question of minimum degree stability: what constant $c$ guarantees that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ is close to $r$-partite? $c$ depends not just on chromatic number of $H$ but also on its finer structure.
Somewhat surprisingly, answering the minimum degree stability question requires understanding of locally colourable graphs -- graphs in which every neighbourhood has small chromatic number. These are generalisations of triangle-free graphs (in which every neighbourhood is an independent set). For triangle-free graphs there is a rich history of bounds on the chromatic number in terms of the minimum degree. The locally colourable case has some similarities but also striking differences.
MSK, UTC +3
Joint work with with Anita Liebenau (UNSW Sydney)
In 1981 Jackson showed that the diregular bipartite tournament (a complete balanced bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We give two approximate versions of this conjecture, and discuss some open problems in the area.
MSK, UTC +3
An automaton consists of a finite set of states and a collection of functions from the set of states to itself. An automaton is synchronizing if there is a word (that is, a sequence of functions) that maps all states onto the same state. Cerny's conjecture on the length of the shortest such word is one of the most famous open problems in automata theory.
We consider the closely related question of determining the minimum length of a word that maps some $k$ states onto a single state. For synchronizing automata, we have improved the upper bound on the minimum length of a word that sends some triple to a single state from $0.5n^2$ to $0.19n^2$. I will discuss this result and some related results, including a generalisation of this approach that leads to an improved bound on the length of a synchronizing word for 4 states and 5 states.
MSK, UTC +3
Random regular graphs are extensively studied, whose analysis typically involves highly nontrivial enumeration arguments, especially when the degree grows fast as the number of vertices grows. Kim and Vu made a conjecture in 2004 that the random regular graph can be well approximated by the random binomial random graphs, in the sense that it is possible to construct $G(n,d)$, $G(n,p_1)$ and $G(n,p_2)$, where $d\sim np_1\sim np_2$, in the same probability space so that with high probability $G(n,p_1)\subseteq G(n,d)\subseteq G(n,p_2)$. This is known as the sandwich conjecture. In this talk I will discuss some recent progress in this conjecture.
MSK, UTC +3
Joint work with Shagnik Das and Benny Sudakov.
Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have been studied extensively. Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. This talk will be about proving Ando's Conjecture for sufficiently large connected graphs.
MSK, UTC +3
This talk is based on joint work with Yinon Spinka
The number of independent sets in the hypercube $\{0,1\}^d$ was estimated precisely by Korshunov and Sapozhenko in the 1980s and recently refined by Jenssen and Perkins.
In this talk we will discuss new results on the number of independent sets in a random subgraph of the hypercube. The results extend to the hardcore model and to the antiferromagnetic Ising model.
MSK, UTC +3
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$.
This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p < \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $\lambda' n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda' > 0$.
MSK, UTC +3
Joint work with Andrey Kupavskii and Arsenii Sagdeev
For a subset $S$ of $R^d$ the chromatic number $\chi(S,R^n)$ is the minimum number of colours needed to colour all points of $R^n$ without a monochromatic isometric copy of $S$. In Euclidean Ramsey theory a set $S$ is called Ramsey, if $\chi(S,R^n)$ tends to infinity. Classifying Euclidean Ramsey sets is a very difficult open problem. Recently, Kupavskii and Sagdeev showed that if we replace the Euclidean norm with the max norm, then every set is Ramsey. In this talk, we discuss several related results. We find essentially tight bounds for the max-norm chromatic number for certain families of sets. We also discuss related results about covering the integers with translates of given sets, and in particular we prove a conjecture of Schmidt–Tuller.
MSK, UTC +3
Joint work with Dmitriy Zakharov
In theoretical computer science, a perfect $3$-hash code $A$ is a set of $n$-dimensional vectors with coordinates among $\left\{0,1,2\right\}$ and which have the property that for every $3$ distinct vectors $x,y,z$ in $A$ there exists at least a coordinate where the entries of the vectors are pairwise distinct (i.e. $x,y,z$ are “trifferent” in this coordinate). Determining how large can such a code be is an important and difficult problem, known as the Trifference Problem. In this talk, we will discuss some recent developments and reflect upon a few intriguing connections with some other famous problems in extremal combinatorics.
MSK, UTC +3
In a deductive game for two players, SF and PGOM, SF conceals an $n$-digit number $x=x_1,\ldots,x_n$ in base $q$, and PGOM, who knows $n$ and $q$, tries to identify $x$ by asking a number of questions, which are answered by SF. Each question is an $n$-digit number $y=y_1,\ldots,y_n$ in base $q$; each answer is the number of subscripts $i$ such that $x_i=y_i$. Moreover, we require PGOM send all the questions at once.
In this talk, I will show that the minimum number of questions required to determine $x$ is $\frac{(2+o_q(1))n}{\log_q n}$. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph. I will state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.
MSK, UTC +3
The Hoffman bound is a spectral bound on the independence number of a graph. More precisely, it is an upper bound on the size of an independent set of a graph in terms of the smallest eigenvalue of its normalized adjacency operator. The bound has found numerous applications in extremal combinatorics, in particular, thanks to the work Alon-Dinur-Friedgut-Sudakov. They exploit the following fact: if the Hoffman bound is sharp for a graph, it remains sharp for a tensor power of the graph. In joint work with Filmus and Lifshitz, we prove a generalization of the Hoffman bound for hypergraphs with a similar property: it remains sharp in a tensor power of a hypergraph. We apply the bound to several problems in extremal combinatorics: Frankl’s problem on extended triangles, Mantel’s Theorem, Frankl-Tokushige Theorem on Intersecting Families. Our proof of Mantel's Theorem was praised by Friedgut as probably the most complicated proof of the theorem known to him.
MSK, UTC +3
A spherical two-distance set is a set of unit vectors in $d$-dimensional Euclidean space such that the inner products between two distinct vectors assume only two values, say α and β. In this talk, I will connect the problem of determining the maximum size of a spherical two-distance set in $R^d$ to forbidden subgraph characterization of signed graphs with eigenvalues bounded from below.
Based on joint work with Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao, and work in progress with Alexandr Polyanskii.