# The History of Hoffman’s (Ratio) Bound

Hoffman’s bound (or: ratio bound) on the size of a coclique (or: independent set, stable set) in a graph is one of the most important bounds in spectral graph theory. At the same time it is often misattributed. Primary reason for is that Hoffman never published it, but people want to cite something for it. A few weeks ago, Willem Haemers published a nice article which presents the history of Hoffman’s ratio bound (here is the journal version).

As I have probably misattributed the bound myself in the past and even one of my favorite books, “Distance-Regular Graphs” by Brouwer, Cohen and Neumaier does so too (but they correct it online), I wanted to make this quick post.

The sad occasion of Willem’s article is that Alan J. Hoffman past away on the 18th January 2021 at the age of 96. May he rest in peace.

Recently, Yu Hin Au, Nathan Lindzey, and Levent Tunçel published a preprint with various spectral bounds on the arXiv. They investigate generalizations of bounds due to Delsarte and Hoffman in the context of the Lovász-Schrijver SDP. Page 12 of that article I knew for a few more days because Nathan asked me if their bound is known. The bound is simply an example to showcase their techniques. Here I will present another method of showing the same bound. Consider the graph ${G_\ell}$ which is defined as follows: Vertices are the elements of ${\{ 0, 1 \}^{2\ell+1}}$ and two vertices are adjacent if they have Hamming distance ${\ell}$ or ${\ell+1}$, that is they differ in ${\ell}$ or ${\ell+1}$ positions. On page 12, they obtain the following bound:

Theorem 1 A clique of ${G_\ell}$ has at most size ${2\ell+2}$.

Here we will discuss equality in this bound and a small improvement for ${\ell}$ even.

# Proving Spectral Bounds With Quotient Matrices

As Anurag Bishnoi likes to point out on his blog, an often overlooked source of wisdom is Willem Haemer’s PhD thesis from 1979. Many of Haemer’s proofs rely on simple properties of partitions of Hermitean matrices. My motivation for this post was a small exercise for myself. I wanted to prove the easy one of the two Cheeger inequalities for graphs using Haemer’s technique. Non-surprisingly, the book “Spectra of Graphs” by Brouwer and Haemers gives this kind of proof.

The K3xK3 graph with two highlighted equitable partitions. Think of the lines as cliques of size 3. This is a picture from my Master thesis many, many years ago.

Earlier on this blog we discussed that there are many different names for equitable partitions. My list from back then is incomplete as (1) I intentionally left out terms such as ${T}$-designs (not to be confused with ${t}$-designs) from Delsarte’s PhD thesis, and (2) I realized that for instance Stefan Steinerberger defined a notion of graphical designs which resembles the definition of a ${T}$-design, while people working on latin squares call them ${k}$-plexes, for instance see here. For this post just recall the following facts on equitable partitions:
(more…)

# Six Spectral Bounds

I spent the last few days in vain using several spectral arguments to bound the size of certain intersection problems. For instance what is the largest set of vectors in ${\{ 0, 1 \}^4}$ pairwise at Hamming distance at most ${2}$ (a problem solved by Kleitman, recently investigated by Huang, Klurman and Pohoata). Here the answer is ${5}$ and ${0000}$, ${0001}$, ${0010}$, ${0100}$, ${1000}$ would be such an example. Or the largest set of vectors in ${\{ 0, 1 \}^7}$ pairwise at distance ${2}$ or ${6}$. Here the answer is ${8}$ and an example is ${0000001}$, ${0000010}$, ${0000100}$, ${0001000}$, ${0010000}$, ${0100000}$, ${1000000}$, ${1111111}$. This is a problem which I recently investigated together with Hajime Tanaka, extending work by Frankl and others.

Usually, this playing around does not lead to anything. But this time …. It is actually the same. However, I did one useful thing which is the following: Generously counting, I do know five different easy spectral arguments which can be used to investigate these questions. This blog post presents these methods for the two problems mentioned above.
(more…)

# Permutation Groups, Analysis of Boolean Functions, Finite Geometry, Coding Theory and Algebraic Graph Theory

Important mathematical concepts get reinvented many times. In my recent work with Yuval Filmus we explored objects that are called (in random ordering) Boolean degree 1 functions, Cameron-Liebler line classes, equitable partitions, completely regular strength 0 codes with covering radius 1, intriguing sets, perfect colorings, sets with dual width 1, tactical decompositions or tight sets — all depending on the context and who you ask. While the article with Yuval explains to some extent how these notions connect, a research article does not seem to be the right format to explain all concepts in sufficient detail. This post tries to amend this. It also prepares a future post which will elaborate my research with Yuval in more detail. (more…)

# Erdős-Ko-Rado Theorems for Spherical Buildings

Today’s topic combines three of my favorite subjects: Erdős-Ko-Rado theorems (EKR theorems), finite buildings and spectral techniques. All of these topics deserve their own books (and have them, here some examples which I read: Erdos-Ko-Rado Theorems: Algebraic Approaches by Chris Godsil and Karen Meagher, Spectra of Graphs by Andries E. Brouwer and Willem H. Haemers, The Structure of Spherical Buildings by Richard M. Weiss), so I will only touch these topics slightly.

My main aim is to present a variation of the EKR theorem which is motivated by questions about spherical buildings. The variation was recently formulated by Klaus Metsch, Bernhard Mühlherr, and me. If you already know spherical buildings, then you might prefer to read the introduction of our paper instead. (more…)