# A Boolean Function with Small Degree and Many Variables

Recently, while working on a research project, I got on a tangent. From this tangent, I got on another tangent and that is what I want to write about today: a very nice Boolean function. This example got rediscovered several times for different reasons and, as I try to emphasize from time, I believe that things that are getting rediscovered many times must be of particular importance.

So let us define our Boolean function. I will give three very similar definitions throughout this post, but I will start with only one. Put ${\ell(d) := 3 \cdot 2^{d-1} - 2}$. Our Boolean function ${F_d: \{ 0, 1\}^{\ell(d)} \rightarrow \{ 0, 1\}}$ is defined as follows: Put ${F_1(x) = x}$ (as ${\ell(1)=1}$). For ${d > 1}$, write ${x \in \{ 0, 1\}^{\ell(d)}}$ as ${x=(s,t,y,z)}$ with ${s,t \in \{ 0,1 \}}$ and ${y, z \in \{ 0, 1\}^{\ell(d-1)}}$. Then use this rule:

• If ${s=t=1}$, then ${F_d(1,1,y,z) = F_{d-1}(y)}$.
• If ${s \neq t=0}$, then ${F_d(1,0,y,z) = F_{d-1}(z)}$.
• If ${s= t = 0}$, then ${F_d(0,0,y,z) = 1-F_{d-1}(y)}$.
• If ${s \neq t = 1}$, then ${F_d(0,1,y,z) = 1-F_{d-1}(z)}$.

In the following, we list some properties of this function. Many of the concepts here are also discussed in an earlier post of mine.

# Sp(6, 2)’s Family, Plots, and Ramsey Numbers

Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36, 10, 4, 2), but there are 32548 non-isomorphic graphs with parameters (36, 15, 6, 6).

Peter Cameron, Random Strongly Regular Graphs?

This a shorter version of this report which I just put on my homepage. But I added more links. I assume that one is familiar with strongly regular graphs (SRGs). One particular SRG, the collinearity graph of $Sp(6, 2)$, has parameters $(63, 30, 13, 15)$. A very simple technique, Godsil-McKay (GM) switching, can generate many non-isomorphic graphs with the same parameters. More specifically, there are probably billions such graphs and I generated 13 505 292 of them. This is the number of graphs which you obtain by applying a certain type of GM switching (i.e. using a bipartition of type 4, 59) at most 5 times to $Sp(6,2)$. Plots of the number of cliques, cocliques, and the size of the autmorphism group are scattered throughout this post.

# The Independence Number of the Orthogonality Graph — Or: The Usefulness of Literature Study

Let ${X}$ be the orthogonality graph, that is the graph with ${\{ -1, 1 \}^n}$ as vertices with two vertices adjacent if they are orthogonal. So ${x, y \in \{ -1, 1 \}^n}$ are adjacent if ${x \cdot y = x_1y_1 + x_2y_2 + \ldots + x_ny_n = 0}$. There are many publications which investigate this problem. The aim of this post is two fold:

1. To summarize the state of the art.
2. To demonstrate how careful literature study is helpful to obtain results.

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

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}.$

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