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: