Equiangular lines with a fixed angle and other breakthroughs from Yufei Zhao’s blog

Today I would like to report about some breakthroughs in the area of combinatorics, and about blog posts in Yufei Zhao’s blog that describe these remarkable results (better than I can). Many of the coauthors in these breakthroughs are undergraduate students.

Equiangular lines with a fixed angle

by Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

Paper ; blog post (end of July, 2019)

A collection of equiangular lines is a collection of lines so that the angles between every pair of lines in the same?

Here are two classical questions:

1. What is the maximum number of equiangular lines in ?
2. Given an angle what is the maximum number of equiangular lines in ? so that the angle between every two lines is

In 2000 Dom de Caen found for the first time an equiangular set of lines in space of size . (The crucial observation that one of the graphs in the Cameron–Seidel association scheme has a certain eigenvalue of large multiplicity.  Prior to this construction, the largest sets had sizes of order .  In de Caen’s example the lines have angles approaching 90 degrees, and question 2 for a fixed value of led to very different bounds. (For another result by Dom, see this post.)

There were some important progress on this problem by Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, as featured in this  Quanta Magazine article written by Kevin Hartnett. Zilin, Jonathan, Yuan, Shengtong, and Yufei  finished off the problem in a clean and crisp manner, in a 10-page paper with a self-contained proof. On the way they proved the following very interesting theorem.

Theorem: A bounded degree graph must have sublinear second eigenvalue multiplicity.

Impartial digraphs

by Yufei Zhao and Yunkun Zhou.

Paper, blog post (end of June 2019)

Abstract: We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.

“Constant density in all tournaments” means that for some (and hence for all , every tournament with vertices has the same number of copies of . (On the nose!)

This result is related to the famous Sidorenko’s conjecture. Let me copy its description from the paper:

For undirected graphs, conjectures of Sidorenko and Erdős–Simonovits (commonly referred to as Sidorenko’s conjecture) say that for every bipartite graph , the -density in a graph of fixed density is minimized asymptotically by a random graph. Lately the conjecture has been proved for many families of though the conjecture remains open in general. In particular, the case is open.

Yufei Zhao

More

Let me describe briefly three additional posts on Yufei’s blog with two results from 2018 and one result from 2014.

Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao  A reverse Sidorenko inequality; (blog post) ; The number of independent sets in an irregular graph; blog post.

These are two remarkable papers by the same team of researchers. The paper  on the number of independent sets in a regular graph settled a famous 2001 conjecture by Jeff Kahn. An earlier breakthrough on the problem was made by Zhao in 2009 when he was an undergraduate student.

Eyal Lubetzky and Yufei Zhao,  On the variational problem for upper tails of triangle counts in sparse random graphs. Blog post.

Recently  I wrote a post Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem describing a major breakthrough on the infamous upper tail problem. Over the years I heard a lot of lectures and private explanation on upper tails and the remarkable related mathematics. I remember lectures by Kim and Vu from the early 2000’s and by Varadhan from ICM 2010 describing (among other things) the fundamental paper by  Chatterjee and Varadhan,  and later works by  DeMarco and Kahn,  and by  Chatterjee and Dembo  and Lubetzky and Zhao and others. But when I wrote the post I realized my knowledge is too sparse for giving a thorough description, and I decided not to wait and write a short post. This post by Yufei describes some of the history very nicely as well as the major papers by Eyal and Yufei from 2012 and 2014.