Numbers, Information and Complexity
Numbers, Information and Complexity is a collection of about 50 articles in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, `Numbers and Combinations', `Information Theory (Channels and Networks, Combinatorial
- PDF / 55,532,030 Bytes
- 659 Pages / 595.252 x 790.854 pts Page_size
- 84 Downloads / 199 Views
Numbers, Information and Complexity Edited by
Ingo Althofer Friedrich Schiller-Universitiit lena
Ning Cai National University of Singapore
Gunter Dueck IBM Germany
Levon Khachatrian Universitiit Bielefeld
Mark S. Pinsker Russian Academy of Sciences
Andras Sarkozy EiHviis Lorand University
Ingo Wegener Universitiit Dortmund
and
ZhenZhang University of Southern California, Los Angeles
lI...
"
SPRINGER SCIENCE+BUSINESS MEDIA, LLC
A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4967-7 ISBN 978-1-4757-6048-4 (eBook) DOI 10.1007/978-1-4757-6048-4
Printed on acidjree paper
AU Rights Reserved © 2000 Springer Science+Business Media New York OriginaUy published by Kluwer Academic Publishers, Boston in 2000 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
Contents
Preface
XIII
Note: Survey articles, also those with some new results, are indicated by an
asterisk
NUMBERS AND COMBINATORICS 1 On Prefix-free and Suffix-free Sequences of Integers Rudolf Ahlswede, Levon H. Khachatrian, and Andras Sarkozy
1
2 Almost Arithmetic Progressions
17
Egbert Harzheim 3* A Method to Estimate Partial-Period Correlations
21
Aimo Tietiiviiinen 4 Splitting Properties in Partially Ordered Sets and Set Systems Rudolf Ahlswede and Levon H. Khachatrian
29
5* Old and New Results for the Weighted t-Intersection Problem via AKMethods
45
Christian Bey and Konrad Engel 6* Some New Results on Macaulay Posets
75
Sergei L. Bezrukov and Uwe Leck v
VI
7 Minimizing the Absolute Upper Shadow
95
Bela Bollobas and Imre Leader
8 Convex Bounds for the 0,1 Co-ordinate Deletions Function
101
David E. Daykin 9 The Extreme Points of the Probabilistic Capacities Cone Problem
105
David E. Daykin 10
109
On Shifts of Cascades
David E. Daykin 11* Erdos-Ko-Rado Theorems of Higher Order
117
Peter L. Erdos and Laszlo A. Szekely
12 On the Prague Dimension of Kneser Graphs
125
Zoltan Furedi
13* The cycle method and its limits
129
Gyula O.H. Katona
14* Extremal Problems on
Alexandr
v.
~-Systems
143
K ostochka
INFORMATION THEORY Channels and Networks 15 The AVC with Noiseless Feedback
Rudolf Ahlswede and Ning Cai
151
Contents
Vll
16
Calculation of the Asymptotically Optimal Capacity of aT-User MFrequency Noiseless Multiple-Access Channel Leonid Bassalygo and Mark Pinsker
177
17* A Survey of Coding Methods for the Adder Channel Gurgen H. Khachatrian
181
18* Communication Network with Self-Similar Traffic Boris Tsybakov
197
19 Error Probabilities for Identification Coding and Least Length Single Sequence Hopping Edward C. van der Meulen and Sandor Csibi
221
Combinatorial and Algebraic Coding 20
A New Upper Bound On Codes Decodable Into Size-2 Lists Alexei Ashikmin, Alexander Barg, and Simon Litsyn
239
21* Constructions of O
