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.


A Very Short History of Pseudorandom Cliquefree Graphs

I started writing this blog post some months ago. Occasion was that my paper “A construction for clique-free pseudorandom graphs” (in joint work Anurag Bishnoi and Valentina Pepe) was accepted by Combinatorica with minor revisions. More precisely, one of the referees was unfavorable of publication because he got the impressions that we are simply restating a result by Bannai, Hao and Song. I think that the referee had a point, but for slightly wrong reasons. This triggered me to do two things. First of all, it made me include more history of the construction in our actual paper. Then I wanted to write a blog post about the history of the construction. Sadly, I wanted to include too much history in my first attempt to write this post, so it was very much out of scope. Here now a more concise version of my original plan.


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.