Lectures on Advances in Combinatorics

by Ahlswede, Rudolf; Blinovsky, Vladimir

• ISBN13: 9783540786016
• ISBN10: 3540786015
• Format: Paperback
• Copyright: 2008-07-01
• Publisher: Springer Nature

Summary

"The main focus of these lectures is basis extremal problems and inequalities - two sides of the same coin. Additionally they prepare well for approaches and methods useful and applicable in a broader mathematical context." "Highlights of the book include a solution to the famous 4m-conjecture of Erdos/Ko/Rado 1938, one of the oldest problems in combinatorial extremal theory, an answer to a question of Erdos (1962) in combinatorial number theory "What is the maximal cardinality of a set of numbers smaller than a with no k+1 of its members pair wise relatively primer", and the discovery that the AD-inequality implies more general and sharper number theoretical inequalities than for instance Behrend's inequality." "Several concepts and problems in the book arise in response to or by rephrasing questions from information theory, computer science, statistical physics. The interdisciplinary character creates an atmosphere rich of incentives for new discoveries and lends Ars Combinatoria a special status in mathematics." "At the end of each chapter, problems are presented in addition to exercises and sometimes conjectures that can open a reader's eyes to new interconnections."--BOOK JACKET.

Author Biography

Rudolf Ahlswede, Professor emeritus of Bielefeld University, has been engaged in research projects to advance a ''General Theory of Information Transfer'' since his retirement in 2003. He is one of the leading experts in combinatorics, number theory and information theory and has been awarded international prizes and honours, for instance a Honorary Doctorate of the Russian Academy of Sciences in 2001, the Humboldt-Japan Society Senior Scientist Award 1998/99, a Paul Erd+¦s Monetary Award (with Levon Khachatrian) in 1996, the Claude-Elwood-Shannon-Award 2006 of the IEEE Information Theory Society. Since 2004 he has been a member of the European Academy of Sciences. Vladimir Blinovsky has been based at the Institute for Information Transmission Problems of the Russian Academy of Sciences, Moscow since 1981. His scientific interests include combinatorics, coding theory, probability theory, large deviations, and information theory, subjects he has taught in Russia, France, the USA, and Germany.

Table of Contents

Conventions and Auxiliary Results	p. 1
Intersection and Diametric Problems	p. 9
The Complete Intersection Theorem	p. 9
The Diametric Problem for Vertices in the Hamming Metric	p. 18
The Diametric Problem for Vertices in the Taxi Metric	p. 30
The Diametric Problem for Edges in Hamming Metric	p. 41
Words with Pairwise Common Letter	p. 49
Constant Distance Code Pairs	p. 52
Covering, Packing, and List Codes	p. 73
Covering and Packing of Hypergraphs	p. 73
Covering of Products of Graphs and Hypergraphs	p. 83
Multiple Packing	p. 89
List Decoding	p. 105
Higher Level and Dimension Constrained Extremal Problems	p. 125
Higher Level Extremal Problems	p. 125
Properties of Binary Sequences Over Reals	p. 135
LYM-Related AZ-Identities, Antichain Splittings and Correlation Inequalities	p. 151
LYM-Type Relations	p. 151
The Splitting Property	p. 158
Correlation Inequalities	p. 160
Basic Problems from Combinatorial Number Theory	p. 199
Solutions of Problems of P. Erdos	p. 199
Appendix	p. 225
References	p. 291
Index	p. 307
List of Symbols	p. 311
Table of Contents provided by Blackwell. All Rights Reserved.