association scheme

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.

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