Umeå University's logo

A celebrated result of Alon from 1993 states that any d-regular graph on n vertices (where d=O(n1/9)) has a bisection with at most [Formula presented.] edges, and this is optimal. Recently, this result was greatly extended by Räty, Sudakov, and Tomon. We build on the ideas of the latter, and use a semidefinite programming inspired approach to prove the following variant for hypergraphs: every r-uniform d-regular hypergraph on n vertices (where d≪n1/2) has a bisection of size at most [Formula presented.] for some c=c(r)>0. This bound is the best possible up to the precise value of c. Moreover, a bisection achieving this bound can be found by a polynomial-time randomized algorithm. The minimum bisection is closely related to discrepancy. We also prove sharp bounds on the discrepancy and so called positive discrepancy of hypergraphs, extending results of Bollobás and Scott. Furthermore, we discuss implications about Alon-Boppana type bounds. We show that if H is an r-uniform d-regular hypergraph, then certain notions of second largest eigenvalue λ2 associated with the adjacency tensor satisfy λ2≥Ωr(d), improving results of Li and Mohar.

Consider the partially ordered set on [t]n:={0,…,t−1}n equipped with the natural coordinate-wise ordering, and let A(t,n) denote the number of antichains of this poset. Determining A(2,n) is the celebrated problem of Dedekind from 1897, and the general quantity A(t,n) has a number of combinatorial interpretations: it is precisely the number of (n−1)-dimensional partitions with entries from {0,…,t}, and by a result of Moshkovitz and Shapira, A(t,n)+1 is equal to the n -color Ramsey number of monotone paths of length t in 3-uniform hypergraphs. This has led to significant interest in the growth rate of A(t,n). Trivially, log2⁡A(t,n)≥α(t,n), where α(t,n) is the size of a maximal antichain in [t]n. In the present paper, we prove that this simple lower bound is close to optimal, in particular for every t,n≥2, log2⁡A(t,n)≤(1+O((log⁡n)3n))⋅α(t,n). This resolves a conjecture of Moshkovitz and Shapira, and gives the first bound that is close to optimal for growing t . Our proof is based on the graph container method, partly inspired by previous work of Pohoata and Zakharov. One of our main contributions is a novel supersaturation result in [t]n. We prove that for any k∈Z+ and δ>0, any set A⊂[t]n of size at least (k+δ)α(t,n) contains a vertex comparable to at least Ωδ,k((n/log⁡n)k) other elements of A , a bound that is optimal up to logarithmic factors. We achieve this by constructing a normalized matching flow on the cover graph of [t]n in which the distribution of weights is close to uniform, a result that may be of independent interest.

A strong s-blocking set in a projective space is a set of points that intersects each codimension-s subspace in a spanning set of the subspace. We present an explicit construction of such sets in a (k-1)-dimensional projective space over Fq of size Os(qsk), which is optimal up to the constant factor depending on s. This also yields an optimal explicit construction of affine blocking sets in Fqk with respect to codimension-(s+1) affine subspaces, and of s-minimal codes. Our approach is motivated by a recent construction of Alon, Bishnoi, Das, and Neri of strong 1-blocking sets, which uses expander graphs with a carefully chosen set of vectors as their vertex set. The main novelty of our work lies in constructing specific hypergraphs on top of these expander graphs, where tree-like configurations correspond to strong s-blocking sets. We also discuss some connections to size-Ramsey numbers of hypergraphs, which might be of independent interest.

We prove that Boolean matrices with bounded γ2-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded γ2-norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph G with m edges has a cut of size at least m2+8m+1-18, with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of G is at most m2+O(m), then G must contain a clique of size Ω(m).

Given a prime p and positive integer n, let fp(n) denote the minimal number of hyperplanes in an irredundant covering of Fnp such that the normal vectors of the hyperlanes span the whole space. The function fp(n) appears to be in connection to several longstanding conjectures in linear algebra and group theory, such as the Alon-Jaeger-Tarsi conjecture, the Additive Basis conjecture, and a conjecture of Pyber on irredundant coset covers of abelian groups. We prove that log p fp(n) = Omega log log p . n , and use this result to make substantial progress on each of the aforementioned conjectures.

More than 40 years ago, Galvin, Rival, and Sands showed that every K_s,s-free graph containing an n-vertex path must contain an induced path of length f(n), where f(n)→∞ as n→∞. Recently, it was shown by Duron, Esperet, and Raymond that one can take f(n) = (log log n)^1/5-o(1). In this note, we give a short self-contained proof that a K_s,s-free graph with an n-vertex path contains an induced path of length at least (log log n)^1-o(1). Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of O((log log n)^1+o(1)), this essentially resolves this old problem.

The positive discrepancy of a graph G of edge density (Formula presented.) is defined as (Formula presented.). In 1993, Alon proved (using the equivalent terminology of minimum bisections) that if G is d-regular on n vertices, and d = O(n1/9), then disc+(G) = Ω(d1/2n). We greatly extend this by showing that if G has average degree d, then (Formula presented.). These bounds are best possible if d << n3/4, and the complete bipartite graph shows that disc+(G) = Ω(n) cannot be improved if d ≈ n/2. Our proofs are based on semidefinite programming and linear algebraic techniques. An interesting corollary of our results is that every d-regular graph on n vertices with (Formula presented.) has a cut of size (Formula presented.). This is not necessarily true without the assumption of regularity, or the bounds on d. The positive discrepancy of regular graphs is controlled by the second eigenvalue λ2, as (Formula presented.). As a byproduct of our arguments, we present lower bounds on λ2 for regular graphs, extending the celebrated Alon-Boppana theorem in the dense regime.

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).