Author: Ferdinand Ihringer

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

Proving Spectral Bounds With Quotient Matrices

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 K3 times K3 graph with two highlighted equitable partitions.

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 {T}-designs (not to be confused with {t}-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 {T}-design, while people working on latin squares call them {k}-plexes, for instance see here. For this post just recall the following facts on equitable partitions:
(more…)

Democratic Primaries, FiveThirtyEight, and Markov Chains

At the moment I am very busy writing things like grant applications and research papers, so I lack the time for blog posts. But then I wasted part of my evening reading this article on FiveThiryEight about the Democratic Party primaries in the US. For each democratic primary contender, they provide the following data:

  • How many of their current supporter do not consider voting for another candidate. For instance for Biden this number is 21.9%, while for Buttigieg it is only 6.2%.
  • Which other candidates their supporter are considering. For instance 52.2% of Biden’s supporter also consider Warren, 39.2% Sanders, 28.9% Harris, and 24.8% Buttigieg.

(more…)

Six Spectral Bounds

I spent the last few days in vain using several spectral arguments to bound the size of certain intersection problems. For instance what is the largest set of vectors in {\{ 0, 1 \}^4} pairwise at Hamming distance at most {2} (a problem solved by Kleitman, recently investigated by Huang, Klurman and Pohoata). Here the answer is {5} and {0000}, {0001}, {0010}, {0100}, {1000} would be such an example. Or the largest set of vectors in {\{ 0, 1 \}^7} pairwise at distance {2} or {6}. Here the answer is {8} and an example is {0000001}, {0000010}, {0000100}, {0001000}, {0010000}, {0100000}, {1000000}, {1111111}. This is a problem which I recently investigated together with Hajime Tanaka, extending work by Frankl and others.

Usually, this playing around does not lead to anything. But this time …. It is actually the same. However, I did one useful thing which is the following: Generously counting, I do know five different easy spectral arguments which can be used to investigate these questions. This blog post presents these methods for the two problems mentioned above.
(more…)

Huang’s Breakthrough, Cvetković’s Bound, Godsil’s Question, and Sinkovic’s Answer

Let us consider the {n}-dimensional hypercube {\{ 0, 1 \}^n}. The Hamming graph on {H_n} has the elements of {\{ 0, 1 \}^n} as vertices an two vertices are adjacent if their Hamming distance is one, so they differ in one coordinate. It is easy to see that the independence number {\alpha} of this graph is {2^{n-1}}.

It was a long open and famous problem what the maximum degree of an induced subgraph on {H_n} with {\alpha+1} vertices is. Very recently, Hao Huang showed that the answer is “at least {\sqrt{n}}” and everyone is blogging about it (only a small selection): Anurag Bishnoi, Gil Kalai, Terry Tao, Fedya Petrov. Here I am jumping on this bandwagon.

Huang uses a variant of the inertia bound (or Cvetković bound). It is a good friend of the ratio bound (or Hoffman’s bound) which is the namesake of this blog. For the second time this year (the first time was due to a discussion with Aida Abiad), this I was reminded me of a result by John Sinkovic from 3 years ago. This blog posts is about Sinkovic’s result which answered a question by Chris Godsil on the inertia bound.
(more…)