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

Advertisement

The insidious corruption of open access publishers

I get spam from MPDI on a regular bases. Here why one should not review for MPDI journals or submit to MPDI journals.

Igor Pak's blog

The evil can be innovative. Highly innovative, in fact. It has to be, to survive. We wouldn’t even notice it otherwise. This is the lesson one repeatedly learns from foreign politics, where authoritarian or outright dictatorial regimes keeps coming up with new and ingenuous uses of technology to further corrupt and impoverish their own people. But this post is about Mathematics, the flagship MDPI journal.

What is MDPI?

It’s a for profit publisher of online-only “open access” journals. Are they legitimate or predatory? That’s a good question. The academic world is a little perplexed on this issue, although maybe they shouldn’t be. It’s hard for me to give a broad answer given that it publishes over 200 journals, most of which have single word wonder titles like Data, Diseases, Diversity, DNA, etc.

If “MDPI” doesn’t register, you probably haven’t checked your spam folder…

View original post 2,897 more words

Bielefeld Buildings Conspiracy

The 28th edition of the Buildings conference is held in Ghent (where I am currently based) this September. [Note that this is unrelated to the actually buildings which you live and work in. The mathematical branch of building theory is abstract algebra. I have one post mentioning them.] Now I am not in the habit of announcing conferences here, so why this post? (It isn’t a good reason.) I just had a look at the list of invited speakers on the conference homepage (accessed on 24 August 2022, 22:04, Belgian time):

Only one “tba”. For the University of Bielefeld. Among all “silly” conspiracy theories, the Bielefeld conspiracy (in short: Bielefeld does not exist) might be the most popular one: Tom Scott made a video about it, Angela Merkel referenced it in a speech, people, who claim to be from Bielefeld, regularly express their frustration with it, and some people claim that it is no longer funny. (But it is a German joke, so maybe it never was funny.) Anyway: the “tba” should not surprise anyone.

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

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