Polymath16, seventeenth thread: Declaring victory

This is the seventeenth “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, we are finalizing a draft of a paper by D.H.J. Polymath. Like Aubrey’s original paper, this will be submitted for publication in Geombinatorics.

This post concludes the Polymath16 project. Of course, we anticipate that folks will continue to make progress on this problem on their own. If you’d like to update the Polymath16 community about your progress, feel free to comment on this post.

I asked Aubrey to offer a few words to reflect on our project:

Continue reading Polymath16, seventeenth thread: Declaring victory

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

We’re kicking off the spring semester on January 26 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 G=(A,B,E,k,w) consisting of

  • disjoint vertex sets A and B,
  • an edge set E\subseteq A\times B,
  • an edge coloring k\colon E\to\mathbb{N}, and
  • a complex vertex weighting w\colon A\to\mathbb{C}.
Continue reading A graph coloring problem from quantum physics (with prizes!)

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.

Update #2: Updated Chapter 1 and started Chapter 2.

Update #3: Added a section to Chapter 2.

Update #4: Added another section to Chapter 2.

Update #5: Added another section to Chapter 2.

Update #6: Added Chapter 3 and started Chapter 4.

Update #7: Updated Section 4.1.

Update #8: Added Section 4.2.

Update #9: Started Section 4.3.

Update #10: Added Section 4.4.

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 \mathrm{ETF}(d,n) denote the set of matrices A in \mathbb{C}^{d\times n} such that

\displaystyle|A^*A|^{2}=I_n+\frac{n-d}{d(n-1)}(J_n-I_n), \qquad AA^*=\frac{n}{d}I_d.

Here, * denotes conjugate transpose, |\cdot|^2 denotes entrywise squared modulus, I_k denotes the k\times k identity matrix, and J_k denotes the k\times k all-ones matrix. In words, the columns of A form an equiangular tight frame (ETF) for \mathbb{C}^d of size n.

Continue reading Kopp’s Whisky Prize

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:

Continue reading Spherical codes and designs

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 n points in \mathbf{CP}^{d-1} for d\in\{2,\ldots,7\} and for n\in\{d+2,\ldots,49\}. 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).

Continue reading Game of Sloanes

Some news regarding the Paley graph

Let \mathbb{F}_p denote the field with p elements, and let Q_p denote the multiplicative subgroup of quadratic residues. For each prime p\equiv 1\bmod 4, we consider the Paley graph G_p with vertex set \mathbb{F}_p, where two vertices are adjacent whenever their difference resides in Q_p. For example, the following illustration from Wikipedia depicts G_{13}:

800px-Paley13.svg

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

Continue reading Some news regarding the Paley graph