PAST TALKS
Feb 10, Gaurav Singh, On Moore graphs of diameter 2 and 3
For positive integers d and k, a (d,k)-Moore graph is a d-regular graph of diamter k and girth 2k+1. In this talk, I will present a beautiful result of Hoffman and Singleton asserting that for k=2 and 3, there are only finitely many Moore graph. In particular, for k=2, the only possible values of d are d=2,3,7,57.
Feb 12, David Xiao, On the independence number of triangle-free graphs
Let G be a triangle-free graph on n points with average degree d. We give a lower bound to the Independence number of such graphs. We then discuss the significance of this result in regards to the Ramsey Numbers. We also consider bounds on the independence number when G contains a limited number of triangles.
Feb 14, Charles Liu, The max-flow and related problems as linear programs with integer solutions
The maximum flow problem is a famous optimization problem where,
given a directed graph with nonnegative capacities on each edge, we are
asked to find the maximum flow from a specified source vertex to a specified
sink vertex, where the flow on each edge does not exceed its capacity.
In this talk, I will present a formulation of the max flow problem as a
linear program. I will also present variations of the max flow problem
and contrast their LP formulations with that of the Knapsack problem, a
famous NP-Complete problem.
Feb 18, Deepak Narayanan, Dijkstra's algorithm
In this talk, I will present Dijkstra’s algorithm, which is a graph search algorithm that aims at solving the single-source shortest path problem for a graph with non-negative edge weights. I will present the algorithm Edgar Dijkstra originally proposed in his 1959 paper and prove its correctness. I will also briefly describe data structures that can make an implementation of Dijkstra’s algorithm more efficient than the basic implementation.
Feb 19, Kelly Peterson, On the Conjugate Gradient Method: Practical Applications for Solving Linear Systems and Optimization Problems
The conjugate gradient (CG) method is an important method for solving sparse systems of linear equations and for solving nonlinear optimization. In this talk, I will focus on the motivation behind the method, its implementation as an algorithm, and its practical applications in computer programs. First, I will present its use as a direct method, and its advantage over traditional methods of solving systems of linear equations. I will then focus on its practical use as an iterative method, whose properties lend itself to a fast and widely applicable algorithm.
Feb 21, Rex Lam, Proofs of Arrow's theorem
Arrow's Theorem is an important result showing that showing that it is impossible to construct a voting system that abides by unanimity, independence of irrelevant alternatives, and the lack of dictatorship. My talk will explore several proofs of the theorem, all of which use the existence of an extremely pivotal voter that can move a candidate from the bottom to the top singlehandedly. I will also give some simple real life examples of the theorem at work.
Feb 24, Tomer Mangoubi, On the structure of graphs with bounded clique number
The Andrasfai-Erdos-Sos theorem gives a lower bound for the minimum degree of (r-1)-colourable Kr free graphs. Originally, Andrasfai, Erdos, and Sos proved the theorem using a lengthy proof based on induction on r. I present a shorter, simpler proof by Stephan Brandt that first proves a structural result of maximal Kr free graphs which in turn allows for a proof of the Andrasfai-Erdos-Sos theorem.
Feb 26, Uddhav Sharma, Discrete Fourier transform / Fast Fourier transform
In this talk I will introduce the Discrete Fourier Transform which takes O(n^2) while calculating it naively. I will then present Fast Fourier Transform which is an algorithm to organize calculations that leads to computation whose operation time is O(n log n). This improvement in operation time allows us to do many calculations efficiently such as convolution, polynomial multiplication and large number multiplication.
Feb 28, Keren Gu, On the First Application of Ramsey's Theorem
In this talk, I will present Ramsey's Theorem and its first application. Ramsey's Theorem states that in any coloring of the edges of a sufficiently large complete graph, these exists a monochromatic complete subgraph. Its first application, presented by Erdos and Szekeres' paper in 1935 , asks whether we can find for a given n a number N(n) such that from any set containing at least N points, it is possible to select n points forming a convex polygon. I will use Ramsey's Theorem to show the existence of such number N.
Mar 3, Iris Xu, Dinitz problem
In this talk, I will present the proof of the Dinitz conjecture, proposed in 1979 by Jeff Dinitz and proven in 1994 by Fred Galvin, and its relationship to graph theory and the list chromatic index. The conjecture states that given an n by n array, a set of m colors, and for each square of the array an n-element set of colors drawn from the m colors, it is possible to color each square with one of those colors so that no row or column repeats a color.
Mar 5, Youyang Gu, Random Walks and Gambler’s Ruin
I will introduce the theory behind random walks, using basic probability and Markov chains as the foundation. A random walk is defined as a discretized path consisting of random steps, and is often represented with a transition matrix of probabilities. After the concept of random walks has been established, I will apply it to the gambler’s ruin problem and present a closed-form solution. First formulated in 1656 by Blaise Pascal, it poses the question: given a game with a winning probability of p and a starting capital of I, what is the probability that one goes broke before reaching a capital of N?
Mar 7, Joel Schneider, Generating Functions and the Rogers-Ramanujan Identities
Generating functions have unique applications to the study of partitions and proofs of identities of the form "There are the same number of restricted partitions p' of an integer n as there are differently restricted partitions p'' ." In this talk, I will present why generating functions are helpful to us in these types of problems, find an expression for the number of unrestricted partitions of n, and then move on to proving the first Roger-Ramanujan identity: "There are the same number of ways to partition n such that every part differs by at least 2 as there are to partition n such that each part is congruent to either 1 or 4 modulo 5."
Mar 10, Thomas Zhang, Combinatorial proofs of Ramsey type problems
In this talk, we will examine combinatorial proofs for two Ramsey type problems in small cases, which will provide insight into the general case. The first Ramsey type problem deals with the existence of arithmetic progressions in r-colorings of the integers. Van der Waerden's theorem states that for any r and k, there exists some integer N=W(r,k) such that if the integers 1 through N are r-colored, there will exist a k long artihmetic progression. We will give combinatorial proofs for upper bounds on W(2,3) and W(3,3). The second Ramsey type problem deals with r-colorings of an integer lattice. We will show that no matter how we r-color the lattice points in the plane, there exists a monochromatic rectangle, and even a monochromatic square. This can be seen as a specific case of the multidimensional van der Waerden theorem, but we will prove it combinatorially.
Mar 12, Kelly Peterson, The Complementary Slackness Theorem
Linear programming (LP) is an important form of mathematical optimization. LP-formulation allows previously constrained problems to be solved in polynomial time, and reduces the number of optimal solutions that must be checked. In this talk, I will present several theorems key to the linear programming method, including duality. Then, I will then present the proof of the Complementary Slackness Theorem, which shows it is possible to obtain the optimal solution to the dual when only the optimal solution to the primal is known.
Mar 14, Rex Lam, Random Shuffling: Top-in-at-random Shuffle and Riffle Shuffle
In this talk, we will explore the question of how many times we need to shuffle for a deck of cards to be random. In particular, we will discuss top-in-at-random shuffle and riffle shuffle. We will see that the former boils down to the coupon collector problem while the latter uses the birthday paradox.
Mar 17, Tomer Mangoubi, Short Proofs of Classical Theorems
I present several short, reasonably intuitive proofs of several of the classical theorems in Graph Theory. The versions of these proofs I will be presenting are due to J.A. Bondy. Theorems include Ore's, Brooks',Vizing's, Lu's, and Gutin's theorem as well as the Chvatal-Lovasz Theorem.
Mar 19, Uddhav Sharma, On Kemnitz’ conjecture concerning lattice-points in the plane
In 1961, Erdos, Ginzburg and Ziv proved a theorem that says each set of 2n-1 integers contains a subset of size n whose sum is divisible by n. In this talk I will prove this theorem and extend this to the lattice points in a plane. The extended proof is Kemnitz's conjecture which states that given 4n-3 lattice points in a plane, there exists a subset of size n such that the centroid of these n lattice points is also a lattice point.
Mar 21, Keren Gu, Lattice Paths and Determinants
When Ira Gessel and Gerard Viennot discovered their counting lemma, they also discovered how the lemma could be successfully applied to a variety of difficult combinatorial problems. In this talk, I will introduce and prove the Gessel-Viennot lemma and given examples on how it applies to other seemingly disconnected combinatorial problems.
Mar 31, Iris Xu, The Lovász Number as an Upper Bound of Shannon Capacity of a Graph
Claude Shannon, the father of information theory, posed the question of what is the maximum rate of transmission such that receiver may recover the original message without error. Shannon modeled the channel as a graph and was able to find the capacity for many simple graphs, but not for the 5-cycle graph C_5. It was not until 20 years later that Lovász was able to find an upper bound known as the Lovász number that showed the capacity for C_5 is sqrt(5). I will present the proof for this upper bound.
Apr 2, Youyang Gu, Kelly Criterion
I will build upon the concept of gambler’s ruin covered in my first talk by posing the question: is there an optimal betting strategy for a given probability of winning? The answer is yes, and is given by the Kelly criterion. This criterion aims to maximize the expected value of the logarithm of wealth. I will go over the derivation of the Kelly criterion, as well as its applications to gambling and the stock market.
Apr 4, Joel Schneider, Using Kasteleyn Signings and Perfect Matchings to Count Tilings
In this talk I will discuss the importance of tilings of regular polygons and how to count them. It is useful to count the number of tilings of a given grid, but calculating these large numbers is difficult and computationally intensive. I will present how we can convert these tiling problems into vertex matching problems in graph theory. I will then use Kasteleyn Signings to show how the number of tilings is related to determinants of adjacency matrices. Through this, we will develop a method to counting tilings of a general grid as well as the specific formula for tiling an m by n chessboard.
Apr 7, Deepak Narayanan, Combinatorial proof of number of k-component multipartitions of a non-negative integer
In this talk, I will present the general idea of counting proofs. I will first talk about the main ideas needed to prove a theorem combinatorially, and will then prove some simple theorems involving Fibonacci and Catalan numbers to show how combinatorial proofs work in practice. I will conclude my talk by delving into a much more involved and elegant combinatorial proof for the number of k-component multi-partitions of a non-negative integer.
Apr 9, Gaurav Singh, The Turan number of F_{3,3}
A 3-graph is a graph where each edge corresponds to a triple of vertices, instead of a pair. The Turan number for a graph G is the maximum number of edges a graph with n vertices can have without containing G as a subgraph. In this talk, we investigate the Turan number of a particular 3-graph, and compute it exactly.
Apr 9, Thomas Zhang (presented in another section), Cake Cutting Problem
The cake cutting problem is a famous game theory problem that deals with the fair
division of goods. Given a cake and a set of n people, a cake cutting algorithm is fair
(envy free), if each person receives at least 1/n of the cake by his own measure. In this
talk, we will examine discrete solutions to the cake cutting problem for n = 2 and 3,
as well as continuous moving knife algorithms. We will also analyze bounds on the
cake cutting problem both in terms of number of cuts required and complexity in the
number of queries.
Apr 11, David Xiao, Combinatorial Nullstallensatz
We present a general algebraic technique and discuss some of its numerous applications in Combinatorial Number Theory, in Graph Theory and in Combinatorics. These applications include results in additive number theory and in the study of graph coloring problems. We discuss a few of these results, some new, some old.
Apr 11, Rex Lam (presenting in another section), Shannon's Entropy Theorem, Huffman Code, Lempel-Ziv Code
In this talk, I will show the proof of Shannon's entropy theorem, which states that (1) one cannot compress data such that the average number of bits per letter is less than the entropy of the data source and (2) there exists codes that approach this lower bound. I will also discuss Huffman Code and Lempel-Ziv Code and analyze how much we can compress data with these algorithms.
Apr 14, Charles Liu, Cayley's Formula
Cayley's formula gives the number of trees that can be constructed on a
set of n labeled vertices. In this talk, I will present a proof of
Cayley's formula using Prufer sequences. Then, I will extend Cayley's
formula to not just trees but forests of trees on the set of vertices and
show that the original Cayley's formula is a special case of this more
general result.
Apr 16, Uddhav Sharma, Hadamard Matrices and Designs
An m x m matrix H = (h_ij) is an Hadamard matrix of order m given (1) the entries of H are either +1 or -1 and (2)HH' = mI. I will show how Hadamard matrices of order 4t (t > 1) can be used to create symmetric BIBD's, which are called Hadamard 2-designs. Then I will prove a theorem which shows that the 3-design is the unique extension of the 2-design.
Apr 18, Keren Gu, Creating Pseudorandom Number Generators with Random Walks on Expander Graphs
Expander graphs are sparse graphs with strong connectivity properties and many applications in computer science, geometric group theory, and in number theory. In this talk, I will given definitions and examples of expander graph. Then I will show how random walks on expander graphs will yield a sequence of vertices that are close to uniformly sampled. Lastly, I will show how we can create a pseudorandom number generators with random walks on expander graphs.
Apr 23, Iris Xu, Properties of transmitting over a channel and capacity of Weighted Graphs
Shannon considered the transmission of messages over a channel with zero probability of error, introducing the idea of the zero-error capacity of a channel. We introduce several other definitions and properties of channels, including the possibility of weighted channels and analyze a few simple cases.
Apr 25, Youyang Gu, Inference on Hidden Markov Models
Hidden Markov models (HMMs) are statistical systems whose underlying processes are characterized by the Markov property with unobserved (hidden) states. They represent probability distributions over sequences of observations, from which information about the hidden states can be derived. In this talk, I will explore two algorithms for inference on HMMs. The forward-backward algorithm uses marginal distributions to compute the distribution over hidden states of a latent variable To calculate the most likely state sequence for a given observation sequence, we modify the forward-backward algorithm to obtain the Viterbi algorithm.
Apr 28, Joel Schneider, The Art Gallery and Fortress Problems
In this talk, I will introduce the topic of visibility problems and we will examine two problems in particular: the Art Gallery Problem and the Fortress Problem. These problems both ask the question of how many cameras are necessary to cover the interior or exterior of a given polygon. We will discuss how the two problems relate to visibility and how to find an upper bound for the number of necessary cameras. To do this, I will illustrate how these problems can be connected to triangulation and graph coloring. These problems have numerous extensions and variations which we will also touch on briefly.
Apr 30, Thomas Zhang, The Johnson-Lindenstrauss Lemma
The Johnson-Lindenstrauss lemma states that a set of points in a high dimensional
space can be embedded into a lower dimensional space while nearly preserving distances.
Specifically, any set of n points in R^d can be embedded into a lower dimensional metric
space R^k with a distortion factor of at most (1±eps), where k is a function of the error
tolerance eps. The Johnson-Lindenstrauss lemma has applications for data compression,
machine learning, and graph embedding. In this paper, we give a proof of the lemma
which in turn gives rise to an algorithm to implement it as well.
May 2, Gaurav Singh, The Hadwiger Debrunner (p,q) Conjecture
A family F of sets has the (p,q) property if for every subset S of size p of F, there are q sets in S which have nonempty intersection. Then, the Hadwiger Debrunner conjecture states that if F is a family of convex, compact sets in R^n, then there is some f(p,q,n) such that there is a set of at most f(p,q,n) points that has nonempty intersection with each set in F.
May 5, David Xiao, Prisoner's Dilemma and the Zero Determinant Strategy
The Iterated Prisoner's Dilemma is well known problem in Game Theory with a supposedly well known result - the only good strategy is Tit-for-Tat. Two years ago however, researchers used a novel analysis of the game to discover a new class of strategies called the Zero-Determinant (ZD) Strategies, which allow a player to unilaterally set an opponent's maximum payoff. Evolutionary analysis show the strategy to be evolutionarily unstable, but this is reversed if the ZD player can identify other ZD players.
May 7, Charles Liu, The probabilistic method
The probabilistic method is a power method used to prove the existence of objects with certain properties — by showing that a random object satisfies our desired properties with nonzero probability, we conclude that at least one such object must exist. It is a widely applicable method and often produces elegant results. In my talk, I will introduce the method and other tools that are commonly used, then give four examples of its application.
May 9, Kelly Peterson, Rayleigh's Monotonicity Law Applied to Random Walks
Rayleigh’s Monotonicity Law is an important law from electric network theory and states that, if the resistances of a circuit are increased, the effective resistance between any two points can only increase, and if they are decreased, it can only decrease. In this talk, I will first show the connection between random walks and electric networks. Using this relationship, I will then prove that Rayleigh’s Monotonicity Law holds for random walks, and can be used to more easily solve probability problems pertaining to a random walk on a finite graph, G.
May 12, Deepak Narayanan, The probabilistic method
The probabilistic method is a non-constructive method, primarily used in combinatorics and pioneered by Paul Erdos, for proving the existence of a prescribed kind of mathematical object. In this talk, I will introduce the basic ideas behind the probabilistic method through some simple applications, and then expand on these ideas by looking at harder problems, including a lower bound for the Ramsey number R(s,s), a lower bound on the crossing number of a graph, as well as a result in number theory.
May 14, Tomer Mangoubi, Network Centrality Measures
The centrality of a node in a network is intuitively understood as a measure of how important that node is to the general functioning of the network. I summarize some of the many ways to define centrality (including the Degree, Eigenvector, and Katz-Bonacich Centrality measures), give intuition as to their use, and describe their applications. Furthermore, since as a heuristic measure centrality has not found a common formal definition, I also present an interesting result by Dequiedt and Zenou that develops a formal, axiomatic characterization of a subclass of centrality measures.
