.
Number of notes  63 
last updated  18th July 2012 
report wrong/dead links  gmail knolopen 
Table of Contents

Notes
(usually new notes are added to the beginning of the section. If a note belongs to more than one category, we just put it in one of the categories.)
Generic Combinatorics
Description:
Class Notes are available in one pdf file or in separate files:
1st Class, 6/21/2004 (pdfhtml): Points in the plane; Games: on a chessboard, on even sets, on a pool table, and the divisor game; Ramsey numbers and ErdosRado arrow notation.
2nd Class, 6/22/2004 (pdfhtml): Games continued: dominoes and triominoes, Knight's trail, chocolate bar, and others; decision trees and strategy functions; Hamilton cycles, bipartite graphs.
3rd Class, 6/23/2004 (pdfhtml): Graph Theory: spanning trees, legal colorings, chromatic numbers; Jensen's inequality; Graphs without short cycles: KováriSósTurán theorem and a theorem by Erdos.
4th Class, 6/24/2004 (pdfhtml): Graph theory continued: edge and vertexconnectednees, Mengar's theorem; tiling puzzles; the game "Set" and Szemerédi's theorem, supermultiplicate functions.
5th Class, 6/25/2004 (pdfhtml): Density versions of coloring theorems, hypergraphs, Steiner triple systems, projective planes, Galois planes, the Fundamental Theorem of Projective Geometry.
6th Class, 6/28/2004 (pdf): NorthSouth game, number of unit distances in the plane < n3/2, max distance occurs = n times, fitting squares, tiliing rectangles by rectangles with at least one integer dimension.
7th Class, 6/30/2004 (pdf): Puzzles on lamp switches and prisoners, Fisherman's clubs, Ramsey theory.
8th Class, 7/2/2004 (pdf): Steiner triple systems, affine spaces, the order of a finite field, Euler's 36 officers problem.
9th Class, 7/7/2004 (pdf): Extremal set theory, Eventown and Oddtown, isotropic vectors and spaces.
10th Class, 7/9/2004 (pdf): CauchyHilbert matrix, Cauchy's functional equation and Hamel bases, some problems in elementary number theory, Ramsey theory.
11th Class, 7/13/2004 (pdf): Totally unimodular matrices, Latin squares, counting perfect matchings in a bipartite graph: the permanent, doubly stochastic matrices.
12th Class, 7/15/2004 (pdf): Constructive proofs of negative results in Ramsey theory, bipartite Ramsey theory, Hadamard matrices, orthogonal matrices, upper and lower density.
13th Class, 7/20/2004 (pdf): the GaleBerlekamp switching game.
14th Class, 7/22/2004 (pdf): Points in general position, pattern in proofs of inequalities using the linear algebra method, additional exercises in probability theory.
15th Class, 7/27/2004 (pdf): Bases for vector spaces of polynomials (and the cookie problem), projective representation of a graph.
16th Class, 7/29/2004 (pdf): Random variables, independenct events, conditional probability.
17th Class, 8/2/2004 (pdf): The Monty Hall paradox and the 2 envelope paradox, statistical vs linear independence, algorithms on conjuntive normal forms, algebraic coding theory.
18th Class, 8/4/2004 (pdf): Projective dimension of a graph continued, the MilnorThom theorem, implication of Warren's theorem.
19th Class, 8/6/2004 (pdf): Matrix rigidity, character tables.
20th Class, 8/9/2004 (pdf): Matrix rigidity continued.
21st Class, 8/11/2004 (pdf): Linear programming, Shannon capacity of a graph, Lovász's theta function.
22nd Class, 8/13/2004 (pdf): 0,1measures, signrigidity.
noteid: Lr5Ssn
Description:
noteid: Lr532L
Description:
Contents
?? Subsets paths and bitstrings
More on binomials
The principle of inclusion and exclusion
Permutations
Binomial identities
Unimodality and Sperner's theorem
Generating functions
Recurrence relations
Partition identities
The Catalan numbers
The Stirling numbers
Graphs
Eulerian trails
De Bruijn sequences
Latin squares
noteid: MHAicR
Description:
Set of notes from Graph theory & combinatorics (I) and (II) from matthew kahle's teaching page.
1:
Basic enumerative techniques: binomial and multinomial coefficients, bijective methods, generating functions, Catalan numbers, hook length formula
Introduction to graph theory: trees, Menger's theorem, max cutmin flow
Counting spanning trees: the matrixtree theorem
Deletion / contraction recurrence and the Tutte polynomial
Graph coloring: Brooks' theorem, BorsukUlam theorem and Lovasz's proof of the Kneser conjecture, Hadwiger conjecture, Hedetniemi's conjecture
Topological graph theory: Kuratowski's theorem for planar graphs, embedding graphs on other surfaces and the minor theorem, the 7color theorem for the torus and 6color theorem for the projective plane, proving a 5color theorem for planar graphs and a discussion of the 4color theorem
More topological graph theory: linklessly embeddable graphs, forbidden minors, the Colin de Verdiere parameter
The polynomial method: Dvir's proof of the finite field Kakeya conjecture (2008), Guth and Katz's resolution of the Erdos distinct distance problem (2010)
More on distance graphs: the unit distance problem, the chromatic number of the plane
Extremal combinatorics: introduction to Ramsey theory, Turan's theorem, set systems with restricted intersections
The probabilistic method: lower bounds in Ramsey theory, graphs with large girth and chromatic number, applications in discrete geometry
Expander graphs: random regular graphs, Cayley graphs over finite fields, Cheeger and Buser inequalities, applications of expanders
2:
The emphasis will be on geometric and topological combinatorics. The course will be aim to be almost completely self contained — there are no real prerequisites other than undergraduate linear algebra and modern algebra, although knowledge of basic graph theory and topology will be helpful. This class may be of particular interest to graduate students studying combinatorics, geometric group theory, algebraic geometry, or algebraic topology. We will survey some of the most important theorems in this rapidly developing area of combinatorics, pointing out many open problems along the away.
noteid: L0pB2f
Description:
noteid: Jyv3hg
Description:
noteid: IxYGdy
Description:
noteid: LtQvDn
Description:
These are informal lecture notes from the course Combinatorics for Computer Scientists
that was offered at Aarhus University in Spring 1995. As a textbook that covers many of the
topics we were interested in, we recommeneded:
noteid: JH7Y59
Description:
For most students, the first and often only area of mathematics in college is calculus. And it is true that calculus is the single most important field of mathematics, whose emergence in the 17th century signalled the birth of modern mathematics and was the key to the successful applications of mathematics in the sciences. But calculus (or analysis) is also very technical. It takes a lot of work even to introduce its fundamental notions like continuity or derivatives (after all, it took 2 centuries just to define these notions properly). To get a feeling for the power of its methods, say by describing one of its important applications in detail, takes years of study. If you want to become a mathematician, computer scientist, or engineer, this investment is necessary. But if your goal is to develop a feeling for what mathematics is all about, where is it that mathematical methods can be helpful, and what kind of questions do mathematicians work on, you may want to look for the answer in some other fields of mathematics. There are many success stories of applied mathematics outside calculus. A recent hot topic is mathematical cryptography, which is based on number theory (the study of positive integers 1,2,3,…), and is widely applied, among others, in computer security and electronic banking. Other important areas in applied mathematics include linear programming, coding theory, theory of computing. The mathematics in these applications is collectively called discrete mathematics. (“Discrete” here is used as the opposite of “continuous”; it is also often used in the more restrictive sense of “finite”.) The aim of this book is not to cover “discrete mathematics” in depth (it should be clear from the description above that such a task would be illdefined and impossible anyway). Rather, we discuss a number of selected results and methods, mostly from the areas of combinatorics, graph theory, and combinatorial geometry, with a little elementary number theory. At the same time, it is important to realize that mathematics cannot be done without proofs. Merely stating the facts, without saying something about why these facts are valid, would be terribly far from the spirit of mathematics and would make it impossible to give any idea about how it works. Thus, wherever possible, we’ll give the proofs of the theorems we state. Sometimes this is not possible; quite simple, elementary facts can be extremely difficult to prove, and some such proofs may take advanced courses to go through. In these cases, we’ll state at least that the proof is highly technical and goes beyond the scope of this book. Another important ingredient of mathematics is problem solving. You won’t be able to learn any mathematics without dirtying your hands and trying out the ideas you learn about in the solution of problems. To some, this may sound frightening, but in fact most people pursue this type of activity almost every day: everybody who plays a game of chess, or solves a puzzle, is solving discrete mathematical problems. The reader is strongly advised to answer the questions posed in the text and to go through the problems at the end of each chapter of this book. Treat it as puzzle solving, and if you find some idea that you come up with in the solution to play some role later, be satisfied that you are beginning to get the essence of how mathematics develops. We hope that we can illustrate that mathematics is a building, where results are built on earlier results, often going back to the great Greek mathematicians; that mathematics is alive, with more new ideas and more pressing unsolved problems than ever; and that mathematics is an art, where the beauty of ideas and methods is as important as their difficulty or applicability.
Contents:
1 Introduction……………………………………. 5
2 Let us count……………………………………. 7
2.1 A party…………………………………… 7
2.2 Sets and the like………………………….. 9
2.3 The number of subsets………………………. 12
2.4 Sequences…………………………………. 16
2.5 Permutations………………………………. 17
3 Induction………………………………………. 21
3.1 The sum of odd numbers……………………… 21
3.2 Subset counting revisited…………………… 23
3.3 Counting regions…………………………… 24
4 Counting subsets………………………………… 27
4.1 The number of ordered subsets……………….. 27
4.2 The number of subsets of a given size………… 28
4.3 The Binomial Theorem……………………….. 29
4.4 Distributing presents………………………. 30
4.5 Anagrams………………………………….. 32
4.6 Distributing money…………………………. 33
5 Pascal?s Triangle……………………………….. 35
5.1 Identities in the Pascal Triangle……………. 35
5.2 A bird?s eye view at the Pascal Triangle……… 38
6 Fibonacci numbers……………………………….. 45
6.1 Fibonacci?s exercise……………………….. 45
6.2 Lots of identities…………………………. 46
6.3 A formula for the Fibonacci numbers………….. 47
7 Combinatorial probability………………………… 51
7.1 Events and probabilities……………………. 51
7.2 Independent repetition of an experiment………. 52
7.3 The Law of Large Numbers……………………. 53
8 Integers, divisors, and primes……………………. 55
8.1 Divisibility of integers……………………. 55
8.2 Primes and their history……………………. 56
8.3 Factorization into primes…………………… 58
8.4 On the set of primes……………………….. 59
8.5 Fermat?s ?Little? Theorem…………………… 63
8.6 The Euclidean Algorithm…………………….. 64
8.7 Testing for primality………………………. 69
9 Graphs…………………………………………. 73
9.1 Even and odd degrees……………………….. 73
9.2 Paths, cycles, and connectivity……………… 77
10 Trees…………………………………………. 81
10.1 How to grow a tree………………………… 82
10.2 Rooted trees……………………………… 84
10.3 How many trees are there…………………… 84
10.4 How to store a tree……………………….. 85
11 Finding the optimum…………………………….. 93
11.1 Finding the best tree……………………… 93
11.2 Traveling Salesman………………………… 96
12 Matchings in graphs…………………………….. 98
12.1 A dancing problem…………………………. 98
12.2 Another matching problem……………………100
12.3 The main theorem…………………………..101
12.4 How to find a perfect matching………………104
12.5 Hamiltonian cycles…………………………107
13 Graph coloring………………………………….110
13.1 Coloring regions: an easy case………………110
14 A Connecticut class in King Arthur?s court…………114
15 A glimpse of cryptography………………………..117
15.1 Classical cryptography……………………..117
16 Onetime pads…………………………………..117
16.1 How to save the last move in chess…………..118
16.2 How to verify a password?without learning it….120
16.3 How to find these primes……………………120
16.4 Public key cryptography…………………….122
noteid: IRGTPB
Description:
This book does not assume any previous knowledge of combinatorics or discrete mathematics. Except
for a few items which can easily be skipped over and some of the material on “generating functions”
in Part IV, calculus is not required. What is required is a certain level of ability or “sophistication”
in dealing with mathematical concepts. The level of mathematical sophistication that is needed is
about the same as that required in a solid beginning calculus course.
You may have noticed similarities and differences in how you think about various fields of
mathematics such as algebra and geometry. In fact, you may have found some areas more interesting
or more difficult than others partially because of the different thought patterns required. The field
of combinatorics will also require you to develop some new thought patterns. This can sometimes
be a difficult and frustrating process. Here is where patience, mathematical sophistication and a
willingness to ask “stupid questions” can all be helpful.
Combinatorics differs as much from mathematics you are likely to have studied previously as
algebra differs from geometry. Some people find this disorienting and others find it fascinating. The
introductions to the parts and to the chapters can help you orient yourself as you learn about
combinatorics. Don’t skip them.
Because of the newness of much of combinatorics, a significant portion of the material in this text
was only discovered in this generation. Some of the material is closely related to current research.
In contrast, the other mathematics courses you have had so far probably contained little if anything
that was not known in the Nineteenth Century. Welcome to the frontiers!
noteid: IRHikO
Description:
Contents:
D0 Introduction to counting problems
D1 Selection and Binomial Coefficients
D2 Properties of Binomial Coefficients
D3 Multisets and Multinomial Coefficients
D4 Counting grid paths and the ballot problem
D5 The pigeonhole principle
D6 Discrete Probability 1: Events
D7 Discrete Probability 2: Boole's Inequality
D8 Discrete Probability 3: Conditional Probability
D9 Discrete Probability 4: Random Variables
D10 Discrete Probability 5: Inequalities
D11 Recurrence Relations 1: Linear Recurrences
D12 Recurrence Relations 2: Divide and Conquer
D13 Recurrence Relations 3: Partitions of sets
D14 Recurrence Relations 4: Derangements
D15 Recurrence Relations 5: Generating Functions
D16 InclusionExclusion
D17 Graph Theory 1: Definitions
D18 Graph Theory 2: Paths, Walks and Bipartite Graphs
D19 Graph Theory 3: Trees
D20 Graph Theory 4: Euler tours and Hamilton cycles
D21 Graph Theory 5: Matchings
D22 Graph Theory 6: Ramsey Theory
D23 Graph Theory 7: Digraphs
noteid: KAZySG
Description:
Our approach to the course is to show students the beauty of combinatorics and how combinatorial problems naturally arise in many settings, particularly in computer science. While proofs are periodically presented in class, the course is not intended to teach students how to write proofs; there are other required courses in our curriculum that meet this need. Students may occasionally be asked to prove small facts, but these arguments are closer to the kind we expect from students in second or third semester calculus as contrasted with proofs we expect from a mathematics major in an upper division course. Regardless, we cut very few corners, and our text can readily be used by instructors who elect to be even more rigorous in their approach. This book arose from our feeling that a text that met our approach to Applied Com binatorics was not available. Because of the diverse set of instructors assigned to the course, the standard text was one that covered every topic imaginable (and then some), but provided little depth. We’ve taken a different approach, attacking the central sub jects of the course description to provide exposure, but taking the time to go into greater depth in select areas to give the students a better feel for how combinatorics works.
noteid: ICDg3G
Description:
A quick and beautiful introduction at upper undergraduate level.
Contents:
Basic Counting
Recurrence Relations and Generating Functions
Probabilistic Method
Some Extremal Problems
The Pigeon Hole Principle
Ramsey Theory
Partially Ordered Sets
Combinatorial Games
Polya Theory of Counting
Graph Theory
Discrete Probability
noteid: ICD4BE
Generic Graph theory
Description:
In this survey, we give a friendly introduction from a graph theory perspective to the qstate
Potts model, an important statistical mechanics tool for analyzing complex systems in which
nearest neighbor interactions determine the aggregate behavior of the system. We present the
surprising equivalence of the Potts model partition function and one of the most renowned
graph invariants, the Tutte polynomial, a relationship that has resulted in a remarkable synergy
between the two fields of study. We highlight some of these interconnections, such as com
putational complexity results that have alternated between the two fields. The Potts model
captures the effect of temperature on the system and plays an important role in the study of
thermodynamic phase transitions. We discuss the equivalence of the chromatic polynomial and
the zerotemperature antiferromagnetic partition function, and how this has led to the study
of the complex zeros of these functions. We also brie?y describe Monte Carlo simulations com
monly used for Potts model analysis of complex systems. The Potts model has applications as
widely varied as magnetism, tumor migration, foam behaviors, and social demographics, and
we provide a sampling of these that also demonstrates some variations of the Potts model. We
conclude with some current areas of investigation that emphasize graph theoretic approaches.
Keywords: Statistical Mechanics, Tutte Polynomial, Potts Model, Ising Model, Monte Carlo Simulation, Chromatic Polynomial.
noteid: NtNnDH
Description:
chapter 1 in combinatorics handbook.
Our purpose in this chapter is twofold: to introduce the basic concepts and techniques of graph theory, and to develop that part of the theory concerned with paths and circuits. We have attempted to weave these two strands together, proceeding from fundamental notions and elementary observations to more sophisticated concepts and methods, much as one does when engaged in research. One of the attractive features of the subject is the wealth of simply stated but challenging open problems, and we have included a large number of these. It must be emphasized that the literature on paths and circuits is extensive. Thus what is presented here is necessarily a selection. Nevertheless, our hope is that, after studying this chapter, the reader will be well equipped to embark on the chapters dealing with particular aspects of graph theory. Circuits in graphs are treated in depth in the books of Walther and Voss (1974) and Voss (1991). There are also many survey articles on particular aspects of the topic. We recommend, in particular, the articles of Carsten Thomassen. Besides their substantial contributions to the theory of graphs, each includes an informed and stimulating discussion of the question under consideration and its links to related matters.
Contents
Contents
1. Basic concepts 5
1.1. Graphs 5
1.2. Subgraphs and minors 7
1.3. Walks 9
1.4. Connection 9
1.5. Extremal graphs 11
1.6. Search trees 12
1.7. Directed graphs 15
1.8. Hypergraphs 18
2. Hamilton paths and circuits in graphs 20
2.1. Dirac's theorem 20
2.2. Generalizations of Dirac's theorem 23
3. Hamilton paths and circuits in digraphs 28
3.1. Redei's theorem 28
3.2. Generalizations of Redei's theorem 29
4. Fundamental parameters 33
4.1. Connectivity and edge connectivity 34
4.2. Stability number 40
4.3. Matching number 46
4.4. Chromatic number and edge chromatic number 48
4.5. Toughness 51
5. Fundamental classes of graphs and digraphs 54
5.1. Bipartite graphs 54
5.2. Planar graphs 55
5.3. Regular graphs and vertextransitive graphs 59
5.4. Line graphs and clawfree graphs 65
5.5. Oriented graphs and tournaments 67
Contents
1. Basic concepts 5
1.1. Graphs 5
1.2. Subgraphs and minors 7
1.3. Walks 9
1.4. Connection 9
1.5. Extremal graphs 11
1.6. Search trees 12
1.7. Directed graphs 15
1.8. Hypergraphs 18
2. Hamilton paths and circuits in graphs 20
2.1. Dirac's theorem 20
2.2. Generalizations of Dirac's theorem 23
3. Hamilton paths and circuits in digraphs 28
3.1. Redei's theorem 28
3.2. Generalizations of Redei's theorem 29
4. Fundamental parameters 33
4.1. Connectivity and edge connectivity 34
4.2. Stability number 40
4.3. Matching number 46
4.4. Chromatic number and edge chromatic number 48
4.5. Toughness 51
5. Fundamental classes of graphs and digraphs 54
5.1. Bipartite graphs 54
5.2. Planar graphs 55
5.3. Regular graphs and vertextransitive graphs 59
5.4. Line graphs and clawfree graphs 65
5.5. Oriented graphs and tournaments 67
6. Special proof techniques for paths and circuits 69
6.1. Thomason's lemma 69
6.2. Posa's lemma 70
6.3. Woodall's hopping lemma 72
7. Lengths of circuits 74
7.1. Circuits of given length modulo k 75
7.2. Circuits of given length 76
7.3. Circuits of many lengths 77
7.4. Circuits of all lengths 77
7.5. The number of circuits 78
8. Packings and coverings by paths and circuits 80
8.1. Packings and coverings of hypergraphs 80
8.2. Packings by paths and circuits 81
8.3. Coverings by circuits 84
8.4. Partitions into paths and circuits 85
8.5. Decompositions into paths and circuits 86
8.6. Decompositions into Hamilton circuits 88
8.7. Compatible circuit decompositions 90
8.8. Double covers 91
References 94
noteid: Pdeczr
Description:
A path or cycle in an edgecoloured multigraph is called alternating if its successive edges differ in colour. We survey results of both theoretical and algorithmic character concerning alternating cycles and paths in edgecoloured multigraphs. We also show useful connections between the theory of paths and cycles in bipartite digraphs and the theory of alternating paths and cycles in edgecoloured graphs.
noteid: MKlm0B
Description:
In this paper, we present a survey of the use of graph theoretical techniques in Biology. In
particular, we discuss recent work on identifying and modelling the structure of biomolecular
networks, as well as the application of centrality measures to interaction networks and research
on the hierarchical structure of such networks and network motifs. Work on the link between
structural network properties and dynamics is also described, with emphasis on synchronization
and disease propagation.
noteid: JYpXcC
Description:
Abstract. We survey some recent results on longstanding conjectures regard ing Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly’s conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are ‘almost’ edgedisjoint. We also highlight the role that the notion of ‘robust expansion’ plays in several of the proofs. New and old open problems are discussed.
noteid: JyndEp
Description:
noteid: Kem95C
Description:
noteid: IQGOZK
Description:
This is a required class in the PhD program in Algorithms, Combinatorics and Optimization. The objective is to provide rigorous treatment of Graph Theory at the level of an introductory graduate course. You do not need to know much about Graph Theory, but you do need the mathematical sophistication of a beginning mathematics graduate student in order to succeed in the course. You will be required to write rigorous mathematical proofs of nontrivial results. In addition to mathematical correctness attention will be paid to writing in an elegant and aesthetically pleasing way. An assignment will be due approximately every two weeks. Thus, in addition to learning Graph Theory, you will get to practice and improve your proofwriting skills. See the links below for sample problems you will be required to solve.
Fundamentals, Matching, Connectivity, Planar graphs, Coloring, Extremal Problems, Ramsey Theory, Random Graphs.
noteid: IDL2Hr
Description:
Table of Contents
1
Introduction … … … … … … … … … … … … … … … … … … … .
2
1.1 Graphs and their plane figures… … … … … … … … … … … … . .
4
1.2 Subgraphs … … … … … … … … … … … … … … … … … … . .
7
1.3 Paths and cycles … … … … … … … … … … … … … … … … …
11
2
Connectivity of Graphs … … … … … … … … … … … … … … … …
16
2.1 Bipartite graphs and trees … … … … … … … … … … … … … …
16
2.2 Connectivity … … … … … … … … … … … … … … … … … …
23
3
Tours and Matchings … … … … … … … … … … … … … … … … . .
29
3.1 Eulerian graphs … … … … … … … … … … … … … … … … …
29
3.2 Hamiltonian graphs … … … … … … … … … … … … … … … . .
31
3.3 Matchings … … … … … … … … … … … … … … … … … … . .
35
4
Colourings … … … … … … … … … … … … … … … … … … … …
43
4.1 Edge colourings … … … … … … … … … … … … … … … … …
43
4.2 Ramsey Theory… … … … … … … … … … … … … … … … … .
47
4.3 Vertex colourings … … … … … … … … … … … … … … … … . .
53
5
Graphs on Surfaces… … … … … … … … … … … … … … … … … .
61
5.1 Planar graphs … … … … … … … … … … … … … … … … … . .
61
5.2 Colouring planar graphs … … … … … … … … … … … … … … .
68
5.3 Genus of a graph … … … … … … … … … … … … … … … … . .
76
6
Directed Graphs… … … … … … … … … … … … … … … … … … .
84
6.1 Digraphs… … … … … … … … … … … … … … … … … … … .
84
6.2 Network Flows … … … … … … … … … … … … … … … … … .
90
Index … … … … … … … … … … … … … … … … … … … … … … …
97
noteid: IDL5D7
Description:
Table of Contents
GRAPH THEORY
by
Ronald J. Gould
Emory University
Chapter 1 Graphs
1.0 Introduction
1
1.1 Fundamental Concepts and Notation
1
1.2 Elementary Properties and Operations
8
1.3 Alternate Representations for Graphs
14
1.4 Algorithms
16
1.5 Degree Sequences
19
1.6 Fundamental Counting
25
Chapter 2 Paths and Searching
2.1 Distance
33
2.2 Connectivity
47
2.3 Digraph Connectivity
56
2.4 Problem Solving and Heuristics
59
Chapter 3 Trees
3.1 Fundamental Properties of Trees
69
3.2 Minimal Weight Spanning Trees
71
3.3 Counting Trees
76
3.4 Directed Trees
80
3.5 Optimal Directed Subgraphs
86
3.6 Binary Trees
90
3.7 More About CountingUsing Generating Functions
99
Chapter 4 Networks
4.1 Flows
105
4.2 The Ford and Fulkerson Approach
107
4.3 The Dinic Algorithm and Layered Networks
114
4.4 Layered Networks and Potential
118
4.5 Variations on Networks
119
4.6 Connectivity and Networks
124
Chapter 5 Cycles and Circuits
5.1 Eulerian Graphs
133
5.2 Adjacency Conditions for Hamiltonian Graphs
139
5.3 Related Hamiltonianlike Properties
148
5.4 Forbidden Subgraphs
151
5.5 Other Types of Hamiltonian Results
155
5.6 The Traveling Salesman Problem
157
5.7 Short Cycles and Girth
159
5.8 Disjoint Cycles
162
Chapter 6 Planarity
6.1 Euler’s Formula
173
6.2 Characterizations of Planar Graphs
176
6.3 A Planarity Algorithm
186
6.4 The HopcroftTarjan Planarity Algorithm
190
6.5 Hamiltonian Planar Graphs
198
Chapter 7 Matchings and rFactors
7.0 Intorduction
203
7.1 Matchings and Bipartite Graphs
203
7.2 Matching Algorithms and Marriage
209
7.3 Factoring
221
7.4 Degrees and 2Factors
227
Chapter 8 Independence
8.1 Vertex Independence and Coverings
235
8.2 Vertex Colorings
237
8.3 Approximate Coloring Algorithms
242
8.4 Edge Colorings
248
8.5 The Four Color Theorem
252
8.6 Chromatic Polynomials
254
8.7 Perfect Graphs
256
Chapter 9 Special Topics and Applications
9.1 Graphs and Ordered Sets
265
9.2 Random Graphs
270
9.3 Ramsey Theory
276
9.4 Finite State Machines
282
9.5 Scheduling
287
9.6 Tournaments
293
Chapter 10 Extremal Theory
10.0 Introduction
305
10.1 Complete Subgraphs
306
10.2 Cycles in Graphs
314
10.3 On the Structure of Extremal Graphs
319
noteid: IDL967
Description:
This is a set of lecture notes for Math 485{Penn State's undergraduate Graph Theory course. Since I use these notes while I teach, there may be typographical errors that I noticed in class, but did not fix in the notes. If you see a typo, send me an email and I'll add an acknowledgement. There may be many typos, that's why you should have a real textbook. The lecture notes are loosely based on Gross and Yellen's Graph Theory and It's Applications, Bollobas's Graph Theory, Diestel's Graph Theory, Wolsey and Nemhauser's Integer and Combinatorial Optimization, Korte and Vygen's Combinatorial Optimization and several other books that are cited in these notes. All of the books mentioned are good books (some great). The problem is, they are either too complex for an introductory undergraduate course, have odd notation, do not focus enough on applications or focus too much on applications.
This set of notes correct some of the problems I mention by presenting the material in a format for that can be used easily in an undergraduate mathematics class. Many of the proofs in this set of notes are adapted from the textbooks with some minor additions. One thing that is included in these notes is a treatment of graph duality theorems from the perspective linear optimization. This is not covered in most graph theory books, while graph theoretic principles are not covered in many linear or combinatorial optimization books. I should note, Bondy and Murty discuss Linear Programming in their book Graph Theory, but it is clear they are not experts in optimization and their treatment is somewhat non sequitur, which is a shame. The best book on the topic of combinatorial optimization is by far Korte and Vygen's, who do cover linear programming in their latest edition. Note: Penn State has an expert in graph coloring problems, so there is no section on coloring in these notes, because I invited a guest lecturer who was the expert. I may add a section on graph coloring eventually.
In order to use these notes successfully, you should have taken a course in combinatorial proof (Math 311W at Penn State) and ideally matrix algebra (Math 220 at Penn State), though courses in Linear Programming (Math 484 at Penn State) wouldn't hurt. I review a substantial amount of the material you will need, but it's always good to have covered prerequisites before you get to a class. That being said, I hope you enjoy using these notes!
Contents:
Chapter 1. Preface and Introduction to Graph Theory 1
1. Some History of Graph Theory and Its Branches 1
2. A Little Note on Network Science 3
Chapter 2. Some Definitions and Theorems 5
1. Graphs, MultiGraphs, Simple Graphs 5
2. Directed Graphs 8
3. Elementary Graph Properties: Degrees and Degree Sequences 10
4. Subgraphs 16
5. Graph Complement, Cliques and Independent Sets 17
Chapter 3. More Definitions and Theorems 21
1. Paths, Walks, and Cycles 21
2. More Graph Properties: Diameter, Radius, Circumference, Girth 23
3. More on Trails and Cycles 24
4. Graph Components 26
5. Bipartite Graphs 30
6. Acyclic Graphs and Trees 31
Chapter 4. Some Algebraic Graph Theory 39
1. Isomorphism and Automorphism 39
2. Fields and Matrices 45
3. Special Matrices and Vectors 47
4. Matrix Representations of Graphs 47
5. Determinants, Eigenvalue and Eigenvectors 50
6. Properties of the Eigenvalues of the Adjacency Matrix 53
Chapter 5. Applications of Algebraic Graph Theory: Eigenvector Centrality and
PageRank 57
1. Basis of Rn 57
2. Eigenvector Centrality 59
3. Markov Chains and Random Walks 62
4. Page Rank 65
Chapter 6. Trees, Algorithms and Matroids 69
1. Two Tree Search Algorithms 69
2. Prim's Spanning Tree Algorithm 71
3. Computational Complexity of Prim's Algorithm 75
4. Kruskal's Algorithm 77
5. Shortest Path Problem in a Positively Weighted Graph 79
6. Greedy Algorithms and Matroids 83
Chapter 7. A Brief Introduction to Linear Programming 87
1. Linear Programming: Notation 87
2. Intuitive Solutions of Linear Programming Problems 88
3. Some Basic Facts about Linear Programming Problems 91
4. Solving Linear Programming Problems with a Computer 94
5. KurushKuhnTucker (KKT) Conditions 96
6. Duality 99
Chapter 8. An Introduction to Network Flows and Combinatorial Optimization 105
1. The Maximum Flow Problem 105
2. The Dual of the Flow Maximization Problem 106
3. The MaxFlow / MinCut Theorem 108
4. An Algorithm for Finding Optimal Flow 111
5. Applications of the Max Flow / Min Cut Theorem 115
Chapter 9. A Short Introduction to Random Graphs 119
1. Bernoulli Random Graphs 119
2. First Order Graph Language and 0 ?? 1 properties 122
3. ErdosRenyi Random Graphs 123
Chapter 10. Some More Algebraic Graph Theory 129
1. Vector Spaces and Linear Transformation 129
2. Linear Span and Basis 131
3. Vector Spaces of a Graph 132
4. Cycle Space 133
5. Cut Space 136
6. The Relation of Cycle Space to Cut Space 139
Bibliography 141
noteid: IDLfKK
Description:
This course will make students familiar with useful techniques in graph theory and show what the applications of these techniques are. Supporting material will be added to this page each week.
The main reference for this course is the online textbook Graph Theory with Applications by Bondy and Murty. Lecture notes are available below, but they only contain an overview of the classes—attendance is essential.
Week 1: Introduction
What is graph theory useful for?
Examples of graphs—directed, undirected, acyclic, complete, bipartite.
Incidence and adjacency.
Example application: shortest path problem.
Example application: three houses problem.
Example application: matching jobs to applicants.
Useful glossary page (Wikipedia).
Lecture notes
Week 2: Trees
Application: planning an efficient road network.
Definition of trees.
Properties of trees: number of edges and vertices, degree of vertices, cut edges.
Spanning trees.
Kruskal's algorithm.
Lecture notes
Week 3: Connectivity
Cayley's formula.
Cut vertices, vertex cuts, edge cuts.
Blocks; the block detection algorithm challenge.
Connectivity and edgeconnectivity.
Application: designing resilient computer networks.
Lecture notes
Week 4: Euler tours and Chinese postmen
The seven bridges of Königsberg
Conditions for Eulerian graphs
The Chinese postman problem
Fleury's algorithm
Hamilton paths
Lecture notes
Week 5: Matchings and coverings
Matches, perfect matches, matches in bipartite graphs
Personnel assigment problem
Hall's theorem
The marriage theorem
The GaleShapley algorithm
Lecture notes
Week 6: Edge colourings
Proper colourings, edge chromaticity
Timetabling problem
Lecture notes
Assignment 1
Week 7: Directed graphs
Orientations of an undirected graph
Tournaments
Euler tours in digraphs
Application: rotational position sensor
Into to graphical models
Lecture notes
(no class week 8.)
Week 9: Message passing
Message passing rules for counting vertices
Separability
Counting paths through a grid
Viterbi (mincut) algorithm
Lecture notes
Week 10: Probabilistic graphical models
Dependence/conditional dependence/conditional independence
Observed and latent variables
Marginalisation and inference
Lecture notes
Week 13: Network flow
Flow/resultant flow
Network cuts
Maxflow mincut
The FordFulkerson algorithm
Lecture notes
noteid: IDLtS9
Extremal Combinatorics and Graph theory
Description:
Program
1 The problem of forbidden subgraphs.
The famous Turan theorem.
2 The fundamental ErdosStone theorem.
The Regularity Lemma
3 Extremal problems for paths and cycles
4 Extremal problems on the order
5 Extremal problems on connectivity
6 Some extremal exercises.
noteid: NsX8a8
Description:
This paper surveys various results concerning the problem of forbidden config
urations (also known as trace in the language of set systems).
Let F be a k X (0,1)matrix (the forbidden configuration).
We define a matrix to be simple if it is a (0,1)matrix with no repeated columns. The matrix
F need not be simple. We define forb(m,F) as the maximum number of columns
of any simple mrowed matrix A which do not contain F as a configuration.
Thus if A is an m × n simple matrix which has no submatrix which is a row
and column permutation of F then n = forb(m,F). Or alternatively if A is an
m × (forb(m,F) + 1) simple matrix then A has a submatrix which is a row and
column permutation of F. Perhaps the most fundamental result is due to Sauer,
Perles and Shelah, Vapnik and Chervonenkis but there are many other results
catalogued here. In the language of sets, a configuration is a trace.
We seek exact values for forb(m,F) as well as seeking asymptotic results for
forb(m,F) for a fixed F and as m tends to infinity.
A conjecture of Anstee and Sali predicts the asymptotically best constructions from which to derive the asymptotics of forb(m,F). This conjecture has helped guide the research and has
been verified for k× lF with k = 1,2,3, with l = 1,2 and for simple F with k = 4
as well as other cases.
noteid: KqWvhw
Description:
Rough Outline
9/7
Ramsey’s theorem and its applications
9/12 Hypergraph Ramsey numbers I
9/14 Hypergraph Ramsey numbers II
9/19 Theorems of van der Waerden, HalesJewett, and Szemerédi
9/21 Student holiday – no class
9/26 Turán’s theorem and its applications
9/28 ErdosStoneSimonovits theorem
10/3 Bipartite Turán problems, algebraic constructions
10/5 Szemerédi’s regularity lemma, statement and proof
10/10 Columbus day – no class
10/12 Applications I  graph removal lemma, (6,3)theorem, Roth’s theorem,
AjtaiSzemerédi corner theorem
10/17 Roth’s theorem – proof using Fourier analysis
10/19 Applications II  Ramsey numbers of bounded degree graphs, induced
Ramsey theorem
10/24 Hypergraph regularity, removal, and the multidimensional Szemerédi
theorem
10/26 Weak regularity lemmas and algorithmic aspects
10/31 Property testing I
11/2 Property testing II
11/7 Sunflower lemma
11/9 LYM inequality, Sperner’s theorem, and LittlewoodOfford theorem
11/14 SauerShelah and KruskalKatona
11/16 Linear algebra in extremal set theory: Odd and even towns, Fisher’s
inequality, RayChaudhuriWilson theorem
11/21 Twodistance sets, GrahamPollack
11/23 modular intersection theorems and the chromatic number of nspace
11/28 FranklWilson theorem, constructive lower bounds for Ramsey numbers,
and Borsuk’s conjecture.
11/30 Dvir’s proof of the finite field Kakeya problem, the joints problem
12/5 Combinatorial Nullstellansatz – statement and proof, CauchyDavenport,
ChevalleyWarning
12/7 Restricted sums
12/12 Regular subgraphs, covering cubes
12/14 Graph coloring
noteid: JYnZZu
Description:
noteid: JyrK9N
Description:
1 Prologue 7
1.1 Apologies … … … … … … … … … … . 7
1.2 Thanks … … … … … … … … … … . . 7
2 Introduction to Extremal Graph Theory 9
2.1 Notation and terminology … … … … … … … . 10
2.1.1 General mathematical notation … … … … … 10
2.1.2 Graph theory notation … … … … … … . . 10
2.1.3 Some special graph families … … … … … . . 11
2.1.4 Useful bounds … … … … … … … … . 11
3 The Basics 13
3.1 KonigHall theorem … … … … … … … … . . 13
3.1.4 Equivalent theorems … … … … … … … 15
3.2 Tutte's theorem … … … … … … … … … . 17
3.3 Turan's theorem … … … … … … … … … 18
3.4 Konigsberg … … … … … … … … … … 20
3.5 Dirac's theorem … … … … … … … … … . 20
3.6 The HajnalSzemeredi theorem … … … … … … . 21
3.7 Gems: The HomanSingleton theorem … … … … . . 26
4 Ramsey Theory 31
4.1 Basic Ramsey theory … … … … … … … … . 31
4.1.4 Innite Ramsey theory … … … … … … . . 32
4.2 Canonical Ramsey theory … … … … … … … . 33
4.2.2 Innite version … … … … … … … … 34
4.2.4 Canonical Ramsey numbers … … … … … . . 35
5 The Power of Probability 37
5.1 Probability spaces … … … … … … … … . . 37
5.1.1 Formal denitions … … … … … … … . 37
5.1.2 Probability in a discrete setting … … … … … 38
5.1.3 Mean and variance … … … … … … … . 38
5.1.5 Independence … … … … … … … … . 39
5.1.6 Expectation … … … … … … … … . . 39
5.2 Linearity of expectation … … … … … … … . . 40
5.2.2 A lower bound for diagonal Ramsey numbers … … . 40
5.2.4 Finding a dense bipartite subgraph … … … … . 41
5.2.6 Dominating sets … … … … … … … . . 42
5.3 Useful bounds … … … … … … … … … . . 43
5.4 ChernoHoeding bounds … … … … … … … 44
5.4.1 Independence … … … … … … … … . 44
5.4.3 A general Cherno bound … … … … … … 45
5.4.6 Binomial random variables … … … … … . . 46
5.5 The random graph … … … … … … … … . . 47
5.6 Alteration method … … … … … … … … . . 48
5.7 Second moment method … … … … … … … . . 49
5.7.1 Threshold functions … … … … … … … 49
5.7.3 Threshold for the emergence of a triangle … … … 49
5.8 Conditional probability … … … … … … … . . 51
5.8.1 The famous Monty Hall Problem: … … … … . . 51
5.8.3 Formal denition of conditional probability … … . . 52
5.8.6 Thresholds in random graphs … … … … … . 53
5.9 Lovasz' Local Lemma … … … … … … … … 55
5.9.3 Property B … … … … … … … … . . 55
5.9.5 Lovasz local lemma { asymmetric form … … … . 56
5.9.8 Application: R(3; k) … … … … … … … 57
5.10 Martingales … … … … … … … … … … 59
5.10.5 Azuma's inequality … … … … … … … . 61
5.10.7 Martingales and concentration … … … … … 62
5.10.13 Another Chernotype bound for binomial random variables 63
5.11 Gems: Entropy Method … … … … … … … . . 64
6 Szemeredi's Regularity Lemma 71
6.1 Origins … … … … … … … … … … … 71
6.2 Epsilonregular pairs … … … … … … … … . 72
6.2.1 Random pairs … … … … … … … … . 72
6.2.3 Regular pairs … … … … … … … … . 73
6.3 The regularity lemma … … … … … … … … 73
6.4 Proving SzemRegLem … … … … … … … … 73
6.4.3 Proof of the Main Lemma … … … … … … 75
6.5 Gems: Smoothed analysis of graphs … … … … … . 81
7 Properties of EpsilonRegular Pairs 83
7.1 The Intersection Property … … … … … … … . 83
7.2 Subsets in regular pairs … … … … … … … . . 85
7.3 Mean and variance implies regularity … … … … … . 86
7.4 Gems: Random slicing and fractional packing … … … . . 86
8 Subgraph Applications of the Regularity Lemma 87
8.1 Erd}osStoneSimonovits … … … … … … … . . 87
8.2 Degree form and number of copies of a graph … … … . . 90
8.2.2 Number of copies of a graph … … … … … . . 90
8.3 Blowup lemma … … … … … … … … … . 92
8.3.1 AlonYuster … … … … … … … … . . 92
8.3.2 Embedding theorems … … … … … … … 92
8.3.3 Zhao's theorem on bipartite tiling … … … … . 92
8.3.4 Tripartite version of HajnalSzemeredi … … … . . 92
9 Induced Subgraph Applications of the Regularity Lemma 93
9.1 An important parameter … … … … … … … . . 93
9.2 Generalized intersection property … … … … … … 93
9.3 Number of graphs of a certain type … … … … … . . 93
9.4 Probability that a graph is in a hereditary property … … . 93
9.5 Edit distance … … … … … … … … … . . 93
9.6 Expander graphs … … … … … … … … … 94
noteid: IDLAxb
Ramsey theory
Description:
A graph is a set of vertices with some pairs of vertices connected by edges. Graphs are used to model a number of phenomena, from biological and physical real life problems, to number theoretic and other mathematical problems. The study of partitioning substructures of graphs has been studied quite extensively. Ramsey theory is often described as the study of preservation of structure under partitioning. In this talk, I will survey some of the classic Ramsey theory results, and survey specifically some results from Ramsey theory on graphs.
noteid: Pd8QE7
Description:
noteid: Jytm3g
Description:
Is this different from "IFFSM0" ?
Ramsey Theory is a branch of combinatorics that can (very roughly) be characterized by the statement no matter how you color some combinatorical object there will be a monochro matic part that is orderly or, to quote Theordore S. Motzkin, complete disorder is impossible.
There are already two elementary books on Ramsey Theory:
1. Ramsey Theory by Graham, Spencer, and Rothchild [14].
2. Ramsey Theory over the Integers, Landman and Robertson [20]
These books are elementary in that they mostly do not use advanced techniques. Within Ramsey Theory, there are two theorems that stand out.
1. Ramsey’s theorem: For all c,m, there exists n, such that, for every ccoloring of Knthere is a monochromatic Km. 2. van der Waerden’s theorem: For all c,k, there exists W such that, for every ccoloring of {1,…,W} there exists a monochromatic arithmetic sequence of length k.
The books on Ramsey Theory mentioned above contain both of these theorems. By contrast, this book is just about van der Waerden’s theorem and its extensions. Given our focus, we can cover more ground. Our goal is to cover virtually every extension or variant of van der Waer den’s theorem that can be proven using purely combinatorial methods.
What does it mean to say that a proof is purely combinatorial? We take this to mean that no methods from Calculus or Topology are used. This does not mean the proofs are easy; however, it does mean that no prior math is re quired aside from some simple combinatorics.
noteid: Jypy20
Description:
Ramsey Theory is a branch of combinatorics that can (very roughly) be characterized by the statement no matter how you color some combinatorical object there will be a monochro matic part that is orderly or, to quote Theordore S. Motzkin, complete disorder is impossible.
There are already two elementary books on Ramsey Theory:
1. Ramsey Theory by Graham, Spencer, and Rothchild [14].
2. Ramsey Theory over the Integers, Landman and Robertson [20]
These books are elementary in that they mostly do not use advanced techniques. Within Ramsey Theory, there are two theorems that stand out.
1. Ramsey’s theorem: For all c,m, there exists n, such that, for every ccoloring of Knthere is a monochromatic Km. 2. van der Waerden’s theorem: For all c,k, there exists W such that, for every ccoloring of {1,…,W} there exists a monochromatic arithmetic sequence of length k.
The books on Ramsey Theory mentioned above contain both of these theorems. By contrast, this book is just about van der Waerden’s theorem and its extensions. Given our focus, we can cover more ground. Our goal is to cover virtually every extension or variant of van der Waer den’s theorem that can be proven using purely combinatorial methods.
What does it mean to say that a proof is purely combinatorial? We take this to mean that no methods from Calculus or Topology are used. This does not mean the proofs are easy; however, it does mean that no prior math is re quired aside from some simple combinatorics.
noteid: IFFSM0
Description:
The past three decades have seen enormous development in graph the ory, and one striking feature is the invention of many modern methods which involve ideas from various branches of mathematics such as proba bility, algebra, geometry, and analysis. Graph Ramsey theory is an impor tant area that serves not only as an abundant source but also as a testing ground of these methods. Given the inconvenience to access sporadic re sults in an extensive literature, we set out to describe the material in this elementary book which aims to provide an introduction to graph Ramsey theory, with focus on methods. The mathematical prerequisites for this book are minimal: we only assumed familiarity with elementary calculus, linear algebra, and graph theory. To make this book as selfcontained as possible, we attempted to develop the theory from scratch except the use of a few theorems in number theory (yet without proofs), for instance, some constructions heavily rely on the structural properties of finite fields, so we laid down the background beforehand. Of course, no book could give a complete treatment of the subject in dicated in their titles; simplicity is our first criterion for selecting topics. By so doing, we hope that, on the one hand, readers can easily extract the basic idea underlying each approach and quickly master the methods; on the other hand, teachers can completely finish one topic in a single lesson. (We are sorry for not being able to incorporate many deep results into this introductory book.) The selected topics are independent; beginners may skip the chapters, sections, and proofs marked with asterisks. Despite substantial advance in graph Ramsey theory, most outstanding problems are far from being solved and beyond the power of traditional methods. The new insights generated by tackling these problems will most likely lead to new tools and techniques. It is due to the abundance and hardness of problems that graph Ramsey theory is full of vitality and hence deserves much more research efforts. We believe that this book, intended for beginning graduate students, can serve as an entrance to this beauti ful theory. To facilitate better understanding of the material, this book contains some standard exercises. We are deeply indebted to the following professors who introduced us to the exciting world of Ramsey theory: J. Beck, B. Bollobás, V. Chvátal, P. Erdos, R. Faudree, A. Gyárfas, J. Kahn, C. Rousseau, M. Saks, R. Schelp, F. Tian. Without their instruction, this book could never be made possible. We also wish to express our gratitude to N. Alon, G. Chang, G. Fan, T. Gowers, F. Graham, K. Lih, J. Kim, Z. Ma, J. Shao, A. Szemerédi, Y. Yeh, and many more who should be on this list, for their perceptive
noteid: IVtZ4x
Description:
There are many interesting applications of Ramsey theory, these include results in number theory, algebra, geometry, topology, set theory, logic, ergodic theory, information theory and theoretical computer science. Relations of Ramseytype theorems to various fields in mathematics are well documented in published books and monographs. The main objective of this survey is to list applications mostly in theoretical computer science of the last two decades not contained in these.
noteid: IVub3N
Description:
These are the notes based on the course on Ramsey Theory taught at Universitat Hamburg in Summer 2011. The lecture was based on the textbook "Ramsey theory" of Graham, Rothschild, and Spencer [44]. In fact, large part of the material is taken from that book.
Hamburg, Summer 2011 Mathias Schacht
Contents:
Preface iii
Chapter 1. Introduction 1
1.1. A few cornerstones in Ramsey theory 1
1.2. A unifying framework 4
1.3. The compactness principle 5
1.4. Other topics in Ramsey theory 6
Chapter 2. Ramsey's theorem 9
2.1. Statement of Ramsey's theorem and notation 9
2.2. Proof of Ramsey's theorem for k = 1 and 2 10
2.3. Proof of Ramsey's theorem for general k 12
2.4. Bounds for the symmetric Ramsey function 15
2.5. Infinite version of Ramsey's theorem 18
Chapter 3. Arithmetic progressions 21
3.1. Combinatorial proof of van der Waerden's theorem 21
3.2. Topological proof of van der Waerden's theorem 26
3.3. Two proofs of Roth's theorem 32
Chapter 4. The Hales{Jewett theorem 43
4.1. Applications of the Hales{Jewett theorem 43
4.2. Shelah's proof of the Hales{Jewett theorem 48
4.3. Upper bounds for the HalesJewett numbers 51
Appendix A. Topology 53
A.1. Topological and metric spaces 53
A.2. Topological dynamics 55
A.3. Ultrafilter 58
Appendix B. Analysis 61
B.1. Subadditive functions 61
B.2. Discrete Fourier analysis 61
Notation 65
Bibliography 67
noteid: IVuBqM
Arithmetic(additive) Combinatorics
Description:
Contents
Contents
1. The HalesJewett Theorem
2. Roth's theorem
3. Weyl's inequality
4. Vinogradov's three primes theorem
5. The geometry of numbers
6. Frieman's theorem
7. Szemeredi's theorem
noteid: Mg20gN
Description:
These are notes from a mini course on additive combinatorics given in Princeton University on August 2324, 2007. The lectures were Boaz Barak (Princeton University), Luca Trevisan (Univer
sity of California at Berkeley) and Avi Wigderson (Institute for Advanced Study, Princeton). The
notes were taken by Aditya Bhaskara, Arnab Bhattacharyya, Moritz Hardt, Cathy Lennon, Kevin
Matulef, Rajsekar Manokaran, Indraneel Mukherjee, Wolfgang Mulzer, Aaron Roth, Shubhangi
Saraf, David Steurer, and Aravindan Vijayaraghavan.
The lectures were also videotaped, and the tapes appear on the course’s website at http://www.
cs.princeton.edu/theory/index.php/Main/AdditiveCombinatoricsMinicourse
The course organizers were Boaz Barak, Moses Charikar and Mitra Kelly.
noteid: L0oYpp
Description:
Additive combinatorics is the branch of combinatorics where the objects of study are subsets
of the integers or of other abelian groups, and one is interested in properties and patterns that
can be expressed in terms of linear equations. More generally, arithmetic combinatorics deals
with properties and patterns that can be expressed via additions and multiplications.
In the past ten years, additive and arithmetic combinatorics have been extremely successful
areas of mathematics, featuring a convergence of techniques from graph theory, analysis and
ergodic theory. They have helped prove longstanding open questions in additive number theory,
and they offer much promise of future progress.
Techniques from additive and arithmetic combinatorics have found several applications in
computer science too, to property testing, pseudorandomness, PCP constructions, lower bounds,
and extractor constructions. Typically, whenever a technique from additive or arithmetic com
binatorics becomes understood by computer scientists, it finds some application.
Considering that there is still a lot of additive and arithmetic combinatorics that computer
scientists do not understand (and, the field being very active, even more will be developed in
the near future), there seems to be much potential for future connections and applications.
noteid: JYtmrJ
Description:
This booklet is devoted to certain aspects of combinatorial number theory, or addi
tive combinatorics as it is now often called. This change of terminology reflects a shift
in the emphasis of problems investigated. First it was mainly infinite sequences and
finite sets of integers; this naturally led to sets of residues, then sets in finite groups,
and also sets of lattice points, then sets in general commutative groups. (We shall now
and then mention results that do not need commutativity, but will not pursue this aim
forcefully.)
In classical additive number theory we start with a given set, say of primes, and
try to understand how an integer can be expressed as a sum of elements of this set. In
combinatorial (or structural, or inverse) theory we do the opposite: given an additive
assumption about a set, say that it has few or many sums, we try to understand its
structure. (This is not always explicit in the formulation; we can equivalently say “if
a set has few sums, it has property A” or “if a set has property nonA, it has many
sums”; we will not attempt uniformity here.)
Historically, combinatorial additive theory grew out of the classical. Though a few
isolated results existed before, the turning point is Schnirelmann’s approach to the
Goldbach problem. Goldbach’s conjecture asserts that any integer > 3 can be expressed
as a sum of 2 or 3 primes, depending on parity. Schnirelmann proved the weaker result
that there is a bound k so that every integer is a sum of at most k primes, or in other
words, the primes form an additive basis. To this end he established that (very loosely
speaking; exact formulations will be given in Chapter 3) integers that can be written
as a sum of two primes have positive density; and every set having positive density is
a basis. For the Goldbach problem Schnirelmann’s approach was soon superseded by
Vinogradov’s trigonometric sum method; however, it kindled the interest in addition of
general sets.
noteid: KiTqwR
Description:
noteid: Jpzewa
Description:
noteid: JpyRBK
Description:
During the fall of 2004 Fan Chung Graham taught a graduate course at UCSD about the combinatorics of patterns in subsets and graphs. Class members would take turns taking notes and then write them up, this is a collection of those notes (with some light revision). We thank Fan for teaching the class and for providing some corrections/directions on the lecture notes. We would also like to thank Van Vu for being a guest lecturer (Lecture 7).
These lecture notes were written by Blair Angle, Steven Butler, Kevin Costello, Daniel Felix, Paul Horn, Ross Richardson, D. Jacob Wildstrom and Lei Wu. This is a work in progress and is being updated from time to time. The most current version can be found by visiting the website below.
1
Introduction
Steven Butler
5
2
Szemerédi’s Regularity Lemma, Part 1
Daniel Felix
9
3
Szemerédi’s Regularity Lemma, Part 2
Kevin Costello
14
4
Applications of the Regularity Lemma
Ross Richardson
20
5
More Applications of the Regularity Lemma
D. Jacob Wildstrom
25
6
Regularity Lemma for Hypergraphs
Steven Butler
29
7
Results on Sumsets
Lei Wu
35
2
8
QuasiRandom Hypergraphs
Paul Horn
40
9
Quasirandomness, Ramsey Graphs, and Explicit Construc
tions
Ross Richardson
45
10 Discrepancy of Graphs
Blair Angle
50
11 Relating Deviation and Discrepancy for Hypergraphs, Part 1
Kevin Costello
54
12 Relating Deviation and Discrepancy for Hypergraphs, Part 2
Daniel Felix
57
13 4term Arithmetic Progressions
Paul Horn
63
14 More on Patterns in Subsets
Jake Wildstrom
69
15 Regularity Lemma and Turán Type Problems
Steven Butler
72
16 Ramsey Theory Applications of the Regularity Lemma
Paul Horn
79
17 Extremal Conjectures Related to the Regularity Lemma and
an Introduction to Expanders
Dan Felix
84
18 Expander Graphs and Superconcentrators
Steven Butler
89
3
19 Spectral Analysis of Expander Graphs
Kevin Costello
95
noteid: KFqM6q
Probabilistic Combinatorics and Graph theory
Geometric Combinatorics and Graph theory
Description:
Contents
1
Drawing Planar Graphs
5
1.1
Euler’s formula … … … … … … … … . .
7
1.2
Straightline drawing … … … … … … … . .
9
1.3
Drawing a planar graph on a grid … … … … … . 13
2
Characterization of planar graphs
17
3
Crossings: few and many
23
3.1
Turan’s Brick Factory Problem
… … … … … . . 23
3.2
Conway’s Thrackle Conjecture … … … … … … 24
4
Turántype problems
29
4.1
Crossing edges, disjoint edges … … … … … … 29
4.2
Extremal Graph Theory … … … … … … … 31
5
Ordnung muß sein!
35
5.1
Ramsey’s Theorem … … … … … … … … 35
5.2
Dilworth’s Theorem … … … … … … … … 37
5.3
DavenportSchinzel Sequences … … … … … … 41
6
Beyond planarity
45
6.1
The Crossing Lemma … … … … … … … . . 45
6.2
Halving segments … … … … … … … … . 47
noteid: JMORIU
Enumerative Combinatorics and Graph theory
Description:
This paper presents a new proof of the hooklength formula, which computes the number of standard Young tableaux of a given shape. After recalling the basic definitions, we present two inverse algorithms giving the desired bijection. The next part of the paper presents the proof of the bijectivity of our construction. The paper concludes with some examples.
noteid: NtM47D
Description:
The term “Fibonacci numbers” is used to describe the series of numbers generated by the pattern
1,1,2,3,5,8,13,21,34,55,89,144…,
where each number in the sequence is given by the sum of the previous two terms.
This pattern is given by $u_1= 1$,$u_2= 1$ and the recursive formula $u_n= u_{n1}+ u_{n2}, n > 2$. First derived from the famous “rabbit problem” of 1228, the Fibonacci numbers were originally used to represent the number of pairs of rabbits born of one pair in a certain population. Let us assume that a pair of rabbits is introduced into a certain place in the first month of the year. This pair of rabbits will produce one pair of offspring every month, and every pair of rabbits will begin to reproduce exactly two months after being born. No rabbit ever dies, and every pair of rabbits will reproduce perfecctly on schedule.
noteid: KqXDS7
Description:
noteid: KSe9FC
Description:
The statements in each problem are to be proved combinatorially, in most
cases by exhibiting an explicit bijection between two sets. Try to give the
most elegant proof possible. Avoid induction, recurrences, generating func
tions, etc., if at all possible.
We will (subjectively) indicate the difficulty level of each problem as follows:
[1] easy
[2] moderately difficult
[3] difficult
[u] unsolved
[?] The result of the problem is known, but I am uncertain whether
a combinatorial proof is known.
[*] A combinatorial proof of the problem is not known. In all cases, the
result of the problem is known.
Further gradations are indicated by + and –; e.g., [3–] is a little easier than
[3]. In general, these difficulty ratings are based on the assumption that the
solutions to the previous problems are known.
For those wanting to plunge immediately into serious research, the most
interesting open bijections (but most of which are likely to be quite difficult)
are Problems 27, 28, 59, 107, 143, 118, 123 (injection of the type described),
125, 140, 148, 151, 195, 198, 215, 216, 217, 226, 235, and 247.
1. Elementary Combinatorics
3
2. Permutations
10
3. Partitions
20
4. Trees
30
5. Catalan Numbers
38
6. Young Tableaux
50
7. Lattice Paths and Tilings
61
noteid: JMOVsc
Description:
This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that I have not attempted to give a comprehensive discussion. Instead I have tried only to communicate some of the main ideas. Generating functions are a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable the ory) on the other. It is possible to study them solely as tools for solving discrete problems. As such there is much that is powerful and magical in the way generating functions give unified methods for handling such prob lems. The reader who wished to omit the analytical parts of the subject would skip chapter 5 and portions of the earlier material. To omit those parts of the subject, however, is like listening to a stereo broadcast of, say, Beethoven’s Ninth Symphony, using only the left audio channel. The full beauty of the subject of generating functions emerges only from tuning in on both channels: the discrete and the continuous. See how they make the solution of difference equations into child’s play. Then see how the theory of functions of a complex variable gives, virtually by inspection, the approximate size of the solution. The interplay between the two channels is vitally important for the appreciation of the music. In recent years there has been a vigorous trend in the direction of finding bijective proofs of combinatorial theorems. That is, if we want to prove that two sets have the same cardinality then we should be able to do it by exhibiting an explicit bijection between the sets. In many cases the fact that the two sets have the same cardinality was discovered in the first place by generating function arguments. Also, even though bijective arguments may be known, the generating function proofs may be shorter or more elegant. The bijective proofs give one a certain satisfying feeling that one ‘re ally’ understands why the theorem is true. The generating function argu ments often give satisfying feelings of naturalness, and ‘oh, I could have thought of that,’ as well as usually offering the best route to finding exact or approximate formulas for the numbers in question. This book was tested in a senior course in discrete mathematics at the University of Pennsylvania. My thanks go to the students in that course for helping me at least partially to debug the manuscript, and to a number of my colleagues who have made many helpful suggestions. Any reader who is kind enough to send me a correction will receive a thencurrent complete errata sheet and many thanks.
Chapter 1: Introductory Ideas and Examples
1.1
An easy two term recurrence … … … … … . . 3
1.2
A slightly harder two term recurrence … … … … . 5
1.3
A three term recurrence … … … … … … . 8
1.4
A three term boundary value problem … … … … 10
1.5
Two independent variables … … … … … . . 11
1.6
Another 2variable case
… … … … … … 16
Exercises … … … … … … … … . 24
Chapter 2: Series
2.1
Formal power series … … … … … … . . 30
2.2
The calculus of formal ordinary power series generating functions 33
2.3
The calculus of formal exponential generating functions
… . 39
2.4
Power series, analytic theory … … … … … . 46
2.5
Some useful power series … … … … … … 52
2.6
Dirichlet series, formal theory
… … … … … 56
Exercises … … … … … … … … . 65
Chapter 3: Cards, Decks, and Hands: The Exponential Formula
3.1
Introduction … … … … … … … . . 73
3.2
Definitions and a question … … … … … . . 74
3.3
Examples of exponential families
… … … … . . 76
3.4
The main counting theorems … … … … … . 78
3.5
Permutations and their cycles
… … … … … 81
3.6
Set partitions … … … … … … … . . 83
3.7
A subclass of permutations … … … … … . . 84
3.8
Involutions, etc.
… … … … … … … 84
3.9
2regular graphs
… … … … … … … 85
3.10 Counting connected graphs … … … … … . . 86
3.11 Counting labeled bipartite graphs … … … … . . 87
3.12 Counting labeled trees … … … … … … . 89
3.13 Exponential families and polynomials of ‘binomial type.’ … . 91
3.14 Unlabeled cards and hands … … … … … . . 92
3.15 The money changing problem
… … … … … 96
3.16 Partitions of integers
… … … … … … . 100
3.17 Rooted trees and forests … … … … … … 102
3.18 Historical notes … … … … … … … . 103
Exercises … … … … … … … … . 104
Chapter 4: Applications of generating functions
4.1
Generating functions find averages, etc.
… … … . . 108
4.2
A generatingfunctionological view of the sieve method … . . 110
4.3
The ‘Snake Oil’ method for easier combinatorial identities
… 118
4.4
WZ pairs prove harder identities
… … … … . . 130
4.5
Generating functions and unimodality, convexity, etc.
… . . 136
4.6
Generating functions prove congruences
… … … . . 140
4.7
The cycle index of the symmetric group
… … … . . 141
4.8
How many permutations have square roots?
… … … 146
4.9
Counting polyominoes … … … … … … . 150
4.10 Exact covering sequences … … … … … … 154
Exercises … … … … … … … … . 157
Chapter 5: Analytic and asymptotic methods
5.1
The Lagrange Inversion Formula
… … … … . . 167
5.2
Analyticity and asymptotics (I): Poles … … … … 171
5.3
Analyticity and asymptotics (II): Algebraic singularities … . 177
5.4
Analyticity and asymptotics (III): Hayman’s method
… . . 181
Exercises … … … … … … … … . 188
Appendix: Using MapleTMand MathematicaTM
… … . . 192
Solutions … … … … … … … … 197
References
… … … … … … … . . 224
noteid: JMP7aQ
Description:
Contents:
1. Introduction
2. Permutations
3. Generating Functions
4. Binomials
5. InclusionExclusion
6. Möbius Inversion
7. CauchyFrobenius Theorem
8. PólyaRedfield Theorem
Bibliography
noteid: JMPjXD
Algebraic Combinatorics and Graph theory
Description:
These notes provide an introduction to association schemes, along with some
related algebra. Their form and content has benefited from discussions with
BillMartin and Ada Chan.
Contents
Preface iii
1 Schemes and Algebras 1
1.1 Definitions and Examples … … … … … … … … 1
1.2 Strongly Regular Graphs … … … … … … … … . 3
1.3 The BoseMesner Algebra … … … … … … … … 6
1.4 Idempotents … … … … … … … … … … . . 7
1.5 Idempotents for Association Schemes … … … … … . . 9
2 Parameters 13
2.1 Eigenvalues … … … … … … … … … … . . 13
2.2 Strongly Regular Graphs … … … … … … … … . 15
2.3 Intersection Numbers … … … … … … … … . . 16
2.4 Krein Parameters … … … … … … … … … . . 17
2.5 The Frame Quotient … … … … … … … … … 20
3 An Inner Product 23
3.1 An Inner Product … … … … … … … … … . . 23
3.2 Orthogonal Projection … … … … … … … … . . 24
3.3 Linear Programming … … … … … … … … … 25
3.4 Cliques and Cocliques … … … … … … … … . . 28
3.5 Feasible Automorphisms … … … … … … … … 30
4 Products and Tensors 33
4.1 Kronecker Products … … … … … … … … … . 33
4.2 Tensor Products … … … … … … … … … … 34
4.3 Tensor Powers … … … … … … … … … … . 37
4.4 Generalized Hamming Schemes … … … … … … . . 38
4.5 A Tensor Identity … … … … … … … … … . . 39
4.6 Applications … … … … … … … … … … . . 41
5 Subschemes and Partitions 43
5.1 Equitable Partitions … … … … … … … … … . 43
5.2 Subschemes and Partitions … … … … … … … . . 45
5.3 Primitivity … … … … … … … … … … … 48
5.4 Simple Subsets … … … … … … … … … … 50
5.5 Completely Regular Subsets … … … … … … … . . 51
6 Translation Schemes 53
6.1 Characters … … … … … … … … … … … 53
6.2 Translation Graphs … … … … … … … … … . 55
6.3 Translation Schemes and their Duals … … … … … . . 56
6.4 Linear Graphs … … … … … … … … … … . 58
6.5 Geometry, Codes and Graphs … … … … … … … . 59
6.6 Language … … … … … … … … … … … . 61
7 Duality 63
7.1 The Discrete Fourier Transform … … … … … … … 63
7.2 The Hadamard Transform … … … … … … … … 65
7.3 TwoMatrix Duals … … … … … … … … … . . 68
7.4 MacWilliams Theorem … … … … … … … … . . 69
7.5 Projective Planes … … … … … … … … … . . 71
7.6 Duality … … … … … … … … … … … . . 73
7.7 Duality and Type IIMatrices … … … … … … … . 75
7.8 Difference Sets … … … … … … … … … … 76
8 TypeIIMatrices 79
8.1 TypeIIMatrices … … … … … … … … … … 79
8.2 Two Algebras … … … … … … … … … … . . 81
8.3 Eigenspaces … … … … … … … … … … . . 83
9 Galois Theory 85
9.1 BoseMesner Automorphisms … … … … … … … 85
9.2 Galois … … … … … … … … … … … … 86
9.3 Applications … … … … … … … … … … . . 89
9.4 Multipliers … … … … … … … … … … … 91
10 A Bestiary 99
10.1 Cyclic Schemes … … … … … … … … … … 99
10.2 Paley Graphs … … … … … … … … … … . . 100
10.3 Quasisymmetric Designs … … … … … … … … 102
10.4 Partial Spreads … … … … … … … … … … . 104
10.5 Covers of Complete Bipartite Graphs … … … … … . . 106
10.6 Groups … … … … … … … … … … … . . 108
11 Algebra andModules 111
11.1 Algebras … … … … … … … … … … … . 111
11.2 Division Algebras … … … … … … … … … . . 112
11.3 Maps andModules … … … … … … … … … . 115
11.4 Opposites … … … … … … … … … … … 116
11.5 Schur’s Lemma … … … … … … … … … … 117
12 SemisimpleModules 119
12.1 Summands and Idempotents … … … … … … … . 119
12.2 Primary Decomposition … … … … … … … … . 121
12.3 Group Algebras … … … … … … … … … … 122
12.4 SemisimpleModules … … … … … … … … … 124
12.5 SemisimpleModules: Examples … … … … … … . . 125
12.6 IndecomposableModules … … … … … … … … 127
13 Semisimple Algebras 131
13.1 Semisimple Algebras … … … … … … … … … 131
13.2 Simple Artinian Algebras … … … … … … … … . 133
13.3 Composition Series … … … … … … … … … . 135
13.4 Semisimple Artinian Algebras … … … … … … … . 137
13.5 Representations … … … … … … … … … … 138
13.6 Centralizers … … … … … … … … … … . . 139
13.7 Trace … … … … … … … … … … … … 141
13.8 Maschke … … … … … … … … … … … . 141
14 Division Algebras 145
14.1 Central Simple Algebras … … … … … … … … . 145
14.2 Factors … … … … … … … … … … … . . 148
14.3 Finite Division Algebras … … … … … … … … . 149
14.4 Real Algebra … … … … … … … … … … . . 151
15 Work 153
15.1 Classical Parameters … … … … … … … … … 153
16 Adjacency Algebras 155
16.1 Extending the Adjacency Algebra … … … … … … . . 155
16.2 Some Applications … … … … … … … … … . 156
16.3 Cospectral Awful Graphs … … … … … … … … . 157
16.4 Modules andWalks … … … … … … … … … . 160
16.5 An Inner Product on Polynomials … … … … … … . 161
16.6 Spectral Decomposition … … … … … … … … . 162
16.7 Orthogonal Polynomials … … … … … … … … . 163
16.8 DistanceRegular Graphs … … … … … … … … 166
16.9 Locally DistanceRegular Graphs … … … … … … . . 166
16.10Coherent Algebras … … … … … … … … … . 168
17 Line Digraphs 171
17.1 Line Digraphs … … … … … … … … … … . 171
17.2 QuantumWalks … … … … … … … … … … 173
17.3 Eigenvalues of QuantumWalks … … … … … … … 173
18 Lie Algebras 177
18.1 Basics … … … … … … … … … … … … 177
18.2 Enveloping Algebras … … … … … … … … … 179
18.3 Posets … … … … … … … … … … … … 179
18.4 Representations of Lie Algebras … … … … … … … 181
18.5 Bilinear Forms … … … … … … … … … … . 182
18.6 An Example … … … … … … … … … … . . 184
18.7 IrreducibleModules … … … … … … … … … 185
18.8 Semisimple Elements … … … … … … … … . . 188
18.9 SemisimpleModules … … … … … … … … … 190
19 Terwilliger Algebras 193
19.1 Modules … … … … … … … … … … … . 193
19.2 Thinness … … … … … … … … … … … . 195
19.3 Jaeger Algebras … … … … … … … … … … 196
20 Strongly Regular Graphs 199
20.1 Strongly Regular Graphs … … … … … … … … . 199
20.2 Local Eigenvalues … … … … … … … … … . . 202
20.3 Dimensions … … … … … … … … … … . . 204
21 Hamming Schemes 207
21.1 The Binary Hamming Scheme … … … … … … … 207
21.2 Modules … … … … … … … … … … … . 208
22 Spin 211
22.1 Braids … … … … … … … … … … … … 211
22.2 Nomura Algebras … … … … … … … … … . . 211
22.3 Braids … … … … … … … … … … … … 212
22.4 Jones Pairs … … … … … … … … … … … 213
22.5 Gauge Equivalence … … … … … … … … … . 216
22.6 Nomura Algebras of TypeIImatrices … … … … … . . 216
22.7 SpinModels … … … … … … … … … … . . 218
23 Abelian Spin 221
23.1 Schemes … … … … … … … … … … … . 221
23.2 CoordinateMatrices … … … … … … … … … 222
23.3 Duality … … … … … … … … … … … . . 224
23.4 Modular Invariance … … … … … … … … … . 226
23.5 The Cyclic Group … … … … … … … … … . . 227
noteid: NsYwtw
Description:
This course deals with results where a combinatorial problem is solved by applying
noncombinatorial (mostly algebraic) arguments. Of course, it is always pleasant when
methods and ideas developed for tacking one sort of problems can can be applied to
another. Also, this often leads to a better understanding of the subject and to further
results. Last, but not least, the proofs obtained via this method are often very elegant
and beautiful.
The drawbacks of the method is that it does not work in many (seemingly suitably)
situations and that each problem usually requires an individual approach. It seems
that the whole theory is still in the stage of development.
Contents
1
Preface
3
2
Lindstrom’s Theorem
4
3
The Addressing Problem for Graphs
6
3.1
{0,1,*}Addressing … … … … … … … … … . .
6
3.2
Reduction to Decompositions … … … … … … … . .
6
3.3
Graham–Pollack Theorem … … … … … … … … .
7
4
Rules and Clubs
8
4.1
A Few Problems … … … … … … … … … …
8
4.2
Solutions
… … … … … … … … … … … .
9
5
Modular Frankl–Wilson Inequality
11
6
Chromatic Number of Rn
13
6.1
Small Dimensions … … … … … … … … … …
14
6.2
General Upper Bounds … … … … … … … … …
14
6.3
Lower Bounds … … … … … … … … … … . .
16
6.4
Figuring the Optimal Parameters … … … … … … …
17
6.5
Some Improvements … … … … … … … … … .
17
7
Borsuk’s Conjecture
20
8
Borsuk’s Conjecture and Leech Lattice
21
9
Constructive Lower Bounds on Ramsey Numbers
26
9.1
Probabilistic Lower Bound … … … … … … … … .
26
9.2
Nagy’s Construction … … … … … … … … … .
26
9.3
Supexponential Bounds
… … … … … … … … . .
27
10 The Shannon Capacity of Graphs
28
10.1 Motivation
… … … … … … … … … … …
28
10.2 The Shannon Capacity of a Union … … … … … … . .
30
10.3 Upper Bounds via Linear Programming … … … … … . .
33
10.4 Pentagon
… … … … … … … … … … … .
35
10.5 Sperner Capacity … … … … … … … … … …
38
11 Combinatorial Nullstellensatz
39
11.1 Cauchy–Davenport Theorem
… … … … … … … . .
39
11.2 Regular Subgraphs … … … … … … … … … . .
42
11.3 Covering Cube by Affine Hyperplanes … … … … … …
46
11.4 Chevalley–Waring Theorem … … … … … … … …
47
11.5 Sets Meeting Every Affine Hyperplane … … … … … …
48
12 Desarguesian Projective Plane PG(2,q)
49
13 Designs
52
13.1 Difference Families … … … … … … … … … . .
53
13.2 Cyclotomic Classes … … … … … … … … … . .
53
13.3 Tools: Mean and Variance … … … … … … … … .
55
13.4 Computing Mean and Variance for m … … … … … …
56
13.5 Putting Everything Together … … … … … … … . .
58
14 Eigenvalues and Expanders
59
14.1 First Eigenvalue
… … … … … … … … … …
59
14.2 Second Eigenvalue … … … … … … … … … . .
60
14.3 Walks on Expanders … … … … … … … … … .
62
14.4 Derandomisation … … … … … … … … … …
63
15 Explicit ConstantDegree Expanders
65
15.1 Operations on Graphs … … … … … … … … …
65
15.2 ZigZag Product
… … … … … … … … … …
66
15.3 Properties of the ZigZag Product
… … … … … … . .
67
16 Example Sheet
69
16.1 Basic Problems … … … … … … … … … … .
69
16.2 Harder Problems … … … … … … … … … …
70
16.3 Yet Harder! … … … … … … … … … … …
71
16.4 Some Important Research Problems … … … … … … .
72
16.5 Application: Primality Testing … … … … … … … .
72
noteid: KqYC4S
Description:
Chapter 1
Walks in graphs
5
Chapter 2
Cubes and the Radon transform
15
Chapter 3
Random walks
25
Chapter 4
The Sperner property
29
Chapter 5
Group actions on boolean algebras
45
Chapter 6
Young diagrams and qbinomial coefficients
61
Chapter 7
Enumeration under group action
83
Chapter 8
A glimpse of Young tableaux
111
Chapter 9
The MatrixTree Theorem
147
Chapter 10 Eulerian digraphs and oriented trees
145
Chapter 11 The cycle space and bond space
157
Chapter 12 Miscellaneous gems of linear algebra
185
References
191
noteid: J75ksI
Description:
Combinatorics encompasses not just the art of counting, but also analyzing the structure of discrete objects such as graphs, matroids and partially ordered sets. In algebraic combinatorics, one associates algebraic objects like groups, rings and vector spaces to combinatorial objects in order to reveal more of their structure.
noteid: J73Xdi
Description:
This course will bring students to the point of being able to conduct supervised original research in lowdimensional combinatorics, using algebraic and bijective techniques. Methods taught will include recurrence relations (linear and nonlinear), transfer matrices, and generating functions; special topics will include triangulations, tilings, Markoff numbers, and Somos sequences.
This course will not require much in the way of prior background in combinatorics (beyond the level of, say, the use of binomial coefficients in counting combinations), but students who take the course will find that a background in discrete mathematics or graph theory, and in the writing of proofs, will be helpful.
There will be an emphasis on discovery and the use of computers (specifically Maple). Prior knowledge of Maple is not required.
The following mathematical topics will be covered:
 Binomial coefficients and Pascal's triangle
 Calculus of finite differences
 Fibonacci numbers and linear recurrences
 Rational and algebraic generating functions
 Continued fractions and continuants
 Catalan objects and lattice animals
 Transfer matrices
 Combinatorial reciprocity theorems
 qenumeration and tiling
 Determinants and condensation, number walls, triangulations, and frieze patterns
 Signed enumeration and applications (the theorems of Vandermonde, CayleyHamilton, and GesselViennot)
 Markoff numbers
 Somos sequences
noteid: IVwoML
Description:
noteid: JMPUbE
Analytic Combinatorics and Graph theory
Description:
This course is intended for graduate students and advanced undergrads in mathematics or theoretical computer science.
Requirements: Basic knowledge of linear algebra and probability. There will be about 5 problem sets. Each student will be required to submit these, as well as to scribe one lecture.
[Lecture 1]  Introduction, examples.
[Lecture 2]  Formal definitions, Isoperimetry, KKL.
[Lecture 3]  Normed spaces, proof of hypercontractive inequality, begin BKKKL
[Lecture 4]  BKKKL (monotonization, discretization), hypercube graph, Russo's Lemma
[Lecture 5]  Juntas, Graph properties and thresholds
[Lecture 6]  First Passage Percolation
[Lecture 7]  Linearity Testing
[Lecture 8]  Long Code Testing
[Lecture 9]  Hastad's 3 bit PCP
[Lecture 10]  Vertex Cover, Intersecting Functions
[Lecture 11]  Noise
noteid: LglVu4
Combinatorial optimization, Polyhedral combinatorics
Description:
Contents
1. Shortest paths and trees
5
1.1. Shortest paths with nonnegative lengths
5
1.2. Speeding up Dijkstra’s algorithm with heaps
9
1.3. Shortest paths with arbitrary lengths
12
1.4. Minimum spanning trees
19
2. Polytopes, polyhedra, Farkas’ lemma, and linear programming
23
2.1. Convex sets
23
2.2. Polytopes and polyhedra
25
2.3. Farkas’ lemma
31
2.4. Linear programming
33
3. Matchings and covers in bipartite graphs
39
3.1. Matchings, covers, and Gallai’s theorem
39
3.2. Maugmenting paths
40
3.3. Konig’s theorems
41
3.4. Cardinality bipartite matching algorithm
45
3.5. Weighted bipartite matching
47
3.6. The matching polytope
50
4. Menger’s theorem, flows, and circulations
54
4.1. Menger’s theorem
54
4.2. Flows in networks
58
4.3. Finding a maximum flow
60
4.4. Speeding up the maximum flow algorithm
65
4.5. Circulations
68
4.6. Minimumcost flows
70
5. Nonbipartite matching
78
5.1. Tutte’s 1factor theorem and the TutteBerge formula
78
5.2. Cardinality matching algorithm
81
5.3. Weighted matching algorithm
85
5.4. The matching polytope
91
5.5. The CunninghamMarsh formula
95
6. Problems, algorithms, and running time
97
6.1. Introduction
97
6.2. Words
98
6.3. Problems
100
6.4. Algorithms and running time
100
6.5. The class NP
101
6.6. The class coNP
102
6.7. NPcompleteness
103
6.8. NPcompleteness of the satisfiability problem
103
6.9. NPcompleteness of some other problems
106
6.10. Turing machines
108
7. Cliques, stable sets, and colourings
111
7.1. Introduction
111
7.2. Edgecolourings of bipartite graphs
115
7.3. Partially ordered sets
121
7.4. Perfect graphs
124
7.5. Chordal graphs
128
8. Integer linear programming and totally unimodular matrices
132
8.1. Integer linear programming
132
8.2. Totally unimodular matrices
134
8.3. Totally unimodular matrices from bipartite graphs
139
8.4. Totally unimodular matrices from directed graphs
143
9. Multicommodity flows and disjoint paths
148
9.1. Introduction
148
9.2. Two commodities
153
9.3. Disjoint paths in acyclic directed graphs
157
9.4. Vertexdisjoint paths in planar graphs
159
9.5. Edgedisjoint paths in planar graphs
165
9.6. A column generation technique for multicommodity flows
168
10. Matroids
173
10.1. Matroids and the greedy algorithm
173
10.2. Equivalent axioms for matroids
176
10.3. Examples of matroids
180
10.4. Two technical lemmas
183
10.5. Matroid intersection
184
10.6. Weighted matroid intersection
190
10.7. Matroids and polyhedra
194
References
199
Name index
210
Subject index
212
noteid: KvPgkR
Description:
This report consists of lecture notes for a graduate course in combinatorial optimization at the University of Oslo. A better, although longer, title of this course would be the report title Convexity, polyhedral theory and combinatorial optimization". The purpose of this report is to introduce the reader to convexity, polyhedral theory and the application of these areas to combinatorial optimization; the latter is known as polyhedral combinatorics. Compared to some other texts in polyhedral combinatorics we concentrate on the foundation in convex analysis. This is motivated by the fact that convexity leads to a good under standing of, e.g., duality and, in addition, convex analysis is very important for applied mathematics in general.
noteid: JMQbLO
Combinatorial design theory
Description:
It is by now well known that there are many connections between coding theory and the theory of combinatorial designs. During the past ten years Marshall Hall was extremely interested in some of these connections. His interest presumably originated with the celebrated result of MacWilliams, Sloane, and Thompson [17] that the code generated by the rows of the in cidence matrix of a projective plane of order 10 (if it exists) can have no words of weight 15 (cf.,[6]). Hall contributed to the attack on this projective plane in a paper on configurations in a plane of order 10 [8]. As we all know, these methods and an extensive computer search led to the "proof" of the nonexistence of the plane of order 10; for an account of this proof see [12].
noteid: NNkHtB
Coding theory
Description:
These are the notes for the 2011 Summer Tutorial on Coding Theory. I have not gone through and given citations or references for all of the results given here, but the presentation relies heavily on two sources, van Lint’s Introduction to Coding Theory and the book of Huffman and Pless Fundamentals of ErrorCorrecting Codes. I also used course notes written by Sebastian Pancratz from a Part II course given at Cambridge on Coding Theory and Cryptography given by Professor Tom Fisher, and my own course notes from a Cambridge Part III Arithmetic Combinatorics course given by Professor Tim Gowers. I also included notes from Henry Cohn’s MIT course, Applied Math for the Pure Mathematician. The last section of the notes is based on Nigel Boston’s survey article, “Graph Based Codes”. All mistakes in these notes are my fault.
noteid: NNmPBE
Description:
These notes were written over a period of years as part of an advanced under
graduate/beginning graduate course on Algebraic Coding Theory at Michigan
State University. They were originally intended for publication as a book, but
that seems less likely now. The material here remains interesting, important,
and useful; but, given the dramatic developments in coding theory during the
last ten years, significant extension would be needed.
 * * concatenated codes, erasure correcting, LDPC codes, iterative decoding, codes
on graphs, Viterbi, turbocodes * * *
The oldest sections are in the Appendix and are over ten years old, while the
newest are in the last two chapters and have been written within the last year.
The long time frame means that terminology and notation may vary somewhat
from one place to another in the notes. (For instance, Zp, Zp, and Fpall denote
a field with p elements, for p a prime.)
There is also some material that would need to be added to any published
version. This includes the graphs toward the end of Chapter 2, an index, and
inline references. You will find on the next page a list of the reference books
that I have found most useful and helpful as well as a list of introductory books
(of varying emphasis, difficulty, and quality).
noteid: Ljh49m