Bóna - A Walk Through Combinatorics: An introduction to Enumeration and Graph Theory

A Walk Through
Combinatorics

An introduction to Enumeration and Graph Theory

Second Edition

Mikls Bna

Department of Mathematics
University of Florida
USA

NEW JERSEY LONDON SINGAPORE BEIJING SHANGHAI HONGKONG TAIPEI CHENNAI

Published by

World Scientific Publishing Co. Pte. Ltd.

5 Toh Tuck Link, Singapore 596224

USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601

UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE

Library of Congress Cataloging-in-Publication Data

Bna, Mikls

A walk through combinatorics : an antroduction to enumeration and graph theory / Mikls Bna.
-- 2nd ed.
p. cm.

Includes bibliographical references and index.

ISBN 981-256-885-9 (alk. paper)

1. Combinatorial analysis. I. Title.

QA164.B66 2006

511'.6--dc22

2006048235

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library.

The graphic on the cover courtesy of Mr. Joseph Sciacca.

Copyright 2006 by World Scientific Publishing Co. Pte. Ltd.

All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.

Printed in Singapore by Mainland Press

To Linda
To Mikike, Benny and Vinnie

Foreword

The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include. There is no more-or-less canonical corpus as in such other subjects as number theory and complex variable theory. Mikls Bna has succeeded admirably in blending classic results that would be on anyone's list for inclusion in a textbook, a sprinkling of more advanced topics that are essential for further study of combinatorics, and a taste of recent work bringing the reader to the frontiers of current research. All three items are conveyed in an engaging style, with many interesting examples and exercises. A worthy feature of the book is the many exercises that come with complete solutions. There are also numerous exercises without solutions that can be assigned for homework.

Some relatively advanced topics covered by Bna include permutations with restricted cycle structure, the Matrix-Tree theorem, Ramsey theory (going well beyond the classical Ramsey's theorem for graphs), the probabilistic method, and the Mbius function of a partially ordered set. Any of these topics could be a springboard for a subsequent course or reading project which will further convince the student of the extraordinary richness, variety, depth, and applicability of combinatorics. The most unusual topic covered by Bna is pattern avoidance in permutations and the connection with stack sortable permutations. This is a relatively recent research area in which most of the work has been entirely elementary. An undergraduate student eager to do some original research has a good chance of making a worthwhile contribution in the area of pattern avoidance.

I only wish that when I was a student beginning to learn combinatorics there was a textbook available as attractive as Bna's. Students today are fortunate to be able to sample the treasures available herein.

Richard Stanley
Cambridge, Massachusetts
February 6, 2002

Preface

The best way to get to know Yosemite National Park is to walk through it, on many different paths. In the optimal case, the gorgeous sights provide ample compensation for our sore muscles. In this book, we intend to explain the basics of Combinatorics while walking through its beautiful results. Starting from our very first chapter, we will show numerous examples of what may be the most attractive feature of this field: that very simple tools can be very powerful at the same time. We will also show the other side of the coin, that is, that sometimes totally elementary-looking problems turn out to be unexpectedly deep, or even unknown.

This book is meant to be a textbook for an introductory combinatorics course that can take one or two semesters. We included a very extensive list of exercises, ranging in difficulty from routine to worthy of independent publication. In each section, we included exercises that contain material not explicitly discussed in the text before. We chose to do this to provide instructors with some extra choices if they want to shift the emphasis of their course.

It goes without saying that we covered the classics, that is, combinatorial choice problems, and graph theory. We included some more elaborate concepts, such as Ramsey theory, the Probabilistic Method, and Pattern Avoidance (the latter is probably a first of its kind). While we realize that we can only skim the surface of these areas, we believe they are interesting enough to catch the attention of some students, even at first sight. Most undergraduate students enroll in at most one Combinatorics course during their studies, therefore it is important that they see as many captivating examples as possible. It is in this spirit that we included two new chapters in the second edition, on Algorithms, and on Computational Complexity. We believe that the best undergraduate students, those who will get tothe end of the book, should be acquainted with the extremely intriguing questions that abound in these two areas.

We wrote this book as we believe that combinatorics, researching it, teaching it, learning it, is always fun. We hope that at the end of the walk, readers will agree.

****

Exercises that are thought to be significantly harder than average are marked by one or more + signs. An exercise with a single + sign is probably at the level of a harder homework problem. The difficulty level of an exercise with more than one + sign may be comparable to an independent publication.

We provide Supplementary Exercises without solutions at the end of each chapter. These typically include, but are not limited to, the easiest exercises in that chapter. A solution manual for the Supplementary Exercises is available for Instructors.

Acknowledgments

This book has been written while I was teaching Combinatorics at the University of Florida, and during my sabbatical at the University of Pennsylvania in the Fall of 2005. I am certainly indebted to the books I used in my teaching during this time. These were Introductory Combinatorics by Kenneth Bogarth, Enumerative Combinatorics I.-II by Richard Stanley, Matching Theory by Lszl Lovsz and Michael D. Plummer, and A Course in Combinatorics by J. H. van Lint and R. M. Wilson. The two new chapters of the second edition were certainly influenced by the books of which I learned the theory of algorithms and computation, namely Computational Complexity by Christos Papadimitriou, Introduction to the Theory of Computation by Michael Sipser, who taught me the subject in person, Algorithms and Complexity by Herbert Wilf, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Several exercises in the book come from my long history as a student mathematics competition participant. This includes various national and international contests, as well as the long-term contest run by the Hungarian student journal KMAL, and the Russian student journal Kvant.