Mathematics

Mathematicians & Bureaucrats

All (most) math departments have a day where school students come to the department and you do math-y activities with them. In Ghent this day is called UniMath and happened today. My colleague Zhirayr Avetisyan and I contributed a riddle to it. Maybe it was a bit too hard, but I like what we ended up with. Here it is. Have a look at the city map of Ghent to see which locations we used (and how much we distorted reality, so that the map is a square).

It is well-known that mathematicians and bureaucrats are archenemies of all times. For mathematicians normally take a hard problem and make it simpler in order to render it solvable, whereas bureaucrats take pride in making otherwise simple problems into very hard ones, so that they become effectively unsolvable.

Below is an abstracted map of the city of Ghent with a selection of landmarks (text) and routes (lines) between them. A group of mathematicians leaves the Sterre campus of UGent in the evening, with the aim of enjoying their time together in the city. Right after that, several bureaucrats leave the city hall at Zuid simultaneously and move each in independent directions, with the aim of catching the mathematicians and preventing them from having fun. Mathematicians always move as a single group, whereas each bureaucrat acts as a separate player. Each turn every player (first the group of mathematicians, then bureaucrat 1, bureaucrat 2, …, bureaucrat n) moves from their present location to one of the nearest locations along a route on the map. Mathematicians are caught if at any moment they are at the same location as at least one of the bureaucrats.

Question At least how many bureaucrats must be allocated for the mission such that the mathematicians are definitely caught at some point?

Everyone always knows where everyone else is, bureaucrats and mathematicians can choose where to move (as long as it is one step along one route), and the chase goes on for all of eternity.

There are many valid solutions. The riddle above was one example in one of the central works on this research area. You can click here to read the paper (but first find the solution yourself).

Collecting Strongly Regular Graphs

Today I write about a recent hobby of mine: Collecting strongly regular graphs. It started three years ago. You can find my collection on my homepage. I collect many SRGs with known parameters. It started here. This is about size, not quantity, and tries to give an idea how a typical SRG with certain parameters might look like. By now my collection has grown so big that I should advertise and describe it.

At the time of writing, my collections splits into four parts. The first two parts are graphs generated with GM- or WQH-switching. The second two parts are graphs generated with what I call Kantor switching. All the data is provided in graph6 format in a compressed text file. In total something beyond 190 million.

(more…)

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.

(more…)

Don’t be a Square (but count them)

One of the structures investigated in finite geometry are related to quadratic forms over finite fields (see below for definitions). Knowledge on the geometry of singular points of quadratic forms is very common and covered in many textbooks on finite geometry, but one cannot say the same for the geometry on non-singular points. This short post tries to amend this a little.

(This is no surprise as the geometry with singular points is much nicer than the geometry associated with various types of non-singular points. Also, everything in the following is well-known for decades. It is simply a bit more obscure than other facts about finite quadrics. Lastly, my title is a terrible pun on slang from the mid-20th century (and Pulp Fiction).)

(more…)

Almost a Hadamard Matrix

Recently, Yu Hin Au, Nathan Lindzey, and Levent Tunçel published a preprint with various spectral bounds on the arXiv. They investigate generalizations of bounds due to Delsarte and Hoffman in the context of the Lovász-Schrijver SDP. Page 12 of that article I knew for a few more days because Nathan asked me if their bound is known. The bound is simply an example to showcase their techniques. Here I will present another method of showing the same bound. Consider the graph ${G_\ell}$ which is defined as follows: Vertices are the elements of ${\{ 0, 1 \}^{2\ell+1}}$ and two vertices are adjacent if they have Hamming distance ${\ell}$ or ${\ell+1}$ , that is they differ in ${\ell}$ or ${\ell+1}$ positions. On page 12, they obtain the following bound:

Theorem 1 A clique of ${G_\ell}$ has at most size ${2\ell+2}$ .

Here we will discuss equality in this bound and a small improvement for ${\ell}$ even.

(more…)

R(5, 22) and R(6, 21)

A quick post about small Ramsey numbers. I like to write on my blog about things which I do not intend to publish, but also do not want to keep as private knowledge. This is one of these posts.

Stanisław P. Radziszowski writes the following in the 15th revision of his survey on small Ramsey numbers:

One can expect that the lower bounds in Table II are weaker than those in Table I, especially smaller ones, in the sense that some of them should not be that hard to improve, in contrast to the bounds in Table I.

Table II contains slightly larger Ramsey numbers, for instance $R(5, 22)$ and $R(6, 21)$ . So when one has idle CPU time, it seems to be reasonable to use it here, I thought some weeks ago. And indeed, it is. I found a witness for $R(5, 22) \geq 492$ and a witness for for $R(6, 21) \geq 884$ . This improves the previously known lower bounds by a gigantic 7 in the first case and a nearly as gigantic 6 in the second case. Here you can find a short description of both cases.

And if anyone asks: The upper bounds are much, much, much larger than both lower bounds. Also I did not put any effort into my search, so it is probably very feasible to improve a few more numbers in Table II of the survey.

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.

(more…)

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.

(more…)

How to Phrase/Make a Conjecture

Recently, I collected a short list of phrases for conjectures on a well-known social media platform and several people contributed to it. One can easily find more examples online, but I like my list, so I will keep it here and include references (as far as I have them). Probably, I will add more entries over time.

Firstly, I will give a list of phrases. Secondly, references for the phrases.
(more…)

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:

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

(more…)

	igorpak on How to Phrase/Make a Conj…
	Bielefeld Buildings… on Erdős-Ko-Rado Theorems for Sph…
	Collecting Strongly… on Constructing Cospectral Graphs
	Collecting Strongly… on Sp(6, 2)’s Family, Plots…
	Ferdinand Ihringer on Constructing Cospectral Graphs