Codes and Expansions (CodEx) Seminar

Last summer, I launched an online seminar with Joey Iverson, John Jasper, and Emily King on the theory and applications of harmonic analysis, combinatorics, and algebra. We meet on Tuesdays at 1pm (Eastern time).

Next week, we’re kicking off the spring semester with a talk from Steve Flammia on recent progress on Zauner’s conjecture.

Click here for the Zoom link and to sign up for the mailing list.

Click here for a list of past and upcoming talks.

Click here for the CodEx YouTube channel.

A graph coloring problem from quantum physics (with prizes!)

What follows is a nice problem that was recently posed by Mario Krenn. Progress on this problem may lead to new insights in quantum physics (see this, this, this, and this for details). In addition, Mario has announced two cash prizes to encourage work in this direction. (!)

Consider a weighted and edge-colored bipartite graph consisting of

• disjoint vertex sets and ,
• an edge set ,
• an edge coloring , and
• a complex vertex weighting .

MATH 2568: Linear Algebra

This spring, I’m teaching a first-semester course on Linear Algebra at the Ohio State University.

Click here for a draft of my lecture notes.

I will update the above link periodically. Feel free to comment below.

Update #1: Added two sections to Chapter 1.

Kopp’s Whisky Prize

At the end of his recent CodEx talk, Gene Kopp posed a problem with a prize attached to it. I was excited to learn about this, so I enlisted both Gene Kopp and Mark Magsino to help me write this blog entry to provide additional details.

First, let denote the set of matrices in such that

Here, denotes conjugate transpose, denotes entrywise squared modulus, denotes the identity matrix, and denotes the all-ones matrix. In words, the columns of form an equiangular tight frame (ETF) for of size .

Polymath16, sixteenth thread: Writing the paper and chasing down loose ends, II

This is the sixteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The paper writing has found a second wind between Philip Gibbs, Aubrey de Grey, Jaan Parts and Tom Sirgedas. For reference, I wanted to compile a list of related publications that have emerged since starting our project. (Feel free to any references I missed in the comments.) There has certainly been a bit of activity since Aubrey’s paper first hit the arXiv two years ago!

P. Ágoston, Probabilistic formulation of the Hadwiger–Nelson problem.

F. Bock, Epsilon-colorings of strips, Acta Math. Univ. Comenianae (2019) 88: 469-473.

G. Exoo, D. Ismailescu, A 6-chromatic two-distance graph in the plane, arXiv preprint arXiv:1909.13177 (2019).

G. Exoo, D. Ismailescu, The chromatic number of the plane is at least 5: A new proof, Discrete & Computational Geometry (2019): 1-11.

G. Exoo, D. Ismailescu, The Hadwiger-Nelson problem with two forbidden distances, arXiv preprint arXiv:1805.06055 (2018).

N. Frankl, T. Hubai, D. Pálvölgyi, Almost-monochromatic sets and the chromatic number of the plane, arXiv preprint arXiv:1912.02604 (2019).

M. J. H. Heule, Computing a Smaller Unit-Distance Graph with Chromatic Number 5 via Proof Trimming, arXiv preprint arXiv:1907.00929 (2019).

M. J. H. Heule, Searching for a Unit-Distance Graph with Chromatic Number 6, SAT COMPETITION 2018: 66.

M. J. H. Heule, Trimming Graphs Using Clausal Proof Optimization, In International Conference on Principles and Practice of Constraint Programming, pp. 251-267. Springer, Cham, 2019.

J. Parts. A small 6-chromatic two-distance graph in the plane, Geombinatorics, vol. 29, No. 3 (2020), pp.111-115.

J. Parts. Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane, Geombinatorics, vol. 29, No. 4 (2020), pp.137-166.

Polymath16, fifteenth thread: Writing the paper and chasing down loose ends

This is the fifteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

At this point, much of the effort is transitioning to the writing stage, which is taking place on Overleaf. See this comment to obtain writing privileges for the paper. This thread can be used to discuss the write-up as well as any remaining research items.

Spherical codes and designs

Later this month, Hans Parshall will participate in a summer school on “Sphere Packings and Optimal Configurations.” In preparation for this event, Hans was assigned the task of writing lecture notes that summarize the main results of the following paper:

P. Delsarte, J. M. Goethals, J. J. Seidel,

Spherical codes and designs,

Geometriae Dedicata 6 (1977) 363–388.

I found Hans’ notes to be particularly helpful, so I’m posting them here with his permission. I’ve lightly edited his notes for formatting and hyperlinks.

Without further ado:

Game of Sloanes

Emily King recently launched an online competition to find the best packings of points in complex projective space. The so-called Game of Sloanes is concerned with packing points in for and for . John Jasper, Emily King and I collaborated to make the baseline for this competition by curating various packings from the literature and then numerically optimizing sub-optimal packings. See our paper for more information:

J. Jasper, E. J. King, D. G. Mixon, Game of Sloanes: Best known packings in complex projective space

If you have a packing that improves upon the current leader board, you can submit your packing to the following email address:

asongofvectorsandangles [at] gmail [dot] com

In this competition, you can win money if you find a new packing that achieves equality in the Welch bound; see this paper for a survey of these so-called equiangular tight frames (ETFs).

Some news regarding the Paley graph

Let denote the field with elements, and let denote the multiplicative subgroup of quadratic residues. For each prime , we consider the Paley graph with vertex set , where two vertices are adjacent whenever their difference resides in . For example, the following illustration from Wikipedia depicts :

The purpose of this blog entry is to discuss recent observations regarding the Paley graph.

Polymath16, fourteenth thread: Automated graph minimization?

This is the fourteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The biggest development in the previous thread:

• The smallest known 5-chromatic unit distance graph has 510 vertices and 2508 edges.

The method used for finding this graph is vaguely described here and here. It seems that the method is currently more of an art form than an algorithm. A next step might be to automate the art away, code up any computational speedups that are available, and then throw more computing power at the problem.