Lectures On Advances In Combinatorics

Preparing link to download Please wait... Download

E-Book Overview

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 Erd?s/Ko/Rado 1938, one of the oldest problems in combinatorial extremal theory, an answer to a question of Erd?s (1962) in combinatorial number theory "What is the maximal cardinality of a set of numbers smaller than n with no k+1 of its members pair wise relatively prime?", 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.

E-Book Content

Rudolf Ahlswede · Vladimir Blinovsky Lectures on Advances in Combinatorics Rudolf Ahlswede Vladimir Blinovsky Universit¨at Bielefeld Fakult¨at f¨ur Mathematik Universit¨atsstr. 25 33615 Bielefeld Germany [email protected] Institute of Information Transmission Problems Russian Academy of Sciences Bol’shoi karetnyi per. 19 127994 Moscow Russia [email protected] ISBN 978-3-540-78601-6 e-ISBN 978-3-540-78602-3 Library of Congress Control Number: 2008923540 Mathematics Subject Classification (2000): 05-XX, 11-XX, 40-XX, 52-XX, 68-XX, 94-XX c Springer-Verlag Berlin Heidelberg 2008 ° This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: WMXDesign GmbH, Heidelberg Printed on acid-free paper 987654321 springer.com Preface The lectures concentrate on highlights in Combinatorial (Chapters II and III) and Number Theoretical (Chapter IV) Extremal Theory, in particular on the solution of famous problems which were open for many decades. However, the organization of the lectures in six chapters does neither follow the historic developments nor the connections between ideas in several cases. With the specified auxiliary results in Chapter I on Probability Theory, Graph Theory, etc., all chapters can be read and taught independently of one another. In addition to the 16 lectures organized in 6 chapters of the main part of the book, there is supplementary material for most of them in the Appendix. In particular, there are applications and further exercises, research problems, conjectures, and even research programs. The followi