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

Advertisements

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

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