Umeå University's logo

The celebrated Kővári-Sós-Turán theorem states that any n-vertex graph containing no copy of the complete bipartite graph Ks,s has at most Os(n2−1/s) edges. In the past two decades, motivated by the applications in discrete geometry and structural graph theory, a number of results demonstrated that this bound can be greatly improved if the graph satisfies certain structural restrictions. We propose the systematic study of this phenomenon, and state the conjecture that if H is a bipartite graph, then an induced H-free and Ks,s-free graph cannot have much more edges than an H-free graph. We provide evidence for this conjecture by considering trees, cycles, the cube graph, and bipartite graphs with degrees bounded by k on one side, obtaining in all the cases similar bounds as in the non-induced setting. Our results also have applications to the Erdős-Hajnal conjecture, the problem of finding induced C4-free subgraphs with large degree and bounding the average degree of Ks,s-free graphs which do not contain induced subdivisions of a fixed graph.

A simple probabilistic argument shows that every r-uniform hypergraph with m edges contains an r-partite subhypergraph with at least (r!/{rr)m edges. The celebrated result of Edwards states that in the case of graphs, that is r=2, the resulting bound m/2 can be improved to m/2+\Ω(m1/2), and this is sharp. We prove that if r\≥ 3, then there is an r-partite subhypergraph with at least (r/rr) m+m3/5-o(1) edges. Moreover, if the hypergraph is linear, this can be improved to (r!/rr) m+m3/4-o(1), which is tight up to the o(1) term. These improve results of Conlon, Fox, Kwan and Sudakov. Our proof is based on a combination of probabilistic, combinatorial, and linear algebraic techniques, and semidefinite programming. A key part of our argument is relating the energy E(G) of a graph G (i.e. the sum of absolute values of eigenvalues of the adjacency matrix) to its maximum cut. We prove that every m edge multigraph G has a cut of size at least m/2+Ω(E(G) log m), which might be of independent interest.

Given an m×n binary matrix M with |M|=p·mn (where |M| denotes the number of 1 entries), define the discrepancy of M as disc(M)=maxX⊂[m],Y⊂[n]||M[X×Y]|-p|X|·|Y||. Using semidefinite programming and spectral techniques, we prove that if rank(M)≤r and p≤1/2, then (Formula presented.) We use this result to obtain a modest improvement of Lovett’s best known upper bound on the log-rank conjecture. We prove that any m×n binary matrix M of rank at most r contains an (m·2-O(r))×(n·2-O(r)) sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank r is at most O(r).

We prove that the number of symmetric chain decompositions of the Boolean lattice 2[n] is (2ne + o(n) )2n . Furthermore, the number of symmetric chain decompositions of the hypergrid [t]n is n(1−on(1))·tn

The goal of this paper is to show the existence (using probabilistic tools) of configurations of lines, boxes, and points with certain interesting combinatorial properties. (i) First, we construct a family of n lines in ℝ³ whose intersection graph is triangle-free of chromatic number Ω (n^1∕15). This improves the previously best known bound Ω (log log n) by Norin, and is also the first construction of a triangle-free intersection graph of simple geometric objects with polynomial chromatic number. (ii) Second, we construct a set of n points in ℝ^d, whose Delaunay graph with respect to axis-parallel boxes has independence number at most n⋅(log n)^{−(𝑑−1)∕2+o(1)}. This extends the planar case considered by Chen, Pach, Szegedy, and Tardos.

Given positive integers k≤ d and a finite field F, a set S⊂ F^d is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most c|F|^d-k . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (|F|^d-k) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid [n]^d⊂ R^d is Ω_d(n*d(d-k)/d-1) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in Rd assuming their incidence graph avoids the complete bipartite graph K_c,c for some large constant c= c(d) .

In 1993, Fishburn and Graham established the following qualitative extension of the classical Erdős–Szekeres theorem. If (Formula presented.) is sufficiently large with respect to (Formula presented.), then any (Formula presented.) real matrix contains an (Formula presented.) submatrix in which every row and every column is monotone. We prove that the smallest such (Formula presented.) is at most (Formula presented.), greatly improving the previously best known double-exponential upper bound of Bucić, Sudakov, and Tran, and matching the best known lower bound (Formula presented.) on an exponential scale. In particular, we prove the following surprisingly sharp transition in the asymmetric setting. On one hand, every (Formula presented.) matrix contains an (Formula presented.) submatrix, in which every row is monotone. On the other hand, there exist (Formula presented.) matrices containing no such submatrix.

We prove that the maximum number of edges in a 3-uniform linear hypergraph on $n$ vertices containing no 2-regular subhypergraph is $n<^>{1+o(1)}$. This resolves a conjecture of Dellamonica, Haxell, & Lstrok;uczak, Mubayi, Nagle, Person, R & ouml;dl, Schacht, and Verstra & euml;te. We use this result to show that the maximum number of edges in a $3$-uniform hypergraph on $n$ vertices containing no immersion of a closed surface is $n<^>{2+o(1)}$. Furthermore, we present results on the maximum number of edges in $k$-uniform linear hypergraphs containing no $r$-regular subhypergraph.

We present several results in extremal graph and hypergraph theory of topological nature. First, we show that if α > 0 and ℓ = Ω(1αlog 1α) is an odd integer, then every graph G with n vertices and at least n1+α edges contains an ℓ-subdivision of the complete graph Kt, where t = nΘ(α). Also, this remains true if in addition the edges of G are properly colored, and one wants to find a rainbow copy of such a subdivision. In the sparser regime, we show that properly edge colored graphs on n vertices with average degree (logn)2+o(1) contain rainbow cycles, while average degree (logn)6+o(1) guarantees rainbow subdivisions of Kt for any fixed t, thus improving recent results of Janzer and Jiang et al., respectively. Furthermore, we consider certain topological notions of cycles in pure simplicial complexes (uniform hypergraphs). We show that if G is a 2-dimensional pure simplicial complex (3-graph) with n 1-dimensional and at least n1+α 2-dimensional faces, then G contains a triangulation of the cylinder and the Möbius strip with O(1αlog 1α) vertices. We present generalizations of this for higher dimensional pure simplicial complexes as well. In order to prove these results, we consider certain (properly edge colored) graphs and hypergraphs G with strong expansion. We argue that if one randomly samples the vertices (and colors) of G with not too small probability, then many pairs of vertices are connected by a short path whose vertices (and colors) are from the sampled set, with high probability.

In this paper 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 d≥s contains a subgraph of average degree at least s on at most nd^-ss-2(logd)^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-2s+ε contains a subgraph of average degree at least s on O_ε,s(1) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraëte.