Lecture Notes in Computer Science 2122 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Helmut Alt (Ed.) Computational Discrete Mathematics Advanced Lectures 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor HelmutAlt FreieUniversita¤tBerlin,Institutfu¤rInformatik Takustr.9,14195Berlin,Germany E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Computationaldiscretemathematics:advancedlectures/HelmutAlt(ed.).- Berlin;Heidelberg;NewYork;Barcelona;HongKong;London;Milan; Paris;Tokyo:Springer,2001 (Lecturenotesincomputerscience;2122) ISBN3-540-42775-9 CRSubjectClassi(cid:222)cation(1998):F.2,G.2,I.3.5 ISSN0302-9743 ISBN3-540-42775-9Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,speci(cid:222)callytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicro(cid:222)lmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de 'Springer-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyOlgunComputergra(cid:222)k Printedonacid-freepaper SPIN10839914 06/3142 543210 Preface In order to speed up doctoral education in Germany the “Deutsche Forschungs- gemeinschaft” (DFG, German Research Association) in the late 1980s devel- opedanewfundingconceptforgraduateprogramscalled“Graduiertenkollegs”. Groups of university teachers could join together and submit proposals for doc- toral studies within certain areas of research. If funded, the program would supply scholarships for doctoral students including means for travel, literature, scientificguests,meetings,andschools.Thescholarshipswouldallowdoctorands to concentrate on their doctoral studies without the usual teaching duties and to obtain their degree in a much shorter period of time. It was the idea of Martin Aigner to join efforts of mathematicians and com- puterscientistsinthenewlyreunifiedBerlinandtoapplyforagraduateprogram withindiscretemathematicsandtheoreticalcomputerscience.Thefinalproposal was submitted by researchers from the three universities of Berlin, Free Univer- sity, Humboldt-University, and Technical University, and the then still existing Academy of Sciences of the German Democratic Republic. The specific areas covered were geometric pattern recognition, constructive approximation, com- plexity theory, combinatorial optimization, graph theory, computational combi- natorics, coding theory, and group theory. The proposal was accepted by the DFG,theprogramwasnamed“AlgorithmischeDiskreteMathematik”(Compu- tational Discrete Mathematics), and Emo Welzl was elected as its first speaker. The program started with the first four doctorands on October 1st, 1991. The program was extended twice by the DFG and ended in September 2000 after the maximal possible runtime of nine years. Twenty-five of the students fundedobtainedtheirdoctoraldegree,mostofthemwithinatimeperiodsignif- icantlybelowaverageandmanyofthemevenwithinthestandardtwoandahalf years of funding by the program. All in all during the last years, discrete math- ematics and algorithmics in general have been flourishing within Berlin mainly due to the existence of the graduate program. In order to enhance contact and cooperation between the various research areas of the members of the program it had been decided at the beginning that there should be a weekly meeting on Monday afternoons during semesters. Part ofthismeetingconsistsofa60to90minutetutoriallecturebyfacultymembers of the program or selected guests. These lectures should be understandable not onlytospecialistsbuttoallmembersofresearchgroupsinvolvedintheprogram. Still, they should be at a high scientific level including recent research results within the different fields of the program. They have turned out to be very popular and very fruitful for all groups involved including the faculty members of the program who use the opportunity to learn about the research areas of their colleagues. In order to make the material of these lectures available to a larger public we created this booklet containing twelve selected lectures held within the graduate program. It covers the whole range of areas represented VI Preface in the program including combinatorics, graph theory, coding theory, discrete and computational geometry, optimization, and algorithmic aspects of algebra. Particularly intriguing are the nonobvious connections between different areas suchascombinatorics,linearalgebra,discretegeometry,andgraphtheoryinthe contributionbyMartinAigner;algebraiccomputingandgraphtheoryintheone by Gu¨nter Rote; or discrete geometry, graph theory, and coding theory in the one by Gu¨nter M. Ziegler. A preliminary version of this booklet was published internally on the day of celebration of the end of the old graduate program and the start of a new one called “Combinatorics, Geometry, and Computation” which is a European graduate program of the same research groups together with partners at ETH Zurich and other European institutions. Berlin, June 1, 2001 Helmut Alt Table of Contents Lattice Paths and Determinants ..................................... 1 Martin Aigner (Freie Universita¨t Berlin) The Nearest Neighbor .............................................. 13 Helmut Alt (Freie Universita¨t Berlin) Explicit and Implicit Enforcing – Randomized Optimization............. 25 Bernd Ga¨rtner and Emo Welzl (ETH Zu¨rich) Codes over Z4 ..................................................... 47 Tor Helleseth (University of Bergen) Degree Bounds for Long Paths and Cycles in k-connected Graphs ........ 56 Heinz Adolf Jung (Technische Universita¨t Berlin) Data Structures for Boolean Functions................................ 61 Christoph Meinel and Christian Stangier (Universita¨t Trier) Scheduling under Uncertainty: Bounding the Makespan Distribution...... 79 Rolf H. Mo¨hring (Technische Universita¨t Berlin) Random Graphs, Random Triangle-Free Graphs, and Random Partial Orders ......................................... 98 Hans Ju¨rgen Pro¨mel and Anusch Taraz (Humboldt–Universita¨t zu Berlin) Division-Free Algorithms for the Determinant and the Pfaffian: Algebraic and Combinatorial Approaches ............................. 119 Gu¨nter Rote (Freie Universita¨t Berlin) Check Character Systems and Anti–symmetric Mappings ............... 136 Ralph-Hardo Schulz (Freie Universita¨t Berlin) Algorithms in Pure Mathematics..................................... 148 Gernot Stroth (Martin-Luther-Universita¨t Halle Wittenberg) Coloring Hamming Graphs, Optimal Binary Codes, and the 0/1-Borsuk Problem in Low Dimensions ....................... 159 Gu¨nter M. Ziegler (Technische Universita¨t Berlin) Author Index ................................................. 173 Author Index Aigner, Martin 1 Rote, Gu¨nter 119 Alt, Helmut 13 Schulz, Ralph-Hardo 136 G¨artner, Bernd 25 Stangier, Christian 61 Stroth, Gernot 148 Helleseth, Tor 47 Jung, Heinz Adolf 56 Taraz, Anusch 98 Meinel, Christoph 61 Welzl, Emo 25 Mo¨hring, Rolf H. 79 Pr¨omel, Hans Ju¨rgen 98 Ziegler, Gu¨nter M. 159 Lattice Paths and Determinants Martin Aigner Department of Mathematics and Computer Science, Free University of Berlin Arnimallee 3, 14195 Berlin, Germany [email protected] The essence of mathematics is proving theorems – and so, that is what mathe- maticians do: they prove theorems. But to tell the truth, what they really want to prove once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the Burnside-Frobenius Lemma in combinatorics. Now what makes a mathematical statement a true Lemma? First, it should be applicable to a wide variety of instances, even seemingly unrelated problems. Secondly, the statement should, once you have seen it, be completely obvious. Thereactionofthereadermightwellbeoneoffaintenvy:Whyhaven’tInoticed this before? And thirdly, on an esthetic level, the Lemma including its proof should be beautiful! In this article we look at one such marvellous piece of mathematical reason- ing, the Lemma of Gessel and Viennot which has become an instant classic in combinatorial enumeration since its appearance in 1985 [1]. A similar version which was largely overlooked was previously obtained by Lindstr¨om [2]. 1 Four Problems Let us consider the following four problems which do not appear to have much in common – and yet they can all be solved by the Gessel–Viennot Lemma. A. The following curious problem was posed by Berlekamp and answered by Carlitz, Roselle and Scoville, see [4], p. 231. Suppose we are given a Young diagram D corresponding to the partition λ : n1n2...nt,n1 ≥ n2 ≥ ... ≥ nt. Given a square s of D, let (cid:7) be the lowest square in the same column as s, and r the rightmost square in the same row as s. Insert into s the number f(s) of paths from (cid:7) to r which stay inside D and use steps to the north and east only. Figure 1 shows the diagram of λ : 765532 and the numbers f(s). Consider the largest square matrix M contained in D. In the figure, the 4×4–matrix is drawn with bold lines. Problem. Prove that always detM =1. B. Everybody knows the Catalan numbers Cn, defined by the convolution recursion (cid:1)n C0 =1, Cn+1 = CkCn−k (n≥0). k=0 H.Alt(Ed.):ComputationalDiscreteMathematics,LNCS2122,pp.1–12,2001. (cid:2)c Springer-VerlagBerlinHeidelberg2001 2 Martin Aigner 142 46 16 7 2 1 1 47 16 6 3 1 1 19 7 3 2 1 5 2 1 1 1 2 1 1 1 1 Fig.1. Stanley lists in his admirable book [4] some 70 combinatorial instances which are counted by the Catalan numbers. One of the classical examples are Dyck paths of length 2n. These are lattice paths from (0,0) to (2n,0) which never go below the line y =0 and use only diagonal steps north–east or south–east. The number of these Dyck paths (of length 2n) is precisely Cn. The next figure shows the C3 =5 Dyck paths of length 6: Fig.2. One of the most elegant characterizations of the sequence (Cn) goes as fol- lows: Associate to (Cn) the Hankel matrices Hn and H(cid:2)n (n≥0), where     C C ... C C C ... C 0 1 n 1 2 n+1     C C ... C  C C ... C  Hn = 1 2 ... n+1 , H(cid:2)n = 2 3 ... n+2  .     C C ... C C C ... C n n+1 2n n+1 n+2 2n+1 Of course, we may associate such a pair of Hankel matrices to any sequence of real numbers. Problem. Prove that (Cn) is the unique sequence of real numbers such that detHn =detH(cid:2)n =1 for all n≥0. C. The Stirling numbers of the second kind Sn,k are defined as the number of partitions of an n-set into k blocks. A classical result states that the numbers Sn,k satisfy the recursion