a research blog by Dustin G. Mixon
Two years ago, Boris Alexeev emailed me a problem:
Let
. Suppose you have
distinct numbers in some field. Is it necessarily possible to arrange the numbers into an
matrix of full rank?
Boris’s problem was originally inspired by a linear algebra exam problem at Princeton: Is it possible arrange four distinct prime numbers in a rank-deficient 
Continue reading A neat application of the polynomial method
This is the eleventh “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.
Here’s a brief summary of the progress made in the previous thread:
– Let w(k) denote the supremum of w such that ![[0,w]\times\mathbb{R}](https://s0.wp.com/latex.php?latex=%5B0%2Cw%5D%5Ctimes%5Cmathbb%7BR%7D&bg=ffffff&fg=303030&s=0 "[0,w]\times\mathbb{R}")
Colorings that produce these lower bounds are depicted here. The upper bound for k=3 is given here.
– The largest known k-colorable disks for k=2,3,4,5 are depicted here.
Presumably, we can obtain descent upper bounds on w(4) by restricting (a finite subset of) the ring ![\mathbb{Z}[\omega_1,\omega_3,\omega_4]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BZ%7D%5B%5Comega_1%2C%5Comega_3%2C%5Comega_4%5D&bg=ffffff&fg=303030&s=0 "\mathbb{Z}[\omega_1,\omega_3,\omega_4]")
This is the fifth (and final) entry to summarize talks in the “boot camp” week of the program on Foundations of Data Science at the Simons Institute for the Theory of Computing, continuing this post. On Friday, we heard talks from Ilya Razenshteyn and Michael Kapralov. Below, I link videos and provide brief summaries of their talks.
Ilya Razenshteyn — Nearest Neighbor Methods
This is the fourth entry to summarize talks in the “boot camp” week of the program on Foundations of Data Science at the Simons Institute for the Theory of Computing, continuing this post. On Thursday, we heard talks from Santosh Vempala and Ilias Diakonikolas. Below, I link videos and provide brief summaries of their talks.
Santosh Vempala — High Dimensional Geometry and Concentration
This is the third entry to summarize talks in the “boot camp” week of the program on Foundations of Data Science at the Simons Institute for the Theory of Computing, continuing this post. On Wednesday, we heard talks from Fred Roosta and Will Fithian. Below, I link videos and provide brief summaries of their talks.
Fred Roosta — Stochastic Second-Order Optimization Methods
This is the second entry to summarize talks in the “boot camp” week of the program on Foundations of Data Science at the Simons Institute for the Theory of Computing, continuing this post. On Tuesday, we heard talks from Ken Clarkson, Rachel Ward, and Michael Mahoney. Below, I link videos and provide brief summaries of their talks.
Ken Clarkson — Sketching for Linear Algebra: Randomized Hadamard, Kernel Methods
This is the tenth “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.
Here’s a brief summary of the progress made in the previous thread:
– We have new results in the probabilistic formulation, namely, Proposition 36 and Lemmas 38 and 39.
– Jaan Parts refined Pritikin’s analysis to prove that every unit-distance graph with at most 24 vertices is 5-colorable, and every such graph with at most 6906 vertices is 6-colorable.
– Domotor, Frankl and Hubai showed that, if there exists a k-chromatic unit-distance graph with a bichromatic origin such that all its neighbors are in the upper half-plane and all their coordinates are rational, then CNP is at least k.
Continue reading Polymath16, tenth thread: Open SAT instances
