Mathematics

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

Democratic Primaries, FiveThirtyEight, and Markov Chains

At the moment I am very busy writing things like grant applications and research papers, so I lack the time for blog posts. But then I wasted part of my evening reading this article on FiveThiryEight about the Democratic Party primaries in the US. For each democratic primary contender, they provide the following data:

How many of their current supporter do not consider voting for another candidate. For instance for Biden this number is 21.9%, while for Buttigieg it is only 6.2%.
Which other candidates their supporter are considering. For instance 52.2% of Biden’s supporter also consider Warren, 39.2% Sanders, 28.9% Harris, and 24.8% Buttigieg.

(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…)

Huang’s Breakthrough, Cvetković’s Bound, Godsil’s Question, and Sinkovic’s Answer

Let us consider the ${n}$ -dimensional hypercube ${\{ 0, 1 \}^n}$ . The Hamming graph on ${H_n}$ has the elements of ${\{ 0, 1 \}^n}$ as vertices an two vertices are adjacent if their Hamming distance is one, so they differ in one coordinate. It is easy to see that the independence number ${\alpha}$ of this graph is ${2^{n-1}}$ .

It was a long open and famous problem what the maximum degree of an induced subgraph on ${H_n}$ with ${\alpha+1}$ vertices is. Very recently, Hao Huang showed that the answer is “at least ${\sqrt{n}}$ ” and everyone is blogging about it (only a small selection): Anurag Bishnoi, Gil Kalai, Terry Tao, Fedya Petrov. Here I am jumping on this bandwagon.

Huang uses a variant of the inertia bound (or Cvetković bound). It is a good friend of the ratio bound (or Hoffman’s bound) which is the namesake of this blog. For the second time this year (the first time was due to a discussion with Aida Abiad), this I was reminded me of a result by John Sinkovic from 3 years ago. This blog posts is about Sinkovic’s result which answered a question by Chris Godsil on the inertia bound.
(more…)

Pseudorandom clique-free graphs

Anurag Bishnoi wrote a post about a recently finished preprint on pseudorandom clique-free graphs written by me, Anurag, and Valentina Pepe. We (slightly) improve a construction by Alon and Krivelevich from 1997.

Anurag's Math Blog

Pseudorandom graphs are graphs that in some way behaves like a random graph with the same edge density. One way in which this happens is as follows. In the random graph $latex G(n, p)$, with $latex p = p(n) leq 0.99$, a direct application of Chernoff bound implies that the probability of the following event approaches $latex 1$ as $latex n$ approaches infinity:

$latex |e(S, T) – p|S||T|| = O(sqrt{pn |S||T|}$

where $latex S,T$ are arbitrary subsets of vertices and $latex e(S,T)$ denotes the number of edges with one end vertex in $latex S$ and the other one in $latex T$. Note that $latex p|S||T|$ is the expected number of edges between $latex S$ and $latex T$ in this model, and $latex sqrt{p(1 – p)|S||T|}$ is the standard deviation. Now let $latex G$ be a $latex d$-regular graph on $latex n$-vertices and let $latex lambda$ be the second largest…

View original post 804 more words

Constructing Cospectral Graphs

Last week I had a cold and could not do much thinking. So I spent my time making TikZ pictures for an upcoming talk of mine. This talk is on my recent work with Akihiro Munemasa on constructing cospectral strongly regular graphs. I think that the pictures are nice for a blog post, so here we go.

1. The Spectrum of a Graph

Two graphs ${\Gamma}$ and ${\overline{\Gamma}}$ are called cospectral if their adjacency matrices ${A}$ and ${\overline{A}}$ have the same eigenvalues. This is the same as saying that there is an orthogonal matrix ${Q}$ with ${\overline{A} = Q^T A Q}$ . Any permutation matrix is a valid choice for ${Q}$ , but this is not very interesting as then ${\Gamma}$ and ${\overline{\Gamma}}$ are isomorphic. Chris Godsil and Brendan McKay described one of the easiest interesting choices for ${Q}$ in 1982. For a graph ${\Gamma}$ on ${v}$ vertices, a simplified version of their matrix is

$\displaystyle Q = \begin{pmatrix} \frac{1}{m} J_{2m} - I_{2m} & 0 \\ 0 & I_{v-2m} \end{pmatrix}.$

(more…)

Boolean Degree 1 Functions on Association Schemes

This is the announced post on my recent paper with Yuval Filmus on Boolean degree ${1}$ functions on association schemes. The post will focus on what motivates the problem from various points of view.

Before I start, a small remark. I am using latex2wp for the first time in this post. Thanks to Luca Trevisan for providing this nice script.

During this post I avoid using many definition, while I cite things that use all kind of terminology. For this I wrote this blog post as a reference. We will go through the main steps in the paper and focus more on the wider context of the research, so the parts for which there is less space in papers and not enough time in talks.

(more…)

Translating Terminology: Equitable Partitions and Related Concepts

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

Schrijver’s SDP Bound for Network Codes

This is a small report on a failed project — obtaining semidefinite programming bounds on constant dimension network codes. But let us start with some context …

A network code consists of a set of subspaces in $\mathbb{F}_q^n$ . It is a code, so we want to maximize the distance between subspaces (or increase the code’s cardinality or rate). The most reasonable metric for this is the subspace metric in which two subspaces $U$ and $W$ have distance $\dim(U+W) - \dim(U \cap W)$ , that is the shortest distance between $U$ and $W$ in the subspace lattice. These codes are used in random linear network coding, that is a method for the many-to-many transmission of data in a network which is faster than multiple one-to-one connections. As in classical coding theory, one area of research on those subspace codes is concerned with bounding the maximal size of a code with minimum distance $d$ in $\mathbb{F}_q^n$ . Notice that one can interpret $q=1$ as a field with one element as is explained here by Peter Cameron. Then it corresponds to classical coding theory. (more…)

The chromatic number of the Kneser graphs and the q-Kneser graphs

This year is László Lovász‘s 70th birthday and I went to his birthday conference, so a blog post about one of his famous results seems to be appropriate: the chromatic number of the Kneser graph.

Let $\Gamma$ be a graph with a vertex set $V$ and an adjacency relation $\sim$ . A coloring of $\Gamma$ is a map from $V$ from $V$ to a set of colors $C$ such that no pair of adjacent vertices gets mapped to the same element of $C$ . The chromatic number of $\Gamma$ is the smallest number of colors needed to color $\Gamma$ . One of the nicest graphs to investigate is the Kneser graph: Here $V$ consists of all subsets of $\{ 1, 2, \ldots, n \}$ of size $k$ and two vertices are adjacent if the corresponding $k$ -sets are disjoint. For $k=2$ and $n=5$ , this is the famous Petersen graph:

400px-Kneser_graph_KG(5,2).svg (more…)

	igorpak on How to Phrase/Make a Conj…
	Bielefeld Buildings… on Erdős-Ko-Rado Theorems for Sph…
	Collecting Strongly… on Constructing Cospectral Graphs
	Collecting Strongly… on Sp(6, 2)’s Family, Plots…
	Ferdinand Ihringer on Constructing Cospectral Graphs