Discrete Mathematics (MA 5760)

Instructor: Narayanan N

Lecture Schedule: 12:00 noon to 12:50pm Monday
10:00am - 10:50am Thursday
9:00am - 9:50am Friday
Venue: HSB 265

Lecture 14, 15

Principle of Inclusion Exclusion, applications, a generalisation. Stirling Numbers, . ( Lecturer: Sajin Koroth.)

Lecture 12, 13

More on counting. Binomial identities and combinaorial proof. Proofs by constructing bijection. Induction and where it can go wrong.

Lecture 11

Sets and Counting. Selection with repitition. Intersecting families and Erdos-Ko-Rado Theorem.

Lecture 10

Assignment 3 (to submit on or before 2/03/2015)

  1. Let $G$ be a minimally two connected graph. Prove that $G -\{u,v\}$ is connected for any pair of adjacent vertices. Give an example to show that it is not true in general arbitrary 2-connected graphs.
  2. Prove that if every vertex of a graph $G$ has degree $3$, then $\lambda(G)=\kappa(G)$. i.e., vertex connectivity and edge connectivity are equal.
  3. Let $G$ be a graph and $C$ be a cycle in $G$. We say that an edge $uv$ is a chord for $C$ if $u$ and $v$ and vertices of $C$, but $uv$ is not an edge of $C$. That is, $u$ and $v$ are not consecutive vertices in the cycle. Prove that a graph is minimally two connected if and only if it contains no chords.

Lecture 9

Structure of two connected graphs. Some theorems.

Lecture 8a

Problem solving session.

Lecture 8

Planar graphs. Euler identity for planar graphs.

Lecture 7

Mengers theorem (ctd). Linearity of expectation and hamiltonial paths in directed graphs.

Assignment 2

  1. Let $T_n$ be any tournament on $n$ vertices (A tournament is a complete graph where every edge has some orientation). Prove that $G$ has a directed hamiltonian path. (A path is hamiltonian, if it contains all the vertices).
  2. Prove that, given $n\in \mathcal{N}$ there exists some tournament on $n$ vertices with at least $\frac{n!}{2^{n-1}}$ directed hamiltonian paths.

Lecture 6

Mengers theorem.

Lecture 5

More on Graceful tree conjecture. Connectivity: edge and vertex connectivities.

Lecture 4a

Class Test

Lecture 4

Properties of Trees. Spanning trees. Cartesian product. Line graph of a graph. Graph Decomposition, Ringel's conjecture and Graceful Tree conjecture.

Homework

    Be available soon.

Lecture 3

Connected components, cut edges and vertices, some basic theorems in graph theory. Use of extremality, contraposition.

Homework

  1. Oriented graphs are graphs obtained from an undirected graph by giving some direction to each edge. We saw that every orientation of $K_n$ contains a directed hamiltonian path.
    Prove that $\exists$ some orientaion of $K_n$ having at least $\frac{n!}{2^{n-1}}$ directed hamiltonian paths.

Lecture 2

Modelling with graphs, scheduling, job assignment, connectivity, flow, designing, bandwidth allocation, map colouring. Definitions: Paths, Walks, Trails, Cycles, Complete graphs, complement, Degree, bipartite graphs. Some simple theorems. Isomorphism. Petersen graph different representations.

Homework

  1. Prove that a graph any two paths of maximum length in a connected graph must have a common vertex.
  2. Prove that every closed walk of odd length contains an odd cycle.
  3. Prove the first theorem of graph theory: $\sum_{v\in V} d(v) = 2|E|$.
  4. If $u,v$ are distinct vertices of $G$, every $u-v$ walk contains a $u-v$ path.
  5. Prove that a graph is bipartite iff every subgraph $H$ contains an independent set of size $\frac{1}{2}|V(H)|$.
  6. If $\delta(G) \ge 3$, then $G$ must contain a cycle of even length.

Lecture 1

The Pigeonhole Principle: Further Applications: Erdos-Szekeres Theorem. Graphs: Definition and examples, representation.

Homework

  1. Using Pigeonhole Principle prove that every lossless compression algorithm must result in increasing the file size for some inputs.
  2. Let $G$ be a graph with minimum degree $\delta(G) \ge \frac{n-1}{2}$. Prove that $G$ is connected.
  3. Show that any set of $n$ people have at least two with the same number of friends.
  4. Given any ordering of a set of $n$ distinct positive integers, there is a subset of numbers consecutive in the given order, whose sum is divisible by $n$.
  5. Let $f$ be any polynomial with integer coefficients. If $f(a)=6$, $f(b) = 7$ and $f(c)=6$ for 3 integers, then $a,b,c$ are consecutive integers.

Lecture 0

Outline of course syllabus:

Recap of basics: Degree, walks, paths, cycles, trails, isomorphism, components. Trees and properties. Spanning trees. Eulerean graphs, Ringel's conjecture and graceful labelling. Algorithms: Minimum Spanning Tree:Prim, Kruskal. Shortest Path: Dijkstra. Matching: Berge's theorem and Halls Theorem. Maximum bipartite matching (asmt), Tutte's 1-factor theorem, Edmond's blossom algorithm (external lecture). Connectivity: Mengers theorem. Flow: Ford-Fulkerson, Max-flow min-cut. Planar graphs: Recap, Crossing number. Graph colouring : (Assignment). Elements of logic: Modelling with graphs (Assignment). Combinatorics: Recap of Basic counting. Generating functions and recurrence relations. Pigeonhole principle, Recap of inclusion exclusion principle. Probabilisitc Method, Discharging Method. Some recent results in graph theory (reading and presenting results from recent papers) Additional topics as seen fit.
Pigeonhole Principle, a first glance: Any $n+1$- subset of $[2n]$ contains two numbers such that one divides the other.


Thanks must go to my friend Amri from whose page I stole the template.