هندسه گسسته و ترکیب‌های جبری: جلسه ویژه Ams درباره هندسه گسسته و ترکیب‌های جبری ۱۱ ژانویه ۲۰۱۳ سن دیگو، کالیفرنیا (ریاضیات معاصر)

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, USA.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. Cover 1 Title page 4 Contents 6 Preface 8 Plank theorems via successive inradii 10 1. Introduction 10 2. Extensions to Successive Inradii 12 3. Proof of Theorem 2.1 13 4. Proof of Theorem 2.2 15 5. Proof of Corollary 2.3 15 6. The equivalence of Conjectures 1.2, ???, ???, ???, ???, and ??? 15 7. Conclusion 16 References 17 Minimal fillings of finite metric spaces: The state of the art 18 1. Introduction: Length-Minimizing Connections 18 2. Combinatorial Definition of Minimal Filling 21 3. Parametric Minimal Fillings 22 4. Realization of Minimal Filling as a Minimal Network 23 5. Minimal Parametric Fillings and Linear Programming 25 6. Generalized Fillings 25 7. Formula for the Weight of Minimal Filling 26 8. Uniqueness Problem 28 9. Minimal Fillings of Additive and Pseudo-Additive Spaces 30 10. Examples of Minimal Fillings 32 11. Ratios 34 12. Generalizations for Infinite Sets 40 Acknowledgments 42 References 42 Combinatorics and geometry of transportation polytopes: An update 46 1. Introduction 46 2. Classical transportation polytopes (2-ways) 47 3. Multi-way transportation polytopes 65 4. Further research directions and more open problems 75 Acknowlegements 78 References 78 A Tree Sperner Lemma 86 1. Introduction 86 2. A Tree Sperner Lemma 87 3. Metric Trees and Segmentations 90 4. KKM Covers of Trees 90 5. A Fixed Point Theorem for Finite Trees 93 6. Infinite Settings 96 7. A KKM Theorem for Cycles 99 References 100 Cliques and cycles in distance graphs and graphs of diameters 102 1. Distance graphs: definitions and motivation 102 2. Graphs of diameters: definitions and motivation 103 3. What is the role of cliques and cycles in geometric graphs? 104 4. Counting cliques in distance graphs and graphs of diameters 105 5. Distance graphs with exponential chromatic numbers and without cliques or cycles 107 6. The chromatic numbers of spheres 109 7. Counterexamples to Borsuk’s conjecture on spheres of small radii 112 References 113 New bounds for equiangular lines 120 1. Introduction 120 2. SDP bounds for equiangular lines 122 3. Tight spherical designs of harmonic index 4 and equiangular lines 124 References 129 Formal duality and generalizations of the Poisson summation formula 132 1. Introduction 132 2. Poisson summation formulas and duality 134 3. Examples 140 4. Structure theory in the cyclic case 142 5. Non-existence of some formal duals 145 6. Open questions 148 Acknowledgments 148 References 148 On constructions of semi-bent functions from bent functions 150 1. Introduction 150 2. Notation and preliminaries 152 3. Constructions of semi-bent functions from bent functions 154 4. Conclusion 161 References 161 Some remarks on multiplicity codes 164 1. Introduction 164 2. Multiplicity Codes 166 3. Decoding Univariate Multiplicity Codes 169 4. Decoding Multivariate Multiplicity Codes 171 5. Encoding 181 6. Discussion 182 7. Open Questions 183 Acknowledgements 184 References 184 Multivariate positive definite functions on spheres 186 1. Introduction 186 2. Gegenbauer polynomials and multivariate positive definite functions 187 3. An extension of the Schoenberg theorem 191 4. Positive definite functions in Rn 194 5. Upper bounds for spherical codes 195 References 198 Back Cover 202 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.