**Contemporary Mathematics**

Volume: 625;
2014;
190 pp;
Softcover

MSC: Primary 52; 05; 37; 94; 58;

**Print ISBN: 978-1-4704-0905-0
Product Code: CONM/625**

List Price: $83.00

AMS Member Price: $66.40

MAA Member Price: $74.70

**Electronic ISBN: 978-1-4704-1949-3
Product Code: CONM/625.E**

List Price: $78.00

AMS Member Price: $62.40

MAA Member Price: $70.20

# Discrete Geometry and Algebraic Combinatorics

Share this page *Edited by *
*Alexander Barg; Oleg R. Musin*

This volume contains the proceedings of the
AMS Special Session on Discrete Geometry and Algebraic Combinatorics
held on January 11, 2013, in San Diego, California.

The collection of articles in this volume is devoted to packings of
metric spaces and related questions, and contains new results as well
as surveys of some areas of discrete geometry. This volume consists of
papers on combinatorics of transportation polytopes, including results
on the diameter of graphs of such polytopes; the generalized Steiner
problem and related topics of the minimal fillings theory; a survey of
distance graphs and graphs of diameters, and a group of papers on
applications of algebraic combinatorics to packings of metric spaces
including sphere packings and topics in coding theory.

In particular, this volume presents a new approach to duality in
sphere packing based on the Poisson summation formula, applications of
semidefinite programming to spherical codes and equiangular lines, new
results in list decoding of a family of algebraic codes, and
constructions of bent and semi-bent functions.

#### Readership

Graduate students and research mathematicians interested in discrete geometry, sphere packing, coding theory, and semidefinite programming.

# Table of Contents

## Discrete Geometry and Algebraic Combinatorics

- Cover Cover11 free
- Title page iii4 free
- Contents v6 free
- Preface vii8 free
- Plank theorems via successive inradii 110 free
- Minimal fillings of finite metric spaces: The state of the art 918
- 1. Introduction: Length-Minimizing Connections 918
- 2. Combinatorial Definition of Minimal Filling 1221
- 3. Parametric Minimal Fillings 1322
- 4. Realization of Minimal Filling as a Minimal Network 1423
- 5. Minimal Parametric Fillings and Linear Programming 1625
- 6. Generalized Fillings 1625
- 7. Formula for the Weight of Minimal Filling 1726
- 8. Uniqueness Problem 1928
- 9. Minimal Fillings of Additive and Pseudo-Additive Spaces 2130
- 10. Examples of Minimal Fillings 2332
- 11. Ratios 2534
- 12. Generalizations for Infinite Sets 3140
- Acknowledgments 3342
- References 3342

- Combinatorics and geometry of transportation polytopes: An update 3746
- A Tree Sperner Lemma 7786
- Cliques and cycles in distance graphs and graphs of diameters 93102
- 1. Distance graphs: definitions and motivation 93102
- 2. Graphs of diameters: definitions and motivation 94103
- 3. What is the role of cliques and cycles in geometric graphs? 95104
- 4. Counting cliques in distance graphs and graphs of diameters 96105
- 5. Distance graphs with exponential chromatic numbers and without cliques or cycles 98107
- 6. The chromatic numbers of spheres 100109
- 7. Counterexamples to Borsuk’s conjecture on spheres of small radii 103112
- References 104113

- New bounds for equiangular lines 111120
- Formal duality and generalizations of the Poisson summation formula 123132
- On constructions of semi-bent functions from bent functions 141150
- Some remarks on multiplicity codes 155164
- Multivariate positive definite functions on spheres 177186
- Back Cover Back Cover1202