Graph Theory – Explicit Constructions of Regular Graphs with Sparse Induced Subgraphs

Question

Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$ vertices where $\alpha$ is a constant depending on $d$ has average degree bounded by, say, $2.1$?

Note that a random $d$-regular graph satisfies this property (see, for example, Section 4.6 of https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf for a proof).

Let's also say we aren't picky about achieving this for literally every choice of $d$, and would be happy with obtaining a construction for arbitrarily large $d$. The notion of explicit here is that the graph is constructible in polynomial time in the number of vertices. Let's also say we are happy if the average degree bound of $2.1$ is replaced by any constant $C$ as long as it does not depend on $d$.

Do any of the explicit constructions of Ramanujan graphs, such as the Lubotzky-Phillips-Sarnak/Margulis/Morgenstern constructions, achieve this property? The best bound we know on the average degree is about $\sqrt{d-1}+1$, which only uses the fact that the second largest magnitude eigenvalue is at most $2\sqrt{d-1}$. Is this bound improvable?

Answer 1

I think that for Ramanujan graphs the situation is similar to vertex expansion, which got more publicity. Namely, a variation of the combinatorial construction of Kahale about vertex expansion (https://www.researchgate.net/publication/2782658_Eigenvalues_and_Expansion_of_Regular_Graphs, Theorem 7, the same paper which proves the edge expansion result you states) should show that you can't expect to get any better using only the second-largest eigenvalue.

Furthermore, in my recent paper with Tali Kaufman (https://arxiv.org/abs/2103.04311, Theorem 1.8 in the current version) we show that you can construct "number theoretic" Ramanujan graphs with plenty of nice properties (high girth, large automorhism group) with a small set (of size square-root of the graph) having exactly the $\sqrt{d-1}+1$ average degree.

On the other hand, as with vertex expansion, the general belief/ hope is that LPS graphs have the property you mentioned, but there is no proof of this in sight.

Two more optimistic comments:

1. In the case when $\sqrt{d-1}$ is not an integer the result can be very slightly improved, essentially because not every vertex can have the average degree.
2. Perhaps you can hope for a construction as in http://www.cs.tau.ac.il/~nogaa/PDFS/acaproc.pdf for this specific question. Namely, the graphs will not have some local structure which can help you. More realistically, maybe this can lead to a construction such that every set of size bounded by $\alpha n$ have a vertex of constant induced degree. I don't even know if this far weaker problem was solved.