Reichstagsgebäude

German Elections! What do the parties say about ̶m̶̶̶a̶̶̶t̶̶̶h̶̶̶?̶ quantum?

Germany votes for a new parliament on the 26th of September 2021, so only in a few weeks from now. What do the German parties say about math in their election platforms? Not much, but they talk much about math-related topics such as artificial intelligence and quantum computing. So let us have a look! Actually, only at quantum thingies. Otherwise, it is too much to write here.

(more…)

The History of Hoffman’s (Ratio) Bound

Hoffman’s bound (or: ratio bound) on the size of a coclique (or: independent set, stable set) in a graph is one of the most important bounds in spectral graph theory. At the same time it is often misattributed. Primary reason for is that Hoffman never published it, but people want to cite something for it. A few weeks ago, Willem Haemers published a nice article which presents the history of Hoffman’s ratio bound (here is the journal version).

As I have probably misattributed the bound myself in the past and even one of my favorite books, “Distance-Regular Graphs” by Brouwer, Cohen and Neumaier does so too (but they correct it online), I wanted to make this quick post.

The sad occasion of Willem’s article is that Alan J. Hoffman past away on the 18th January 2021 at the age of 96. May he rest in peace.

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

Quick Note: How to Referee Anonymously

When you submit an article in mathematics to a journal, then it will be reviewed by other mathematicians. These are unknown to you. It is a so-called single-blind process. This is so that the referees do not have to fear the wreath of the authors if they write a bad review. Now often this anonymity is a bit of a lie. You might know the style of a referee and recognize her that way. Sometimes the referee intentionally reveals herself for a variety of reasons (more commonly, after the article is published). But for me, the only time when I dare to guess the referee is when she unintentionally reveals herself. Namely, by PDF metadata. This is a short note on how to avoid this case as a reviewer.

Often, when you write your referee report, your LaTeX compiler will add some meta-data. This metadata can be used to de-anonymize a referee report. Now I do not want to get into examples, but you can see the metadata in your PDF file usually under “Properties” in your PDF reader.

Here now a quick guide to avoid this reliably. My example is for Linux, but Windows or Mac users have the same tools available to them. That is, you need exiftool and qpdf. If the name of your referee report is review.pdf, then you can do the following in your console/shell (in the same directory as review.pdf):

$ exiftool -all= -overwrite_original review.pdf
$ mv review.pdf tmp.pdf
$ qpdf --linearize tmp.pdf review.pdf

Note that for Windows “mv” is “move”. Now your referee report is free of metadata and it is harder for the author to guess who you are. Besides these technicalities, always pay attention to metadata when at least a superficial level anonymity is important.

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.

size_aut

(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:

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

(more…)