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.
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).)
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
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.
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 and . 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 and a witness for for . 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.
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.
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 , has parameters . 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 . Plots of the number of cliques, cocliques, and the size of the autmorphism group are scattered throughout this post.
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.
As Anurag Bishnoi likes to point out on his blog, an often overlooked source of wisdom is Willem Haemer’s PhD thesis from 1979. Many of Haemer’s proofs rely on simple properties of partitions of Hermitean matrices. My motivation for this post was a small exercise for myself. I wanted to prove the easy one of the two Cheeger inequalities for graphs using Haemer’s technique. Non-surprisingly, the book “Spectra of Graphs” by Brouwer and Haemers gives this kind of proof.
The K3xK3 graph with two highlighted equitable partitions. Think of the lines as cliques of size 3. This is a picture from my Master thesis many, many years ago.
Earlier on this blog we discussed that there are many different names for equitable partitions. My list from back then is incomplete as (1) I intentionally left out terms such as -designs (not to be confused with -designs) from Delsarte’s PhD thesis, and (2) I realized that for instance Stefan Steinerberger defined a notion of graphical designs which resembles the definition of a -design, while people working on latin squares call them -plexes, for instance see here. For this post just recall the following facts on equitable partitions: