Spectral bounds in extremal discrete geometry

• Applicant: Professor Dr. Frank Vallentin
• Subject Area: Mathematics
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 414898050

• Final Report Year: 2024

Final Report Abstract

The aim of the project was to study extremal structures in discrete geometry which optimize some given parameter, like for instance minimizing packing density, minimizing/maximizing potential energy, or finding a coloring with as few colors as possible. In particular we developed techniques based on spectral theory which are useful as obstructions. Then they can be used to prove that a given structure is indeed optimal. For this we considered the following concrete problems: How many regular tetrahedra can touch one point? How many colors are needed to color a given Riemannian space so that points at a prescribed set of distances receive different colors? Which lattices are critical points for a given potential energy? How to efficiently solve the closest vector problem in a special class of lattices whose Voronoi cells are zonotopes (orthogonal projections of regular cubes)? How can one extend existing spectral techniques from graphs to hypergraphs?

Publications

• A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces, 21 pages
  A. Heimendahl, M. Lücke, F. Vallentin & M.C. Zimmermann
  
• A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices. SIAM Journal on Discrete Mathematics, 35(4), 2345-2356.
  McCormick, S. Thomas; Peis, Britta; Scheidweiler, Robert & Vallentin, Frank
  
• Coloring the Voronoi tessellation of lattices. Journal of the London Mathematical Society, 104(3), 1135-1171.
  Dutour, Sikirić Mathieu; Madore, David A.; Moustrou, Philippe & Vallentin, Frank
  
• Semidefinite programming bounds for error-correcting codes, pages 267–281 in Concise Encyclopedia of Coding Theory (W.C. Huffman, J.-L. Kim, P. Solé (ed.)), CRC Press, 2021
  F. Vallentin
  
• A recursive Lovász theta number for simplex-avoiding sets. Proceedings of the American Mathematical Society, 150(8), 3307-3322.
  Castro-Silva, Davi; de Oliveira, Filho Fernando; Slot, Lucas & Vallentin, Frank
  
• Critical Even Unimodular Lattices in the Gaussian Core Model. International Mathematics Research Notices, 2023(6), 5352-5396.
  Heimendahl, Arne; Marafioti, Aurelio; Thiemeyer, Antonia; Vallentin, Frank & Zimmermann, Marc Christian
  
• The kissing number problem for regular tetrahedra, in: “Conic Linear Optimization for Computer-Assisted Proofs”. Abstracts from the workshop held April 10–16, 2022. Organized by D. Henrion, E. de Klerk, F. Vallentin, A. Wiegele, Oberwolfach Reports (2022)
  A. Spomer
  
• A Recursive Theta Body for Hypergraphs. Combinatorica, 43(5), 909-938.
  Castro-Silva, Davi; de Oliveira, Filho Fernando Mário; Slot, Lucas & Vallentin, Frank