Rutgers Graduate Combinatorics Seminar - Archives

Fall 2021 Abstracts

Date:	Wednesday, December 8
Speaker:	Maxwell Aires
Time:	2:20PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	Counting Angles in Discrete Point Sets
Abstract:	A recurring problem in extremal discrete geometry is to ask for an upper or lower bound on the number of instances of a certain configuration in a set of n points. Important examples of this include the number of lines through k or more points (answered in the famous Szemeredi-Trotter Theorem), and the number of pairs of points at a fixed distance. In this talk, we consider the number of angles with a given measure alpha from n points in the plane, and derive an upper bound of O(n^2log n) from Pach and Sharir. We then show that this bound can be achieved for many values of alpha.




Date:	Wednesday, November 27
Speaker:	Rashmika Goswami
Time:	2:20PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	An Overview of the Parallel Repetition Theorem
Abstract:	Given a cooperative 2-player, 1-round game, we can consider its value - the maximum probability that the two players will win. The way the value changes when you repeat the game multiple times in parallel is unexpectedly nontrivial. I will discuss some of the work that led up to the formulation and resolution of the parallel repetition conjecture (including an application of Ramsey theory), as well its role in the field of probabilistic proofs.




Date:	November 10, 2021
Speaker:	Minhao Bai
Time:	3PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	Diameter of Polyhedral Graphs
Abstract:	In this talk, I'm going to introduce polyhedral graphs and the problem estimating the diameter of a d-dim polyhedral graph with n facets. The problem is interesting in calculating the complexity of linear optimization algorithms. We will see different upper bounds of the problem.




Date:	October 27, 2021
Speaker:	Brian Pinsky
Time:	3PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	Finite Axioms of Choice
Abstract:	The axiom of choice says "every set of non-empty sets has a choice function". This has some well known, slightly problematic consequences. However, abandoning AC can result in much much worse consequences (e.g. the reals are a countable union of countable sets). This has led mathematicians think of lots of weaker axioms over the year. In this talk, I'll give an overview of a bunch of several of these axioms. Some are stronger than others, but which ones are how strong can be hard to tell. The axioms "every set of n-element sets have a choice function" turn out particularly interesting; studying the implications will take us through some vary fancy combinatorics, and a presumably open question that's been bothering me for like years now.




Date:	October 6, 2021
Speaker:	Robert Dougherty-Bliss
Time:	3PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	The Real Reasons Linear Algebra is Useful or: A Love Letter to Traditionalists
Abstract:	The divide between traditional and experimental combinatorialists is at a breaking point. In a recent talk, it was claimed that linear algebra is useful because of set systems and discrete geometry. These are surely important applications, but nowhere were the basic linear algebra tools of an experimentalist: Deriving recurrence relations, automatic summation, and systems of equations. I will give an experimental take on linear algebra, hopefully bringing us together as a family once more.




Date:	September 22, 2021
Speaker:	Corrine Yap
Time:	3PM
Place:	Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom
Title:	The Real Reasons Linear Algebra is Useful
Abstract:	How many lines are determined by n points in the plane? How many pieces of smaller diameter are needed to cover a bounded subset of R^d? These combinatorial questions can surprisingly be answered using fundamental concepts from linear algebra. In this talk, we'll see some basic and some not-so-basic applications of linear algebraic methods to solve problems about set systems, discrete geometry, and more.

Spring 2021 Abstracts

Date:	April 21st, 2021
Speaker:	AJ Bu
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Enumerating Restricted Dyck Paths with Context-Free Grammars
Abstract:	I will be giving a talk on my joint paper with Robert Dougherty-Bliss, "Enumerating Restricted Dyck Paths with Context-Free Grammars". The number of Dyck paths of semilength n is famously C_n, the nth Catalan number. This fact follows after noticing that every Dyck path can be uniquely parsed according to a context-free grammar. Doron Zeilberger showed that many restricted sets of Dyck paths satisfy different, more complicated grammars, and from this derived various generating function identities. We take this further, highlighting some combinatorial results about Dyck paths obtained via grammatical proof and generalizing some of Zeilberger's grammars to infinite families.




Date:	April 7th, 2021
Speaker:	Jason Saied
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Motivated proof of the Rogers-Ramanujan identities
Abstract:	The Rogers-Ramanujan identities are a pair of deep partition identities that were first proven by Rogers in 1894 and (independently) Ramanujan in 1917. In the following years, a variety of different proofs were given, but they mostly took the form of verifications: the proofs relied on having guessed or been given both sides of the identities in advance. We will discuss an argument called the "motivated proof," first given by Andrews and Baxter in 1989, in which they proved the Rogers-Ramanujan identities by starting with only one side of the identities. It is very cool, different from anything else I have seen, and doesn't openly use any algebra. (At the very end, I will try to ruin it by explaining how it might connect to algebra after all.) If you know what a generating function is, you should understand everything except the last 5-10 minutes.




Date:	March 24th, 2021
Speaker:	Corrine Yap
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Reconstructing random pictures
Abstract:	Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. Objects such as graphs, abelian groups, and geometric sets. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) and prove a nearly-sharp threshold. Our main proof technique is an interface argument commonly used in percolation theory.




Date:	March 10th, 2021
Speaker:	Rashmika Goswami
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	The Chvátal-Rödl-Szemerédi-Trotter Theorem
Abstract:	The Ramsey number r(G) of a graph G is the minimum number n such that any two-coloring of the edges of a complete graph on n vertices will contain a monochromatic copy of G. It is known that for the complete graph, r(K_n) grows exponentially in n. However, for graphs of bounded degree, Chvátal, Rödl, Szemerédi, and Trotter showed that this number is (asymptotically) much smaller. This result also illustrates a nice application of Szemerédi's Regularity Lemma.




Date:	March 3rd, 2021
Speaker:	Quentin Dubroff
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Random Talks
Abstract:	I will give an introduction to random walks on graphs, deriving some useful identities and touching upon the fruitful analogy to electric networks. I'll then apply what has been developed to show the existence of short universal transversal sequences.




Date:	February 17th, 2021
Speaker:	Charles Kenney
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Stopped Sequences and the Narayana-Zidek-Capell Numbers
Abstract:	Let b=(b_1, b_2, b_3, ...) be a sequence of 0s and 1s. We say b is stopped at time T if, for every index t in (T/2, T], b_t = 0. The stopping time of b is the smallest T such that b is stopped at time T, if it exists; otherwise b has infinite stopping time. For instance, the sequence (1,0,1,1,0,0,0,0,1) is stopped at times 2 and 8, and has stopping time 2. The Narayana-Zidek-Capell (NZC) numbers, A002083 in the OEIS, were introduced by Capell and Narayana (1970) to enumerate what they called ``random knock-out tournaments." We give two proofs that the set of sequences with stopping time 2n is enumerated by the NZC sequence, and then discuss related problems and generalizations (some new, some well-known), such as ``how likely is a random binary sequence to have finite stopping time?" and ``what can we say about natural numbers whose binary expressions have certain stopping times?"




Date:	February 3rd, 2021
Speaker:	Yuchen Wei
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Hook Length Formula
Abstract:	What is the number of standard Young tableaux for a given partition? And why do we care about the number of standard Young tableaux? It turns out that we can quickly compute it by invoking the hook length formula which only involves the number of boxes in the partition and the hook lengths (isn't it nice?). To answer the second question, one reason is that the number of standard Young tableaux of a given partition is equal to the dimension of the irreducible representation (over the complex field) associated with the given partition! This reveals the true beauty of the hook length formula: combinatorics at one end and algebra on the other. But we will only focus on the combinatorics in the talk. I will sketch a short probabilistic proof then quickly move to an elegant bijective proof given by Igor Pak. Time permitting, we will also talk about the RSK as a corollary.

Fall 2020 Abstracts

Date:	December 9th, 2020
Speaker:	Aditi Dudeja
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Gomory-Hu trees
Abstract:	The all-pairs minimum-cut size problem asks for a minimum s-t cut over all pairs of vertices s, t. This can clearly be solved in time O(n^2 T) where T is the time take for computing a minimum s-t cut for any given s,t. Gomory and Hu showed that for undirected graphs it can be done faster, and there is a concise structure, the Gomory-Hu tree to represent all minimum cuts. In this talk, I will prove that for any graph G, a Gomory-Hu tree exists and can be found using n-1 min-cut computations.




Date:	November 18th, 2020
Speaker:	Robert Dougherty-Bliss
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Automagic Inverse Continued Fraction Calculators
Abstract:	The well-exploited theory of SIMPLE continued fractions has produced some dazzling identities and wonderful irrationality proofs. The often-overlooked theory of GENERAL continued fractions is harder to champion, but just as, if not more, interesting. A recent project (viz. The Ramanujan Machine) tried to numerically "fit" general continued fractions to well-known constants, hoping to find very good rational approximations. To highlight the power of symbolic experimentation, I will tour us through automatically proving some of these conjectures and generalizing them to infinite families.




Date:	November 11th, 2020
Speaker:	Rashmika Goswami
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Triangle-Intersecting Families of Graphs
Abstract:	We say a family of graphs is triangle-intersecting if the intersection of any two graphs in the family contains a triangle. If we consider graphs on n vertices, how large can such a family be? It is clear that we can get 1/8 of the graphs by fixing a triangle and taking all of the graphs containing that triangle - such a family is called a Δumvirate. In fact, as Ellis, Filmus, and Friedgut showed in 2012, this is the best we can do: not only is such a family the unique extremal example, it is also stable in the sense that any family with size close to the upper bound is close to a Δumvirate. I will go over this proof, which uses an interesting combination of techniques from different areas of combinatorics.




Date:	October 28th, 2020
Speaker:	Matthew Russell
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Partition identities, q-series identities, and experimental mathematics
Abstract:	I will talk about partition identities and q-series identities (and especially identities in the intersection of those two sets), and the use of computer algebra systems in experimentally discovering them. There won't be any real background knowledge assumed, other than basics of generating functions - I'll tell you what a partition is and what a q-series is (it's a series that has qs in it).




Date:	September 30th 2020
Speaker:	Quentin Dubroff
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	Sidon sets and subset sums
Abstract:	This two part talk will be centered around the theme that sets of integers in [n] avoiding certain combinatorial configurations cannot be too large.




Date:	September 30th 2020
Speaker:	Tae Young Lee
Time:	12:15PM
Place:	Zoom: please email quentin [dot] dubroff [at] rutgers [dot] edu to be added to the mailing list
Title:	The Erdős-Szekeres conjecture
Abstract:	Imagine five points in R^2, where no three of them are colinear. You can always find a convex quadrilateral among them. How many points do you need for a convex pentagon? What about a convex k-gon? Is it even possible? Erdős and Szekeres proved that this is indeed possible whenever you have at least ES(k) points in general position, where ES(k) is some number not exceeding ((2k-4) choose (k-2))+1. They conjectured that ES(k)=2^{k-2}+1, and later proved that this is a lower bound. I will present their proofs about these facts and a sketch of the proof of the best known upper bound by Andrew Suk. If time permits, I will also briefly discuss some variants and generalizations of this problem.




Date:	September 23th 2020
Speaker:	Corrine Yap
Time:	12:15PM
Place:	Zoom
Title:	Dependent Random Choice
Abstract:	I will introduce a probabilistic technique called dependent random choice, which allows us to analyze dense graphs and find many small sets of vertices with large common neighborhoods. We'll discuss applications of this tool to Turán-type problems where we want to find an isomorphic or homeomorphic copy of a fixed subgraph inside a larger graph, and Ramsey problems where we want to find a monochromatic subgraph inside an edge-coloring of a larger graph.




Date:	September 16th 2020
Speaker:	Andre Hernandez-Espiet
Time:	12:15PM
Place:	Zoom
Title:	Permutation Puzzles: Rubik's cube and 15-puzzle
Abstract:	In this talk I will be talking about permutation puzzles. These refer to puzzles in which every valid move performs a permutation of these numbers and can be undone. One clear example of this is the 15-puzzle. One less obvious example (at first) is the Rubik's cube. I will be giving solvability criteria, counting the number of configurations, and calculating the probability of being able to solve from a random starting point.

Spring 2020 Abstracts

On March 13, 2020, Rutgers announced that all instruction would move online for the remainder

of the semester due to coronavirus, so GCS was put on hold.

Date:	March 11, 2020
Speaker:	Keith Frankston
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Automorphisms of Induced Subgraphs of Gn,p.
Abstract:	The Erdős Rényi random graph (denoted Gn,p) is a random object on n vertices where each edge appears independently with probability p. We call a graph rigid if it has no non-trivial automorphisms. A classical result in random graph theory states that the probability that Gn,p is rigid goes to 1 (as n goes to infinity) for p(1-p)>>log(n)/n. In this talk we discuss what happens when we instead at look at induced subgraphs of Gn,p. We will show that almost surely any induced subgraph of sufficient size is rigid by proving a more general result.




Date:	March 4, 2020
Speaker:	Charles Kenney
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Electric Networks and Square Tilings
Abstract:	Can a rectangle be tiled by finitely-many squares of distinct side lengths, which are almost-disjoint (intersect only at the boundary)? It turns out that this recreational math problem of squaring a rectangle can be related to electrical networks. We'll use graph theory to deduce a necessary condition, originally due to Dehn, for a rectangle to be squared.




Date:	February 26, 2020
Speaker:	Nathan Mehlhop
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	How many ways can a permutation in S_n be written as a product of k transpositions?
Abstract:	To answer the question in the title, we will develop a systematic method for calculating these numbers using the adjacency matrices of certain directed graphs whose vertices are the conjugacy classes of S_n. I will mumble without proof some connections to the representation theory of S_n and to symmetric functions, and then prove a few identities using facts about Ferrers diagrams.




Date:	February 19, 2020
Speaker:	Brian Pinsky
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Squags, Sloops, Quasigroups and Loops: Using made-up words to find Latin Squares
Abstract:	What do groups, semirings, lattices, and magmas all have in common? Well, if you squint hard enough, all of their definitions are essentially the same: they're sets with a bunch of operations that have to satisfy a bunch of equations. Moreover, all of these structures have a lot in common: all of them have a 0 object, a direct product, a notion of homomorphism, etc. In fact, they have so much in common, you could make an entire field of math just studying just how similar they are. They did that, and they called it universal algebra. Like any worthwhile field of math, universal algebra has tons of pun-tastic and ridiculous words, surprising and powerful theorems, and almost no useful applications whatsoever. But while it's generally useless, it turns out there are some combinatorics topics where it's incredibly useful, and that's what this talk will be about. Specifically, we'll talk about latin squares and some special kinds of hypergraphs. Latin squares are grids like sudoku puzzles; each number must occur in each row and column exactly once. They seem friendly enough, but studying latin squares is generally quite hard. Looking at this with universal algebra gives a nice reason why it might be hard: latin squares correspond precisely to cayley tables of quaisigroups (a universal variety), so the theory of latin squares should be at least as hard as group theory, plus whatever complications this "quasi-" prefix adds. Orthogonal latin squares are n by n latin squares which, when stacked on top of each other, contain all the n^2 possible pairs of numbers as columns. It turns out, these correspond to another universal variety. My main goal this talk is to use that characterization to construct as many orthogonal latin squares as I can. Euler conjectured that it was impossible for n=2 mod 4, and we're going to prove he was wrong.




Date:	February 12, 2020
Speaker:	Jinyoung Park
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	On symmetric 3-wise intersecting families
Abstract:	I will give an expository talk on a nice paper by our own Prof. Bhargav Narayanan (joint with David Ellis). https://sites.math.rutgers.edu/~narayanan/pdf/symmetric_3_families.pdf . A family of sets is said to be symmetric if its automorphism group is transitive, and 3-wise intersecting if any three sets in the family have nonempty intersection. This paper proves if F is a symmetric 3-wise intersecting family of [n] then |F|=o(2^n) (so F is tiny).




Date:	February 5, 2020
Speaker:	Aditya Potukuchi
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Parallel repetition of games
Abstract:	Consider a "game" involving two players Alice and Bob (as a team), who coordinate on a strategy beforehand. The following describes one round of the "game": 1. You sample a couple of (not necessarily independent) random variables x and y, and give Alice x, and Bob y. For example, think of x and y as two parts of a question in a quiz show. 2. Alice returns with answer a, and Bob returns with an answer b without communicating. 3. They (Alice+Bob) win if V(x,y,a,b) = 1 for some function V chosen beforehand. For example, if a+b is the answer to the question x+y in the quiz show. Let p be the maximum probability (over all strategies) that Alice+Bob win the round. Here is the question: Suppose you independently sampled a bunch of tuples $(x_1,y_1), (x_2,y_2),....,(x_t,y_t)$, gave Alice all the $x_i$'s and Bob all the $y_i$'s, what is the maximum probability that they win _all_ the rounds? It's obviously $p^t$ right? Since they can't communicate and the questions are chosen independently..... This is (strangely) not quite the case. In fact, showing that it even goes down exponentially with t itself is quite difficult and is commonly called the "Parallel Repetition Theorem". I will talk about this theorem and some ideas behind the proof.

Fall 2019 Abstracts

Date:	December 4th, 2019
Speaker:	Yukun Yao
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Dynamic Programming and Combinatorial Game Theory
Abstract:	In this talk we will talk about dynamic programming and combinatorial game theory. Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure. We will see some problems that can be solved by dynamic programming. Then we will discuss impartial games, especially Nim and how we can use dynamic programming to find Sprague–Grundy function values so that we know where are winning positions and where are losing positions. A winning strategy follows. Sprague–Grundy theorem will also be mentioned.




Date:	November 20th, 2019
Speaker:	Rashmika Goswami
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Arrow's Impossibility Theorem
Abstract:	Roughly speaking, Arrow's theorem states that in an election with more than two candidates, there is no "reasonable" voting rule that gives a rational outcome. I will discuss this and related theorems, as well as giving a Fourier-theoretic proof of Arrow's theorem which sheds light on how likely rational outcomes are for any voting rule.




Date:	November 13th, 2019
Speaker:	Quentin Dubroff
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Helly's Theorem and generalizations
Abstract:	Helly's theorem states that if any d+1 or fewer elements of a finite family of convex sets in R^d have non-empty intersection then there is a point which is contained in every member of the family. I will present a proof of this theorem and will discuss its foundational role in convex geometry. I will then show how we can extract information about intersection patterns of convex sets by studying simplicial complexes following a paper of Gil Kalai.




Event:	Faculty Research Talks
Date:	November 6th, 2019
Time:	12:15PM-1:30PM (there will be a 15-minute break between talks, due to speaker schedule constraints)
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Shubhangi Saraf
Title:	Polynomial factoring and some questions about polytopes
Abstract:	I will discuss some questions on counting integer points within polytopes and an approximate version of Caratheodory's Theorem. These geometric questions are motivated by some basic questions in polynomial factoring. This is based on joint work with Vishwas Bhargava and Ilya Volkovich.
Speaker:	Swastik Kopparty
Title:	Error-Correcting Codes




Date:	October 30th, 2019
Speaker:	Keith Frankston
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Automorphisms of Induced Subgraphs of $G(n,1/2)$
Abstract:	The Erdős Rényi random graph (denoted $G(n,1/2)$) is a random object on $n$ vertices where each edge appears independently with probability 1/2. We call a graph rigid if it has no non-trivial automorphisms. A classical result in random graph theory states that the probability that $G(n,1/2)$ is rigid goes to 1 (as $n$ goes to infinity). In this talk we discuss what happens when we look, not at $G(n,1/2)$, but its induced subgraphs. We will show that almost surely any induced subgraph of size $(1 + \epsilon) n/2$ is rigid by looking at a more general result.




Date:	October 23rd, 2019
Speaker:	Vishwas Bhargava
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Burgess' bound on character sums
Abstract:	Finding the least quadratic non-residue in a finite field is of great interest in number theory, Additive Combinatorics, and Theoretical computer science. We will look into a state-of-the-art bound for this which was proved by Burgess in 1963. It is a smart proof with lots of open problems around it. Time permitting, I will also discuss some recent developments.




Date:	October 16th, 2019
Speaker:	Justin Semonsen
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	A Maximum Determinant Problem
Abstract:	Here we discuss a method for bounding the maximum determinant of a certain class of zero-one matrices. The methods are based on former Rutgers grad student Danny Scheinerman's recent thesis, although new analysis techniques allow for stronger results.




Date:	October 9th, 2019
Speaker:	Yonah Biers-Ariel
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Correlation Inequalities for Permutations
Abstract:	I will present Harris' Inequality for subsets of the Boolean cube before discussing a new correlation inequality due to Johnson, Leader, and Long which applies to sets of permutations rather than sets of binary vectors.




Date:	October 2nd, 2019
Speaker:	Corrine Yap
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Combinatorial Group Theory
Abstract:	What do groups have to do with graphs? How can one use graph properties to say something about group structure? What do the words "combinatorial group theory" even mean? We will answer these questions, and more!




Date:	September 25th, 2019
Speaker:	Jinyoung Park
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	A quick introduction to entropy
Abstract:	We introduce the entropy of a discrete random variable and discuss some quick applications. This talk is mostly based on Galvin's lecture notes: https://arxiv.org/abs/1406.7872




Date:	September 18th, 2019
Speaker:	Aditya Potukuchi
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	A spectral proof of Katona's t-intersection theorem
Abstract:	Katona's theorem stated that a maximal t-intersecting family has size at most \binom{n}{\geq (n+t)/2}. The proof is by a tricky shifting argument. We will see a Fourier proof of the same result. This proof is somewhat easy (as easy as this type of proof can get I guess), and it possibly has its own merits. The reference I will be using is the following: https://anuragbishnoi.wordpress.com/2019/07/27/spectral-proofs-of-theorems-on-the-boolean-hypercube/

Spring 2019 Abstracts

Date:	May 1st, 2019
Speaker:	Aditya Potukuchi
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Independent Sets in the Hypercube
Abstract:	I will explain an old result of Sapozhenko that counts the number of independent sets in a cube graph. The reference I will be using is this recent exposition.




Event:	Faculty Research Talks
Date:	April 24th, 2019
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jeff Kahn
Title:	Trees and Degrees
Abstract:	I'll mention a few problems on tree counts in graphs and, as time permits, try to say a little about what these might have to do with one or two topics (random methods, entropy) that I like.
Speaker:	Anders Buch
Title:	Schur Polynomials and the Littlewood-Richardson Rule
Abstract:	The ring of symmetric polynomials in a list of variables has a basis consisting of Schur polynomials that is related to many areas in mathematics, including representation theory of GL(n), geometry of Grassmannians, eigenvalues of Hermitian matrices, statistics, and complexity theory. The coefficients obtained when a product of two Schur polynomials is expanded in the basis of Schur polynomials are called Littlewood-Richardson coefficients. The classical Littlewood-Richardson rule expresses these coefficients as the number of ways of filling a diagram of boxes with integers satisfying certain conditions. I will speak about these basic notions, which are important in many parts of mathematics and have inspired many developments within combinatorics.




Date:	April 17th, 2019
Speaker:	Rashmika Goswami
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Series Multisection and the Cyclic Sieving Phenomenon
Abstract:	I will discuss two problems in combinatorics where evaluating a polynomial at a primitive root of unity will help us to count objects which are cyclic in nature. The first will involve subset sums modulo n and the second will be an illustrative example of the cyclic sieving phenomenon in the context of permutations acting on multisets.




Date:	April 10th, 2019
Speaker:	Vishwas Bhargava
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Combinatorial Nullstellensatz and List Coloring
Abstract:	We will study a more general notion of Graph Coloring in which the set of permitted colors is different for each vertex, as long as at least {k} colors are listed at each vertex. This leads to the notion of a so-called choice number, which was introduced by Erdős, Rubin, and Taylor. We will prove an interesting upper bound on choice number using Combinatorial Nullstellensatz.




Date:	April 3rd, 2019
Speaker:	Forrest Thurman
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The combinatorics of orthogonal polynomials
Abstract:	When expanding a product of orthogonal polynomials in the basis of orthogonal polynomials, the coefficients that occur often have a combinatorial interpretation as certain types of partial matchings between finite sets. I will go over some known cases of this phenomenon and some situations where the combinatorics is less understood.




Date:	March 27th, 2019
Speaker:	Jinyoung Park
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An isoperimetric inequality for the Hamming cube and some consequences
Abstract:	I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a "stability" version of Harper's edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half cubes, and later by Ellis for subsets of any size. Our inequality also plays a key role in a recent result on the asymptotic number of maximal independent sets in the cube. This is joint work with Jeff Kahn.




Date:	March 13th, 2019
Speakers:	Yonah Biers-Ariel, Corrine Yap, Danny Scheinerman, Abigail Raz
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Ten-Minute Talks
Abstract:	A subset of regular GCS attendees will give ten-minute talks on various subjects. This event was most certainly planned in advance and not due to the unfortunate incapacitation of a previously-scheduled speaker.




Date:	March 6th, 2019
Speaker:	Aditi Dudeja
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Alon-Jaeger-Tarsi Conjecture
Abstract:	The Alon-Jaeger-Tarsi conjecture states that for any field F with |F|\geq 4 and any non-singular matrix A over F, there is a vector x such that both x and Ax have only non-zero entries. I will relate this conjecture to the perrank of a matrix A which is the size of the largest square submatrix of A with non-zero permanent. I will state and prove some properties of perrank, and use these to prove a small result on the Alon-Jaeger-Tarsi conjecture.




Date:	February 27th, 2019
Speaker:	Mingjia Yang
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Relaxed Partitions
Abstract:	A partition of a positive integer n is a finite nonincreasing sequence of positive integers \lambda_1, \lambda_2 . . . \lambda_k whose sum is equal to n. We will start with some examples of generating functions related to partitions, then we will introduce the notion of relaxed partitions (or r-partitions) where \lambda_i - \lambda_{i+1} \geq r and r can be negative. For example, (2, 3, 1, 1) is a (-1)-partition of 7. We will discuss some results on the total number of r-partitions with the first part equal to M and exactly N parts (M and N are positive integers), as well as questions (some are still open!) related to generating functions, and we will see how Maple was of great help in the process of exploration and discovery.




Date:	February 20th, 2019
Speaker:	Quentin Dubroff
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Orchard Problem
Abstract:	The orchard problem asks for the maximum number of collinear triples in a finite set of points in the plane. Very recently, Green and Tao gave an upper bound on this old problem which exactly matches the known lower bound. I will construct the set which achieves this lower bound, and I'll mention some connections with number theory and algebraic geometry. I will also discuss the conjectured generalization of this problem to collinear k-tuples by Erdős, which is worth 100 dollars.




Date:	February 13th, 2019
Speaker:	Danny Scheinerman
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Unique sum-free sets
Abstract:	Call a subset A of an abelian group G unique sum free (USF) if every sum s in A+A is not uniquely represented. That is for every a and b in A there exists c and d in A with a+b=c+d and the sets {a,b} and {c,d} are different. For A in F_p we can ask how small a USF set can be. We will show a lower bound of \Theta(\log(p)) and an upper bound of \Theta(log^2 p). Closing this gap is an open problem. We'll discuss some generalizations.




Date:	February 6th, 2019
Speaker:	Yuxuan Yang
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Distribution of geodesic on cube and other surfaces
Abstract:	The distribution of a straight line on closed surface is a basic problem in mathematics. One famous result is irrational flow on torus. It is dense and uniformly distributed. A geodesic on a cube is another example after that, but the uniformity here is not as good as irrational flow on torus. Surprisingly, the representation theory will work here.

Fall 2018 Abstracts

Date:	December 5th, 2018
Speaker:	Cole Franks
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An application of non-Boolean Fourier analysis
Abstract:	The discrepancy of a red-blue coloring of the vertices of a hypergraph is the maximum imbalance between the number of red and blue vertices in any edge. The discrepancy of a hypergraph is the least discrepancy of any red-blue coloring. A major open question is whether the discrepancy of a t-regular hypergraph is O(\sqrt{t}). I will discuss some recent joint work with Michael Saks concerning the discrepancy of random regular hypergraphs.




Date:	November 28th, 2018
Speaker:	Yukun Yao
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Some Interesting Combinatorics and Probability Problems in Job Interviews
Abstract:	Combinatorics and probability are two interesting areas. And they are also very useful, not only in academia but also for non-academic purposes. In this talk, we will discuss some combinatorics and probability problems which you may be asked in job interviews.




Date:	November 14th, 2018
Speaker:	Keith Frankston
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Keith Hopefully Finally Talks About Containers
Abstract:	I might actually talk about the method of containers. This is a powerful technique that was only developed in the last decade and has been used to prove some long standing conjectures (and to simplify the proofs of many existing theorems). While we won't prove an example of a container lemma, we will instead talk about what these lemmas look like and how they can be used to prove a variety of combinatorial results.




Date:	November 7th, 2018
Speaker:	Jinyoung Park
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Important Graphs are Indeed Important
Abstract:	Earlier this semester, Aditya showed a construction of "important graphs." In this talk, we will see these graphs are indeed important. Based on Noga Alon's talk at https://www.renyi.hu/conferences/ll70/.




Event:	Faculty Research Talks (in conjunction with Graduate Algebra and Representation Theory Seminar (GARTS))
Date:	October 31st, 2018
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Bhargav Narayanan
Title:	Cutting Cake with Algebraic Topology
Abstract:	A group of people want to divvy up a piece of cake "fairly". What does "fairly" mean? How do they this? What does this have to do with the Borsuk--Ulam theorem? I will try to say something about these questions, and a bit more, time permitting.
Speaker:	Vladimir Retakh
Title:	Introduction to Noncommutative Birational Geometry
Abstract:	I will discuss several phenomena related to noncommutative triangulations of surfaces.




Date:	October 24th, 2018
Speaker:	John Chiarelli
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	It's Hard to Find a Stable Marriage: Strategic Exploitation of the Gale-Shapley Algorithm
Abstract:	The stable marriage problem is a classic one in the library of discrete math. The best-known results on the problem stem from the work of David Gale and Lloyd Shapley, who in their 1962 paper not only showed that a stable matching exists for every possible instance of the problem, but also gave an algorithm for finding such a matching. However, in applications of finding stable matchings between agents, these agents may choose to be dishonest about their preferences. In this talk, I will discuss the circumstances under which agents in the Gale-Shapley algorithm can improve their outcome by lying about their order of preference.




Date:	October 17th, 2018
Speaker:	Yonah Biers-Ariel
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An Introduction to WZ Theory
Abstract:	WZ Theory is a powerful method to automatically conjecture and prove identities involving hypergeometric series. I will give an overview of the method and important results.




Date:	October 10th, 2018
Speaker:	Abigail Raz
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Tuza's Conjecture
Abstract:	Tuza's Conjecture states that the triangle cover number is at most 2 times the triangle matching number for every graph G (don't worry, I will define what those two numbers are). Much work has been built off of this conjecture and we will take a short tour through it. We will start by discussing when the conjecture is tight and what progress has been made towards it. We will then look at two fractional versions of the conjecture and end with an extension.




Date:	October 3rd, 2018
Speaker:	Matthew Russell
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Apéry's proof of the irrationality of zeta(3)
Abstract:	Roger Apéry shocked the world in 1978 by announcing a proof that zeta(3) was irrational. A lot of the machinery here relies on sums of binomial coefficients, along with other sequences defined recursively, which makes them perfect targets for WZ machinery. I'll spend this weekend* teaching these techniques to myself, and then report to you all what I learned on Wednesday at lunch time (which will likely be a high-level overview of the proof process, with emphasis on the parts that are, indeed, shaloshable). Hopefully, it will be fun. And perhaps educational? (At least for Keith.) *Let's be honest, "weekend" probably should be replaced with "Tuesday night". Or "Wednesday morning".




Date:	September 26th, 2018
Speaker:	Aditya Potukuchi
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An Important Graph
Abstract:	I will describe the construction of an explicit (family of) graph(s) due to Alon, which has many interesting and seemingly different extremal properties. Two of these that I will try to talk about are: Triangle free, but has small non-trivial eigenvalues (I will try to justify what "but" means here). Gives graph with a small Shannon capacity but a large theta value. The topics that I will cover are strictly contained in this article: https://www.tau.ac.il/~nogaa/PDFS/ll70.pdf. There are, of course, interesting open problems related to these (I am not too familiar, but I will provide additional references for them) in case people find this interesting.




Date:	September 19th, 2018
Speaker:	Justin Semonsen
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Interactive Proofs
Abstract:	What is a proof? What is a proof to a computer? In this talk, we will develop a number of ways to prove whether two graphs are isomorphic or not, and thereby explore the power and limitations of interactive proofs.




Date:	September 12th, 2018
Speaker:	Weihong Xu
Time:	12:15PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An Algebraic Proof of Sperner's Theorem
Abstract:	My main goal in this talk is to present an interesting algebraic proof of Sperner's theorem on the size of anti-chains. This proof can also be understood using the representation theory of sl2. I learned this proof from June Huh. This talk should be accessible to people with minimal combinatorics background (I will start with basic definitions) and people without any knowledge of Lie algebras.

Spring 2018 Abstracts

Date:	April 18th, 2018
Speaker:	Yael Davidov
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Symmetric Designs
Abstract:	This talk will be about symmetric designs. Symmetric designs are mathematical objects that include but are not limited to finite projective planes and difference sets. I will define symmetric designs, give some cool examples, and provide an outline of a proof of the Bruck-Ryser-Chowla Theorem about the possible parameters of a design which uses some fun facts from algebra (quadratic forms) and number theory.




Date:	April 11th, 2018
Speaker:	Andrew Lohr
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Automating Summations
Abstract:	It's very common to have to analyze summations when working in combinatorics. Just as we would consult a computer when doing other rote tasks in mathematics, there are tools out there for evaluating summations. We'll talk about Sister Celine's technique and Gosper's algorithm. They are two of the earliest automated approaches to the proving of summation identities.




Date:	April 4th, 2018
Speaker:	Louis Gaudet
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Jacobian Group of a Graph
Abstract:	Given a (finite) graph G, there is a natural finite abelian group we can associate to G, called its Jacobian group. There are different sources of motivation for studying these groups. They are the "tropical" (i.e. piecewise-linear) analogs of classical algebro-geometric objects. They are used as models for certain physical systems - so-called "sandpile groups." The statistics of Jacobian groups of random graphs are related to the Cohen-Lenstra heuristics, which describe statistics of ideal class groups of number fields. For instance, a fun fact: the Jacobian of a random graph is cyclic just about 79% of the time. Rather than discuss these connections in depth, we'll explore a more basic question: which groups actually appear as the Jacobian of some graph? Along the way, we'll observe and exploit connections of the Jacobian group to classical graph theoretic properties of interest: planarity, counts of spanning trees, etc. We'll construct graphs whose Jacobians realize a large class of groups, and we'll prove that there are infinite families of groups that cannot be realized as the Jacobian of any graph. The general question, however, is still open, and I will point out several possible research problems.




Date:	March 28th, 2018
Speaker:	Edna Jones
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	r-Complete Sequences of Positive Integers
Abstract:	A strictly increasing sequence of positive integers (a_n) is said to be (weakly) complete if every sufficiently large positive integer is representable as a sum of distinct terms of (a_n). We extend this concept by saying a sequence (a_n) is r-complete if every sufficiently large positive integer is representable as the sum of r or more distinct elements from (a_n). We establish a number of results related to r-complete sequences. In particular, for any positive integer r we construct an example of a sequence which is r-complete but not (r+1)-complete.




Date:	February 28th, 2018
Speaker:	Richard Voepel
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	No X Points on a Y: A Class of Discrete Geometry Problems
Abstract:	First introduced in 1917 by Henry Dudeney, the No-Three-In-Line problem asks for the maximum number of points that can be placed in an N by N grid such that no three are collinear. While there have been results concerning lower bounds for this number, non-trivial upper bounds remain largely conjectural. But this is not the only problem of this form to receive attention; one may consider generalizations to higher dimensions, asking for no three points to be collinear in an N by N by N grid, or for no four points to be coplanar. We present select results for these problems, and propose further cases to study.




Date:	February 21st, 2018
Speaker:	Justin Semonsen
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Counting Random Sheep
Abstract:	We will talk about different ways to count sheep randomly, less randomly, and not randomly at all. Along the way, we might talk about expander graphs too.




Date:	February 14th, 2018
Speaker:	Sam Braunfeld
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Model Theory and Combinatorics
Abstract:	I will discuss some interactions between model theory and combinatorics. Due to the facts that I will not be assuming model theory knowledge, that I plan to discuss several topics, and that I only somewhat understand these topics myself, things will be very sketchy.




Date:	February 7th, 2018
Speaker:	Bryan Ek
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Angel Problem
Abstract:	In honor of the Super Bowl, I will be talking about the classic Angel problem by Conway. (Feel free to decide for yourself which team is the Devil). This problem went many years with only restricted progress before being solved simultaneously by several authors in 2007. I will present some of the easy early results and try to explain which side has the winning strategy in general.




Date:	January 31st, 2018
Speaker:	Keith Frankston
Time:	12:15
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Proof Methods in Combinatorics
Abstract:	The container theorem allows us to analyze the independent sets of a hypergraph by collecting each independent set in a small number of containers. This technique has led to many breakthroughs in combinatorics and number theory. Unfortunately, we won't be talking about it today. Instead I'll be presenting proofs of a couple of results each of which display an interesting proof technique.

Fall 2017 Abstracts

Date:	December 6th, 2017
Speaker:	Aditya Potukuchi
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An application of topology to a hypergraph problem
Abstract:	The chromatic number of the Kneser graph (conjectured in 1955) was a seemingly difficult open problem until it was solved by Lovasz in 1978 by using quite non-trivial ideas from topology. Using a bit of geometry, Barany (1978) turned this into an extremely short (yet non-trivial!) proof. The main idea of behind talk is to try and understand at least some of the power that is to be gained by using topological ideas to solve problems that seemingly stem (purely!) from combinatorics. In particular, the paper that will be used for this attempt is a paper by Alon-Frankl-Lovasz, who generalize Lovasz's earlier proof to hypergraphs




Date:	November 29th, 2017
Speaker:	John Chiarelli
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	What We Have Here is a Failure to Communicate: A Communication Game and Applications to the Sensitivity Conjecture
Abstract:	The sensitivity conjecture is one of the core unresolved questions of computational complexity. In this talk, I will look at one angle that has been taken in tackling this problem, via a cooperative two-player game based on communication. I will also talk about conjectures made in that direction that ultimately failed due to particular counterexamples.




Date:	November 15th, 2017
Speaker:	Matthew Russell
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Partition Bijections
Abstract:	We will look at some bijective proofs of partition identities.




Date:	November 8th, 2017
Speaker:	Andrew Lohr
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Matroids and Greedy Algorithms
Abstract:	Greedy algorithms are great when they work. They are often very fast and simple to implement. For many problems, though, it it can be misleading, sometimes giving a really far from optimal solution. We'll see how a greedy algorithm working relates to the problems having a matroid structure.




Date:	November 1st, 2017
Speaker:	George Hauser
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Counting Convex Quadrilaterals
Abstract:	How many convex quadrilaterals must occur among n points in the plane, no three of which are collinear? We will consider this question in a few small cases, and see how lower bounds in small cases induce lower bounds in general. But in order to beat the bounds that arise in this way, we must use more strongly the geometry of the underlying point set. We will demonstrate some recent techniques in this area. In the talk we will see how this question of counting convex quadrilaterals bears on the general combinatorial geometry of planar point sets.




Date:	October 25th, 2017
Speaker:	Yonah Biers-Ariel
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Combinatorial Nullstellensatz
Abstract:	Combinatorial Nullstellensatz is a surprisingly powerful proof technique based on an elementary observation. We will look at some results from Noga Alon's original paper which demonstrate the ability of this strategy to make very difficult problems quite straightforward.




Date:	October 18th, 2017
Speaker:	Danny Scheinerman
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Fifty shades of Gray codes
Abstract:	We will describe the classical Gray code and some of its nice properties. We can generalize Gray codes as walks generally through a collection of objects where each step the adjacent objects are close in some way. We'll see some examples and open problems. Hopefully this talk won't be too painful. Unless you're into that sort of thing.




Date:	October 11th, 2017
Speaker:	Abigail Raz
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	What do the largest subgraphs of K_n (or the random graph!) with a particular matching number look like?
Abstract:	There are many statements across math of the form "a structure with property X must have one of the following forms". We will see a few of these statements focusing on a result by Erdos and Gallai that every largest subgraph of K_n with matching number t must have one of two basic forms (note here largest refers to the number of edges). We will discuss this result as well as how the statement extends to random graphs.




Date:	October 4th, 2017
Speaker:	Corrine Yap
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Topological Graph Theory
Abstract:	What happens when we take the graphs we know and love and stick them on the torus? What about the Möbius strip? Or the Klein bottle?? We'll talk about how to embed graphs on "nice" surfaces in a "nice" way and give generalizations to a few familiar theorems about planar graphs. There will be no topology knowledge required. If time permits, we'll also color some stuff!




Date:	September 27th, 2017
Speaker:	Cole Franks
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Entropy
Abstract:	Shannon's entropy shows up in many places in mathematics, information theory, and computer science. After an overview of the basic concepts, I will discuss some non-obvious applications of the entropy function.




Date:	September 20th, 2017
Speaker:	Jinyoung Park
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Number of Maximal Independent Sets
Abstract:	For a given graph G, a subset A of V(G) is independent if no two vertices in A are adjacent. Some time ago, Erdos and Moser asked: what's the maximum possible number of maximal independent sets in a graph G with n vertices. In this talk we will investigate the answer to this question, and some other related questions.

Spring 2017 Abstracts

Date:	May 1st, 2017
Speaker:	Yonah Biers-Ariel
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	How To Avoid a Pattern
Abstract:	This talk will define permutation pattern avoidance classes and give some (in my opinion) surprising results regarding which patterns are easiest to avoid. Time permitting, we will then discuss pattern containment and superpatterns.

Date:	April 24th, 2017
Speaker:	Charles Wolf
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Oriented Matroids
Abstract:	Oriented matroids are a class of matroids with a geometric flavor. We will see several examples of these, and find out why you should care about oriented matroids (or at least why Charles cares).




Date:	April 17th, 2017
Speaker:	Aditya Potukuchi
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Threshold(s) for perfect matchings in graphs.
Abstract:	We will study the quite well known threshold for perfect matchings in G_{n,p}, and (hopefully) hypergraphs. Due to the relatively lengthy nature of these proofs, I will try to confine myself mostly to 'sketches' of (only) most parts the proof(s).




Date:	April 12th, 2017
Speaker:	Mike Donders
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Ergodic Ramsey Theory
Abstract:	Ergodic theory, being the study of invariant measures of dynamical systems, and Ramsey theory, being the study of structures within partitions of sets, seem like they would have little relation to each other. However it turns out that the two are very much connected and many Ramsey theory problems can be solved using methods from ergodic theory. In this talk we will see some examples of this and the link between ergodic and Ramsey theory.




Date:	April 5th, 2017
Speaker:	Rebecca Coulson
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Exploring the connections between model theory and combinatorics
Abstract:	Model theory, the area in mathematical logic which focuses broadly on mathematical theories and structures, has long been show to have applications to other areas of mathematics. Some of these famously include the Mordell-Lang Conjecture, Ax's Theorem, and the Nullstellensatz. In this talk, we will explore the nature of the connections between model theory and combinatorics, as well as examine a few examples. This talk is intended to be educational and entertaining, and I hope you all can make it!




Date:	March 29th, 2017
Speaker:	Jinyoung Park
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Counting maximal antichains and independent sets
Abstract:	Counting the number of antichains in the Boolean algebra is known as Dedekind's problem and the asymptotic of this number is known. In this talk I will discuss the number of maximal antichains in the Boolean algebra and the number of maximal independent sets in the hypercube. We will see the asymptotics for the logarithm of these numbers and how they are closely related to the size of the maximum induced matchings. This talk is based on the paper of Ilinca-Kahn with the same title.




Date:	March 22nd, 2017
Speaker:	Keith Frankston
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Fomin Growth Diagrams or How I Learned to Stop Worrying and Love Young Tableaux
Abstract:	This talk will be an introduction to the combinatorial tool I call Fomin Growth Diagrams. These diagrams are natural number arrays augmented with partitions. The specific partitions that appear are governed by a ruleset which grows them from an initial arrangement to an assignment over the entire array. In particular, we will describe the ruleset controlling the growth and show it produces a bijective relationship between initial conditions and last stage of growth. Once we have proven that the underlying ruleset produces a bijection, by restricting the initial conditions of the underlying array, we will derive a number of non-trivial combinatorial bijections with almost no work (in particular, RSK and the Schur identity). In fact, for RSK, we will get as a corollary a result that would otherwise require significant work in and of itself. While I won't go into further applications, I hope to convince everyone that this is a powerful tool when dealing with Young Tableaux (and it even can be used in some seemingly unrelated applications). In addition, this is far from the only ruleset you can choose to produce such structures. I will start the talk with a brief introduction to partitions, tableaux and Schur functions (though it certainly won't hurt if you've seen any or all of these concepts before).




Date:	March 8th, 2017
Speaker:	Nathan Fox
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Combinatorial Interpretations of Hofstadter-Like Sequences
Abstract:	Keith doesn't like my research, because he thinks it's too esoteric. The goal of this talk is to convince him that he's only mostly (and not entirely) correct. The primary objects of my research are Hofstadter-like sequences, that is, sequences arising from nested recurrence relations. Contrary to Keith's perception, such sequences often have non-obvious combinatorial interpretations. Keith (and everyone else) will learn how these sequences sometimes enumerate the leaves in certain infinite labeled tree structures.




Date:	March 1st, 2017
Speaker:	Ross Berkowitz
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	An Uncertainty Principle and an Application
Abstract:	I know where I will be on Wednesday at 12:10 PM, but I don't know what I'll be talking about. We will be able to apply this "uncertainty" to provide a clever proof of the Cauchy-Davenport Theorem.




Date:	February 22nd, 2017
Speaker:	Katie McKeon
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Furstenberg's Multiple Recurrence Theorem
Abstract:	We'll see how Furstenberg applied ergodic techniques to problems in combinatorics.




Date:	February 15th, 2017
Speaker:	Abigail Raz
Time:	12:10
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	The Union-Closed Sets Conjecture
Abstract:	The union-closed sets conjecture states that for any union closed family of sets with only finitely many member sets (and not only the empty set) there is an element appearing in at least half the sets. In this talk we will discuss a few weaker results that hold for union closed families motivated by the conjecture. Additionally, time permitting we will discuss a few reformulations of the conjecture in the language of lattices and graphs. We will state, and maybe even prove, that the conjecture is true for certain families.




Date:	February 8th, 2017
Speaker:	Bryan Ek
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	t-Core Partitions
Abstract:	The hook lengths of a partition are defined using the Ferrer's diagram of a partition. Fix a positive integer t. If a partition has no hook lengths that are multiples of t, then we say the partition is a t-core partition. Let ct(n) denote the number of t-core partitions of n. I will give an introduction to the generating series of ct(n) and how we can use it to prove ct(n)>0 for certain cases of t. Dependent on time, I will discuss the existence of special t-core partitions with extra restrictions. This will mainly be a combinatorics talk that utilizes results in number theory.




Date:	January 25th, 2017
Speaker:	Mrinal Kumar
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Simple proofs of some determinant complexity lower bounds
Abstract:	The determinant complexity of a polynomial P \in F[X1, X2, ..., Xn] is the smallest k such that the there is a k*k matrix N, whose entries are linear forms in the X variables, such that P = Determinant(N). The problem of constructing explicit low degree polynomials P such that the determinant complexity of P is at least super-polynomial in n is an important problem in computer science and is closely related to an algebraic analog of the P vs NP question. We will see some very simple proofs of determinant complexity lower bounds for the power sum symmetric polynomials. The bounds obtained are essentially the best lower bound currently known for any explicit polynomial.

Fall 2016 Abstracts

Date:	December 7, 2016
Speaker:	Aditya Potukuchi
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Hereditary Quasirandomness Without Regularity
Abstract:	I will discuss topics related to the recent paper:Hereditary Quasirandomness Without Regularity. I will start off with (more or less) basic notions and try to approach (one of) the main result of that paper.




Date:	November 30, 2016
Speaker:	Corrine Yap
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Do Matroids Dream of Unipancyclic Sheep? (An Intro to Matroid Theory via a Graph Theoretic Problem)
Abstract:	Matroids are a useful tool for generalizing ideas of dependence and independence, particularly within linear algebra and graph theory. This talk will explore a few of the many equivalent definitions for matroids by looking at the notion of "unipancyclic" (UPC) graphs (which arose from work on Hamiltonian graphs) and extending it to the matroid world. We will examine some non-graphic ways in which matroids can be represented, such as matrix and transversal representations, and use these to prove the connectivity of general UPC matroids.




Date:	November 16, 2016
Speaker:	Jinyoung Park
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Sum of Evenly Spaced Binomial Coefficients
Abstract:	It is well known that the sum of n choose k is 2^n, and the sum of n choose 2k is 2^(n-1). One can prove it in combinatorial way, as well as with the famous binomial theorem. In this talk, I will introduce a generalization of this identity, namely the sum of n choose rk for any fixed r, as well as its nice combinatorial proof.




Date:	November 9, 2016
Speaker:	Ross Berkowitz
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Basic Linear Duality for Linear Programming I: An Introduction for Beginners.
Abstract:	The linear duality theorem for linear programming is a basic and useful tool in discrete mathematics. I will talk about the basics of what linear duality does, and discuss some applications to discrete mathematics.




Date:	November 2, 2016
Speaker:	Andrew Lohr
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Reductions for polynomial lower bounds
Abstract:	3SUM is a problem that is conjectured to need at least roughly quadradic time to solve. This can be used to get conjectured polynomial lower bounds on a large number of other problems. We'll be looking at a few of them.




Date:	October 26, 2016
Speaker:	Justin Semonsen
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Color by Algebraic Number
Abstract:	Coloring a graph and finding its chromatic number is a very interesting area of combinatorics, but is very difficult to do efficiently. In this talk, we will use algebra to examine how we can color graphs more efficiently, as well as the limitations on coloring. Based on a 2008 paper by De Loera et. al.




Date:	October 19, 2016
Speaker:	Jason Saied
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Outer Automorphisms of S_6
Abstract:	S_6 is the only symmetric group which has outer automorphisms. (Yep, you read that right. What's so special about six?) We'll spend some time looking at the structure of the automorphism group of S_6 and the pretty properties it has. Among other things, we'll construct the outer automorphisms by playing with icosahedra, use those icosahedra to find some pretty weird (and important!) subgroups of S_6, and cook up a surprisingly simple construction of the Sylvester graph. This is based on work I did at Lafayette College with Dantong Zhu.




Date:	October 12, 2016
Speaker:	John Chiarelli
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	You Really Need to Be a Little Less Sensitive: Sensitivity Measures on the Boolean Cube
Abstract:	The study of Boolean functions is integral to both discrete math and computer science; one particular recurring question in dealing with them is quantifying how much of an impact changing some of the inputs of a given function can have on the output. In this talk, I will go over several major ways in which we perform such a quantification - sensitivity, block sensitivity, certificate complexity, decision tree depth, and tree sensitivity. I will also outline the relationships between these measures, both proven and conjectured.




Date:	October 5, 2016
Speaker:	Daniel Scheinerman
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Randomized Algorithms
Abstract:	Sometimes in life rolling the die helps. We will look at a number of examples of algorithms which efficienttly solve problems for which no deterministic solution is known. Time permitting we will examine on a few "derandomization" techniques. This will be a good talk. Probably.




Date:	September 28, 2016
Speaker:	Cole Franks
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	A theorem used in communication complexity and a conjectured generalization.
Abstract:	Unbounded error probabilistic communication complexity of a bivariate function is the number of bits two players, one having the first input and the other the second, would need to share for one of them to have a strictly better than 1/2 chance at guessing the value of the function. This problem has some nice equivalent formulations, and some good lower and upper bounds. A theorem involved in the lower bound, now called Forster's theorem, has popped up in some other places and has several nice proofs. We'll talk about the model, the theorem, and a possible generalization of said theorem.




Date:	September 21, 2016
Speaker:	Pat Devlin
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Matrix permanent and its norm
Abstract:	The permanent of a matrix is super important. It's a lot like the determinant except that the permanent is notoriously difficult to work with. So it's nice when you can say anything at all about the permanent. In this talk, we (essentially) characterize the matrices whose permanents are large, and we show the outline of the proof. The main idea is to exploit a known formula relating the permanent to the expectation of a certain random variable, and then we just beat the thing to death via the magic of probability. This is joint work with Ross Berkowitz, and time permitting I may get around to mentioning this fact.

Spring 2016 Abstracts

Date:	April 27, 2016
Speaker:	Tim Naumovitz
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Title:	Chernoff Bounds
Abstract:	In this talk, I'll present a few different versions of the Chernoff Bound, going through derivations for a couple of them, and spend some time looking at applications.




Date:	April 20, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	An introduction to WZ theory
Abstract:	In many cases, the evaluation of hypergeometric series is a shaloshable problem. We will discuss methods for doing this developed by Herb Wilf, Doron Zeilberger, and a nun.




Date:	April 13, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jinyoung Park
Title:	Can you play a fair game of craps with a loaded pair of dice?
Abstract:	Craps is played by rolling two standard cubical dice with sides numbered 1 to 6. The dice are called fair if each number is equally likely to be rolled and unfair or loaded otherwise. The play of the game is determined by the total distribution of the dice, and we are going to explore some interesting questions such as whether it would be possible to play this game with a loaded pair of dice, with the same probabilities of game events as if fair dice were being used.




Date:	April 6, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Andrew Lohr
Title:	Percolation on graphs
Abstract:	Suppose you have a d-dimensional infinite lattice (V=Z^d and edges between any two points distance 1 apart), and remove edges from it independently with some fixed probability. Then, we will be interested in the connected components you are probably left with. We say that the graph percolates if you have an infinite connected component left over. We'll go over some of the easier results, and maybe mention some open related problems.




Date:	March 30, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Abdul Basit
Title:	Geometric ideas in Sum-Product theory
Abstract:	The sum-product conjecture of Erdos-Szemeredi states that for any finite set A of the reals max(|A+A|, |AA|) \geq |A|^{2 - \epsilon}. Here A+A (resp. AA) is the set of all pairwise sums (resp. products) of elements of A. We will go over various sum-product type estimates and see how ideas from geometry come into play when proving such estimates.




Date:	March 23, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Cole Franks
Title:	Approximately Counting Graph Colorings
Abstract:	It is easy to see that a graph of degree d>0 has a proper 2d-coloring, but is it easy to count the number of such colorings? It turns out that in order to approximately count said colorings, it is enough to sample them (almost) uniformly at random. We`ll see why this is the case and go on to find an efficient way to sample these colorings using rapidly mixing Markov chains.




Date:	March 9, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Abigail Raz
Title:	Distinguishing Numbers of Graphs
Abstract:	Imagine you have a ring of key cards that open various doors. The only problem is that each of your key cards looks exactly the same. You decide to put stickers on them to distinguish the keys, but want to know the minimum number of different stickers you need to do so. This is exactly the problem of the distinguishing number of a graph. Formally we ask what is the minimum number of colors we need so that we can color the vertices of our graph such that no automorphism preserves the coloring. We will discuss this for various graphs and generalize to groups, H, where the distinguishing set of H is the set of distinguishing numbers of graphs G where Aut(G)= H.




Date:	March 2, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matt Charnley
Title:	Graphons and Finite Forcibility
Abstract:	Given a binary sequence, an especially curious person might wonder how many distinct subsequences it contains. We will first develop a simple algorithm to find the number of distinct subsequences in any fixed sequence, and then find the expected number of subsequences in a randomly generated sequence.




Date:	February 24, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Yonah Biers-Ariel
Title:	Counting Subsequences of a Binary Sequence
Abstract:	There is a somewhat clear way to define a distance between two graphs with the same number of vertices. After a slight generalization, we get a distance function that even works for graphs on differing numbers of vertices. We can also consider a sequence G_n of graphs, talk about convergence of a sequence of graphs (generally with the number of vertices going to infinity), and discuss what we mean by a limit. In this talk, I will motivate and define these limit objects, graphons, and talk about in what sense we can say the sequence converges. If time permits, I will also discuss the property of Finite Forcibility, and state a few results in this area.




Date:	February 17, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	Some Analytic Results For Generating Functions
Abstract:	At the start of his book, Herb Wilf said "A generating function is a clothesline on which we hang up a sequence of numbers for display". However, he also knew that the generating function was more than a merely a formal object. I will talk about some ways in which the analytic properties of generating functions relate to their associated sequences.




Date:	February 10, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Fun With PSPACE
Abstract:	You're walking down the hallway of Hill Center. You pass a group of cool computer scientists. They are having a conversation about something called PSPACE. You think to yourself, "I wish I knew what PSPACE was so I could be as cool as them." Good news! In this talk we will define PSPACE and introduce a well-known PSPACE-complete problem. Then, we will use these concepts to prove that a much more fun problem is PSPACE-card, er, I mean PSPACE-hard. (Disclaimer: This talk will teach you about PSPACE, but it will not teach you how to use correct grammar in your thoughts.)




Date:	February 3, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Sam Braunfeld
Title:	Homogeneity, Amalgamation, and Classifying Homogeneous Structures of n Linear Orders
Abstract:	This talk will introduce homogeneous structures, which have an extremely transitive automorphism group, and Fraisse's theory connecting them to amalgamation classes, which are classes of finite structures satisfying a simple combinatorial property. Remaining time will be spent discussing recent results in the direction of classifying the homogeneous structures of n linear orders.




Date:	January 27, 2016
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Katie McKeon
Title:	The Circle Method
Abstract:	A generating function for the number of partitions of an integer is fairly easy to obtain, but a bit unruly to work with. We will use a tool from analytic number theory to develop an asymptotic formula for the partition function via its generating function.

Fall 2015 Abstracts

Date:	December 9, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Bryan Ek
Title:	Pizza Seminar
Abstract:	Everyone wants to get the most (or not the least) when it comes to dividing up food. I will discuss and prove many food related theorems including the pizza theorem, lazy caterers theorem, ham sandwich theorem, and anything else that makes me hungry.




Date:	December 2, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Semonsen
Title:	Planar Approximation Schema
Abstract:	This talk will give an overview the special properties of planar graphs and how these can be exploited to get a linear time epsilon approximation for independent set. We will also develop the key ideas for the development of linear-time approximation schema for other NP-hard problems in planar graphs.




Date:	November 18, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Keith Frankston
Title:	Totally a Combinatorics Talk
Abstract:	This is definitely not a talk on ultrafilters and the Stone-Cech compactification of the natural numbers and their use in proving Hindman's theorem. Hindman's theorem (also known as the finite sums theorem) is a result from infinite Ramsey theory which states that any finite coloring of the natural numbers contains an infinite subset B of one of the colors such that the sum of any finite selection of elements of B is in the same color class. We will prove this result through the introduction of a bizarre binary operation on ultrafilters with the property that the existence of any idempotent element will allow us to construct such a B given any choice of coloring.




Date:	November 11, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Charles Wolf
Title:	Proofs and Generalizations of the Sylvester-Gallai Theorem
Abstract:	The Sylvester-Gallai Theorem states that any finite point set in real space either must be collinear or must have some line passing through exactly 2 points. We will go through a few proofs of this, and see which proofs generalize to other statements about lines through point sets.




Date:	November 4, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz




Date:	October 28, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin
Title:	Evasive boolean functions (and evasive graphs)
Abstract:	It is a well-known fact that in an early draft of Tolkien's "Riddles in the Dark" chapter of the Hobbit, Gollum challenges Bilbo to the following game. Gollum draws a graph on the ground, and he declares "we thinks of a set of vertices. Does it haves any edgeses?". Bilbo is allowed to ask about vertices one by one via questions of the form "is THIS vertex in your set?", and Gollum answers tricksily (adversarially). Bilbo wins if he manages to answer Gollum's riddle without having to ask about literally every single vertex of the graph. In the subsequent dialog, Tolkien explores for which graphs Gollum has a winning strategy and calls such graphs "evasive" (otherwise, non-evasive). Following Tolkien's original manuscripts, in this talk we discuss the question of which graphs are evasive, how to test evasiveness, and a striking conjecture that is either extremely interesting or extremely false. We settle the question completely for trees, cycles, and a few other graph families. Time permitting, we will show connections between this question and the larger framework of more general boolean functions [about which multiple very interesting results have been proven (mostly via neat topological ideas)]. **Note: The speaker is willing to offer anyone one (1) ring of power for a positive proof of the main conjecture or four (4) cakes of lembas bread for a counterexample.




Date:	October 21, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Nice Solutions to Meta-Fibonacci Recurrences
Abstract:	In 1963, Douglas Hofstadter first contemplated the recurrence Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)). He found that, when given the initial conditions Q(1)=1 and Q(2)=1, this sequence behaves chaotically. In fact, we still do not know whether Q(n) < n for all n. About thirty years later, Solomon Golomb observed that the initial conditions Q(1)=3, Q(2)=2, Q(3)=1 give rise to a much more predictable sequence. Even more recently, Frank Ruskey discovered a way to embed the Fibonacci sequence into the Hofstadter's recurrence. In this talk, we will expand upon the ideas of Golomb and Ruskey as we explore what sorts of nice solutions exist to the Hofstadter and related recurrences, known as meta-Fibonacci recurrences. This talk will be similar to my October 1 talk at the Experimental Math Seminar, but there will be differences. In particular, that talk was more concerned with giving an overview. Here, we will examine particular results and give more examples.




Date:	October 14, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	John Chiarelli
Title:	A Broader Color Scheme: A Symmetric Polynomial Extension of the Chromatic Polynomial
Abstract:	Based on a 1995 paper by Prof. Richard Stanley at MIT, this talk will define a graph property based upon the idea of the chromatic polynomial, expanded to the field of multiple-input symmetric polynomials, and look into some of the properties of this polynomial. In particular, I will use this polynomial to look into characteristics of a graph based on its sink sequence.




Date:	October 7, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Katie McKeon
Title:	Zeta Functions of Graphs
Abstract:	We'll look at the graph theoretic analogue of the Riemann zeta function. These functions are linked to the eigenvalues of a graph. In particular, we will show that expander graphs with a certain eigenvalue constraint satisfy the Riemann hypothesis.




Date:	September 30, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Overpartitions
Abstract:	Overpartitions are like partitions, but different. I will talk about them.




Date:	September 23, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Cole Franks
Title:	Guillotine Cutting Sequences
Abstract:	Have you ever been stranded in a post-apocalyptic wasteland in which your only chance of survival was to cut pre-drawn shapes out of a piece of paper with only a Swingline\AE Guillotine Paper Trimmer? I am sure you have been and will be again, but have no fear! I will show you how to save at least a 4/729 fraction of those objects, provided they are axis parallel squares.




Date:	September 16, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	An efficient algorithm for computing ulam distance.
Abstract:	The question of computing ulam distance arises out of a hope of attacking the difficult related problem of computing (or approximating) edit distance. In this talk, I'll introduce the notion of ulam distance and show how the task of computing ulam distance can be reduced to a discrete nearest neighbor problem. Subsequently, I'll show how one can use techniques motivated by binary search to solve this problem. If there's time, I might lift up the proverbial rug at the end of the talk and look at the things I swept under it.

Spring 2015 Abstracts

Date:	April 29, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Sam Braunfeld
Title:	Trees
Abstract:	I intend to prove a theorem (Spoiler: It will be tree).




Date:	April 22, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Bryan Ek
Title:	Intricacies of Pursuit-Evasion Games
Abstract:	"Tag" is a common schoolyard game in which someone, "it", tries to capture someone else, a runner. By constraining the playing field to a graph, with edges being the valid movements, we can determine whether the "it" person captures a runner, or if the runners evade indefinitely. I will discuss some variants of this game and the relation to properties of graphs.




Date:	April 15, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Garnett
Title:	Multi-armed Bandit Problems
Abstract:	The basic setup of the multi-armed bandit problem is that there are several slot machines with unknown reward distributions, and you have time/resources for some (maybe unknown) number of plays. If your goal is to maximize your winnings, you'll have to balance the desire to stick with a seemingly good machine with the competing desire to acquire more information about other machines. I'll discuss some strategies depending on the goal and variation of the problem.




Date:	April 8, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Andrew Lohr
Title:	The Thue-Morse Sequence
Abstract:	In this talk, we'll examine fixed points of morphisms of words, a way of constructing interesting infinite words. In particular, we will mostly focus on the Thue-Morse word, which has appearances in many different locations. We'll see some of them. We will also talk about generalizations of this word to a larger alphabet size.




Date:	April 1, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	Counting Counting Crows
Abstract:	Have you ever been listening to music by your favorite bands (2 Franks and a Shank, Democratic Republic of the Bongos, $\frac{(S)m^ar+ly}{Pr\Sigma(\pi)y}$, etc) and wondered how they got their names? In this talk, we'll explore ways in which we can use combinatorial techniques to come up with a closed form for the number of ways in which you can name your band. If there's time, we'll travel to the town in which Schubert was built and, using my advisor's phone, attempt to solve Fox's conjecture (or at least figure out what it says).




Date:	March 25, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Keith Frankston
Title:	From French Desserts to British Majors
Abstract:	In this talk we will explore the connection between tilings of hexagons and plane partitions. We will also prove MacMahon's well known result about the number of plane partitions of bounded row, column and part size.




Date:	March 11, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	The German Tank Problem
Abstract:	In World War 2, the Allies were interested in knowing how many tanks the Germans were building. This quantity was approximated using a statistical method which proved very accurate, and so the problem of estimating a population via sampling without replacement has become known as the German Tank Problem. We will analyze this problem and time permitting a few other related population estimate problems.




Date:	March 4, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin
Title:	(Hyper-)Graph Expansion and (Linear) Algebra: Techniques, Examples, and Applications
Abstract:	In this talk, we'll discuss some notions of expansion in graphs and hypergraphs. For the graph case, we will explore the connection between this and the eigenvalues of the graph taking a scenic route that motivates the use of the relevant (linear) algebraic ideas. We will also discuss a notion of expansion in hypergraphs and show some applications to fractional matchings. As always, the talk will be interactive, and the particular topics pursued will be dictated by audience interest.




Date:	February 25, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Katie McKeon
Title:	The Complexity of Algebraic Numbers
Abstract:	The subword complexity of a sequence counts the distinct strings of a given length that are contained within the sequence. We will examine a large class of transcendental numbers through the lens of this complexity function. In particular, we will use the Schmidt Subspace Theorem to prove that the subword complexity of an algebraic number (written as a sequence in some finite integer base) cannot increase too slowly.




Date:	February 18, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	John Chiarelli
Title:	Colorblind: Alfred Kempe and the Four-Color Theorem
Abstract:	When Kenneth Appel and Wolfgang Haken revealed their proof of the Four-Color Theorem in 1976, they were met with a lot of skepticism, and not just because of their use of computers. The Four-Color Theorem - which states that any planar graph can be colored with four colors such that no two adjacent vertices are the same color - has a long history of failed attempts at a solution. In this talk, I will look into the details of one particular failed attempt at proving the theorem, posited by Alfred Kempe in 1879. While it ultimately turned out to be incorrect, the methods used have notable applications. Accompanying this "proof" will be Percy James Heawood's modifications to Kempe's work to prove a weaker proof, the Five-Color Theorem.




Date:	February 11, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Abigail Raz
Title:	Fun with Signed Graphs
Abstract:	In this talk we look at signed graphs–graphs whose edges have weights of plus or minus one–and how to construct their exterior powers. We will discuss basic properties of these signed graphs- when are they balanced, anti-balanced, or unbalanced? Specifically, we will look at a complete characterization for when the exterior power of a graph is balanced.




Date:	February 4, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Solving functional equations by guessing
Abstract:	As combinatorialists, we like generating functions. Sometimes, we have a functional equation for a generating function, but not yet an explicit form. We'd like an explicit form - how do we find one? (See title.)




Date:	January 28, 2015
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jake Baron
Title:	Is Numerical 3D Matching Still NP-Hard When X=Y=Z?
Abstract:	We introduce a problem in combinatorial optimization that arose from a project on how to best allocate boats to rescue stations for the US Coast Guard. We show that the new problem is a substantially restricted version of a problem known to be NP-hard, and we therefore ponder about its own complexity status.

Fall 2014 Abstracts

Date:	December 10, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	Parallel Computing and Quadratic Rado Numbers
Abstract:	In 1916, Issai Schur invented Ramsey theory. In 1926, Frank Ramsey also invented Ramsey theory. We will explain this time-travel-related paradox and give some basic history of Ramsey theory, and then discuss the computational challenges for computing Ramsey quantities of various types. We will then discuss some of the basic ways in which modern computing methods can be used to tackle a few different types of Ramsey theoretic computations, including some recent computation of Rado numbers for quadratic Diophantine equations.




Date:	December 3, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Gilmer
Title:	A new approach to the sensitivity conjecture
Abstract:	We'll discuss a new two-player communication game for which a strong enough lower bound on the cost of this game would imply the famous sensitivity conjecture. We'll then prove such a lower bound for a restricted variant of the game. Some new open questions as a result of this work will be discussed, some of which may turn out to be "low hanging fruit". No prior knowledge will be assumed for this talk. Joint work with Michael Saks and Michal Koucky.




Date:	November 19, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Daniel Scheinerman
Title:	Van der Waerden's Theorem and Similar Results
Abstract:	We will discuss Van der Waerden's theorem and other theorems in which we color the integers (or Z^n) and look for arithmetic progressions (or other patterns).




Date:	November 12, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Charles Wolf
Title:	Bounds for the CHSH game
Abstract:	Abigail and Brian are each given a random element x and y, respectively, from a finite field. Without speaking to each other, they respectively output elements a and b in the field in an attempt to make a+b=xy. What is the probability they get the desired equality? This is an adaptation of the Clauser, Horne, Shimnoy and Holt (CHSH) game, which is well studied in quantum information theory.




Date:	November 5, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin
Title:	It's too Late: Topologize!
Abstract:	It is sometimes remarked that combinatorics is not the study of structures or theorems, but instead it is the study of techniques. Several techniques are well known and evidently quite fruitful (e.g., the probabilistic method, linear algebra, Fourier analysis, entropy, et cetera). But [believe it or not] another tool that should be in every discrete mathematician's backpocket is algebraic topology. We will discuss the really clever historical applications of this technique to combinatorics, provide a quick primer on the relevant topological kajiggers, and equip ourselves with ways to recognize when this technique might be useful in our own combinatorial lives. I pinky promise that this talk will be 100% accessible and very clear (cross my heart and hope to die).




Date:	October 29, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Cole Franks
Title:	Hypergraph Discrepancy
Abstract:	Imagine coloring a hypergraph with two colors so that each edge is as fairly split as possible between the two colors. This is the well-studied field of hypergraph discrepancy. We will go through the proof of the famous "Six Standard Deviations Suffice" theorem of Spencer and if time permits we will look at an open problem in discrepancy theory.




Date:	October 22, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Drafting
Abstract:	Whether it be aerobie players, bagels, Agricola cards, or something else, most of use have drafted something at some point in our lives. But how carefully did you consider your strategy from pick to pick? Today, we will analyze a bunch of drafting scenarios which may help improve your drafting strategies going forward.




Date:	October 15, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Partition Identities
Abstract:	I will talk about partition identities.




Date:	October 8, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	The Graph Reconstruction Conjecture
Abstract:	The Reconstruction Conjecture, a famous open problem in graph theory, asks whether all graphs are uniquely determined by their list of subgraphs of order n-1. In this talk, I will answer this question, and talk about modified versions of this conjecture. I will also give an overview of certain properties of graphs which are known to be reconstructible, as well as certain classes of graphs which can be reconstructed from their subgraphs.




Date:	October 1, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	DeBruijn Sequences
Abstract:	Let's say somebody asks you to construct a sequence of ones and zeros with the following property: You will be given a window through which you look at 10 consecutive bits of your sequence, and you must be able to identify where in the sequence these 10 bits lay. How long can you make such a sequence? We will answer this question along with further considerations including: how quickly can you locate the 10 bit subsequence in the original string, how would you proceed if instead of an n-bit string you are to construct an nxn matrix, and if time permits how much can you do when your window is dirty, and some of the data is misreported.




Date:	September 24, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Michael Donders
Title:	Seymour's Second Neighborhood Conjecture
Abstract:	First proposed by Paul Seymour in 1990, Seymour's Second Neighborhood conjecture is a relatively simple sounding statement that has proved surprisingly difficult to verify. The conjecture states that for every simple directed graph, there exists a vertex whose second neighborhood is at least as large as its first neighborhood. This talk will go over the trickiness that is involved with directed graph neighborhoods, as well as the progress and partial results that have accumulated over this conjecture. Further we will discuss the relevance of the Second Neighborhood Conjecture to other important conjectures in directed graph theory, including the Caccetta-H\E4ggkvist Conjecture and the Behzad-Chartrand-Wall Conjecture.




Date:	September 17, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathaniel Shar
Title:	Lambda Calculus
Abstract:	The lambda calculus is the main competitor to the Turing machine model of computation. In addition to being of mathematical interest, it is also the inspiration for the so-called functional programming languages, like Lisp and Haskell. In this talk, I'll try to convince you that the lambda calculus is more elegant (or at least more interesting) than Turing machines. No prior knowledge of computer science is required.

Spring 2014 Abstracts

Date:	May 7, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Charles Wolf
Title:	A Survey of q-Analog Versions of Introductory Combinatorics Theorems
Abstract:	I will present several q-analog versions of combinatorics (or Qombinatoriqs) theorems covered in the introductory graduate courses. We will note which of these analogs look identical to the normal version, which look slightly different, and which are still open.




Date:	April 30, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jake Baron
Title:	Dense Graphs with a Large Triangle Cover Need Not Have a Large Triangle Packing
Abstract:	It is well known that a graph G can be made triangle-free via the removal of at most half its edges. If in order to make G trianlge-free one must actually remove nearly half its edges, this can be viewed as evidence that G has a lot of triangles. Another piece of evidence to the same conclusion would be that G has an edge-disjoint triangle packing covering nearly all its edges. In 2010, Raphael Yuster conjectured (omitting some details) that the first property implies the second. I will explain my recent proof, with Jeff Kahn, that he was wrong.




Date:	April 23, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	John Kim
Title:	Circuit Complexity
Abstract:	Say you want to raise a number in F_{2^n} to a large power (for example, to find the inverse of x, take x^(2^n-2)). Is this easy or hard to compute? We will consider the setting of AC0(parity) circuits, and ask which powers are computable by constant-depth, polynomial-size circuits. We give a general, sufficient condition for when a power is hard to compute in AC0(parity).




Date:	April 16, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Andrew Lohr
Title:	Well Quasi-Orders
Abstract:	When a set is closed downward under a well quasi order, it is very simple to test membership of elements in this set. So, it is helpful to know that certain sets have this property. In particular, subset languages of words and graphs and trees under minors do.




Date:	April 9, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Katie McKeon
Title:	Voltage Graphs and the Heawood Problem
Abstract:	Heawood conjectured a formula for the maximum number of colors needed to color a map on a surface of a given genus. Voltage graphs were introduced as a concise way to express a large graph and its quotient graph via a function from the edges of the quotient to some group. We will see how voltage graphs can be used to embed a complete graph of large order on a surface and how this helps answer the Heawood map coloring problem.




Date:	April 2, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Simão Herdade
Title:	The Weak Bezout Theorem
Abstract:	For most applications of Bezout's theorem, it is enough to know that the number of distinct points of intersection of two algebraic curves (with no common factor) in the Euclidean plane, is at most the product of their degrees. In this talk we will look at a hands-on proof of this bound, requiring no knowledge of Algebraic Geometry.




Date:	March 26, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	Communication is the Key to Any Relationship
Abstract:	Just kidding, in this talk the goal will be to communicate as little as possible. We will see a brief introduction to communication complexity, and look at several classic communication problems.




Date:	March 12, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Garnett
Title:	How to Gamble in Certain Situations
Abstract:	"It is almost always gambling that enables one to form a fairly clear idea of a manifestation of chance...it is, therefore, gambling that one must strive to understand, but one should understand it in a philosophic sense, free from all vulgar ideas." --Louis Bachelier




Date:	March 5, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	Linear Codes and Lattices
Abstract:	Linear codes and real lattices are two distinct objects that seem anecdotally similar, and indeed share a fruitful connection. We will discuss some analogous behavior between the two objects, and in particular look at a connection between circulant codes and a recent improvement on lattice sphere packings in high dimensions. If time permits we will also discuss some recent attempts of my own to leach ideas from the lattice world.




Date:	February 26, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Systematically Proving Ptolemy-like Theorems
Abstract:	Ptolemy's theorem is a classical result that gives a formula relating the side lengths and diagonals of cyclic quadrilaterals. More generally, there are theorems that do the same for cyclic polygons. We will look at various methods for proving these, including by means of the Lagrange Interpolation Formula. This talk will serve as a warm-up to my talk in the experimental mathematics seminar the following week.




Date:	February 19, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Michael Donders
Title:	Optimal Graphs for Chromatic Polynomials
Abstract:	The chromatic polynomial of a graph G is the number of ways in which G can be colored with lambda colors. We then define a graph to have optimal chromatic polynomial if it has the greatest chromatic polynomial among all graph with the same number of vertices and edges. This talk will go over some basic properties and results regarding chromatic polynomials, as well as some methods for calculating chromatic polynomials, and then discuss the problem of finding graphs which have optimal chromatic polynomials, including some results as well as open conjectures on the topic.




Date:	February 5, 2014
Time:	2:00 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin
Title:	Entropy: How to and Why
Abstract:	The talk will be about some math thing at least loosely connected to combinatorics. There will be food and people you like, so it will therefore be a success. (I believe the talk will a discussion about [information theoretic] entropy [what is it, how to think about it, and what to do with it].) It'll be great.




Date:	January 29, 2014
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Zeckendorf Representations
Abstract:	Most people learn the base ten number system early in their lives. Many people are even familiar with other number bases, such as binary. In all such systems, we force the place values to be powers of some number. But, why have such a restriction? What if we make the place values Fibonacci numbers instead? This leads to what is known as the Zeckendorf Representation. In this talk, we will examine some combinatorial properties of the Zeckendorf Representation, and, if time permits, we will see a further generalization.

Fall 2013 Abstracts

Date:	December 11, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Thomas Sznigir
Title:	Delaunay Triangulation
Abstract:	Given a (non-degenerate) collection of three or more points in the plane, it is possible to construct a triangulation. While existence is nice, arbitrary triangulations can have dreadful numerical properties. Fortunately, any given triangulation can be transformed into a Delaunay triangulation, which has much better properties. For example, it maximizes the minimal angle of any triangle in the triangulation. It is also the dual graph to the Voronoi diagram, which has many scientific applications.




Date:	December 4, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathaniel Shar
Title:	Richman Games
Abstract:	In most games, players alternate turns. But there are other methods to decide whose move it is. In this talk, I will discuss Richman games, in which the privilege of moving is auctioned off each turn. Although this may seem to add a lot of additional complexity, Richman games are sometimes easier to analyze than their standard counterparts; as an example of this, we will see the algorithm of Payne and Robeva for winning Bidding Hex.




Date:	November 20, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Gilmer
Title:	The Geometry of the Boolean Cube and the Hamming Ball
Abstract:	We will cover a recent paper which gave a construction of a bi-Lipschitz bijection between the Boolean cube and the Hamming ball of equal volume. In layman's terms, the Boolean cube is just all strings of length n of 0's and 1's and the Hamming ball is all strings of length n+1 which have more than n/2 1's (assume n is even). Bi-Lipshitz simply means that close points map to close points and same for the inverse map. The main technical tool will be a cool partitioning of the cube into symmetric chains. No prior knowledge will be necessary to understand this talk, and many new open problems will be given at the end.




Date:	November 13, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	The Calkin-Wilf Tree
Abstract:	The Calkin-Wilf tree is a tree that contains every rational number exactly once, and in which a/b is the parent of a/(a+b) and (a+b)/b. The root of the tree is 1. This tree does more than give an interesting enumeration of the rationals, so I will discuss some of its interesting properties, structures, and generalizations.




Date:	November 6, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Cole Franks
Title:	Graph Labeling with Distance Conditions
Abstract:	I will describe a problem arising from channel assignment, that is, the assignment of frequencies to transmitters in such away that closer transmitters receive more distant frequencies to avoid interference. An L(2,1)-labeling of a simple graph G is a labeling of the vertices of G with integers such that the labels of adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. The span of such a labeling is the difference between the highest and lowest labels used. I will discuss conjectured and proven bounds on the smallest possible span of an L(2,1)-labeling of a given graph in terms of its maximum degree. I will also present some graphs of low maximum degree that admit only labelings with large spans.




Date:	October 30, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Arran Hamm
Title:	Kneser Graphs and Kneser's Conjecture
Abstract:	The Kneser graphs form an infinite family of graphs which were first investigated in the 1950's. In this talk we will investigate this family of graphs and aim to identify a few graph parameters such as clique number and independence number. I will also state Kneser's Conjecture concerning the chromatic number of each member of this family of graphs. This was proven to be correct by Lovasz in the 1970's with topology making a surprising cameo. We will prove Kneser's Conjecture which just so happens to be my favorite proof of all time.




Date:	October 23, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Daniel Scheinerman
Title:	Random Threshold Graphs
Abstract:	A threshold graph is a simple graph, G, such that we can assign weights to the vertices of G such that there is an edge between two vertices exactly when the sum of their weights is at least one. We will give some characterizations of threshold graphs and use them to analyze several models of random theshold graphs. Unlike, Erdos-Renyi models for many of the questions we will ask we will obtain exact formulas.




Date:	October 16, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jake Baron
Title:	The Konig Tree Lemma
Abstract:	Every infinite connected graph with all degrees finite has an infinite path. This is the Konig Tree Lemma--a simple, obvious, and shockingly powerful result in infinitary combinatorics that also happens to be the speaker's favorite theorem. I'll state two versions, prove them, and discuss deep, dark connections to compactness and choice. After running out of time, I'll show an amazing application to the infinite Ramsey theorem.




Date:	October 9, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	Streaming Algorithms
Abstract:	Suppose you're being held captive by an Evil Intel Number Box (EINB). The EINB will shout a sequence of (at most) 8-bit integers at you very fast, and when it stops, it tells you to output the mode of the sequence. If you answer correctly, it will set you free, but if not, you will be subjected to an endless stream of Nathan's puns instead. You do not know how long the sequence will be, but you are promised that more than half of the numbers in the sequence will be the mode. If you want to learn how to do this, come to my talk.




Date:	October 2, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Subtraction Games
Abstract:	You may be familiar with the game of Nim, which has a straightforward winning strategy. Related to Nim is a class of games, known as subtraction games, for which the winning strategies are much more poorly understood. I will give a survey of the few results known about winning strategies in subtraction games. Then, I will discuss an automated procedure for determining these winning strategies. Finally, if time permits, I will generalize the notion of subtraction games and prove a result in that more general setting.




Date:	September 25, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	Sperner's Lemma
Abstract:	In 1928 Emanuel Sperner proved a nice combinatorial result concerning the coloring of points in the plane. This theorem has turned out to be very useful in finding fixed points and has many applications including a wonderful proof of a topological fact: Brouwer's fixed point theorem.




Date:	September 18, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Automated Proving of Collatz-like Theorems
Abstract:	What do you do when you try to prove the Collatz conjecture, but get stuck? Turn it into a second-order recurrence! What do you do when you'd like to prove something by induction, but can't quite figure out what the inductive hypothesis should be? Have the computer come up with it for you!

Spring 2013 Abstracts

Date:	May 1, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Nakamura
Title:	Problems Regarding Synchronizing Automata
Abstract:	A deterministic finite automaton is called synchronizing if there exists a "reset" word that sends every state to one particular state. In this talk, I will discuss some questions that have been posed regarding synchronizing automata (including an open problem known as the Cerny Conjecture). I will also discuss some game theoretic questions that have been recently asked for synchronizing automata. No prior background (in this area) will be assumed.




Date:	April 24, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin




Date:	April 17, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Simão Herdade
Title:	Random Walk with Fixed Step Length: Maximum Returning Probability
Abstract:	We shall study the maximum possible returning probability of a random walk with all steps of same length. For this purpose we'll visit the important notion of generalized arithmetic progressions, and in the end get into a nice combinatorial geometry open problem, which we could not solve. Joint work with Van Vu




Date:	April 10, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Gilmer




Date:	April 3, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	WZ Theory and Automatic Hypergeometric Summation




Date:	March 13, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	Conway's Angel and Devil
Abstract:	The game of the Angel and the Devil is defined as follows: The Angel, of specified power p, moves on a large or infinite chessboard, up to p squares in each direction at any time. The Devil's move is to eat any square. Can the Angel avoid using a square that is eaten? Does this depend on p? I will present some results concerning this game, including the answer to the above question. Taking p>=2 is sufficient, a fact recently proved by four people (each independently). At least two of these proofs will be presented.




Date:	March 6, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jake Baron
Title:	Infinite Combinatorics
Abstract:	Alas, try as I might, I won't be able to cover an infinite amount of combinatorics in my 50-minute talk. What I will do is give an absurdly brief introduction to a few nice combinatorial questions in set theory. We'll discuss some subset of tall trees, nonprincipal ultrafilters, many-petaled sunflowers, mad families, and impregnable towers.




Date:	February 27, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathaniel Shar
Title:	Quasirandom Graphs
Abstract:	There are many familiar examples of deterministic sequences of integers that behave as though they were random, such as the output of a pseudorandom number generator or, conjecturally, the digits of pi. We will discuss a similar phenomenon in which certain deterministic graphs behave, for many practical purposes, like random graphs. Such graphs are called quasirandom. We will focus on the random-like properties of quasirandom graphs and clever ways to recognize such graphs when you run across them.




Date:	February 20, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Nathan Fox
Title:	Subword and Abelian Complexity
Abstract:	I have a word, and I want to study how it behaves. I would like to just look at the entire word, but this is only possible if the word is finite. In general, I can examine the finite subwords of my word. There are two standard ways to do this. First, the subword complexity of a word, as a function of n, is the number of subwords of the word of length n. A newer concept, abelian complexity, is the same as subword complexity, except that if two subwords are anagrams of each other they are counted as the same word. I will present some general properties of these two functions on words, and then I will compute the asymptotic behavior of the abelian complexity function on a certain class of infinite binary words.




Date:	February 13, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Garnett
Title:	Martingales and Optimal Betting Strategies
Abstract:	Brian decided to study math because he wanted to be better at gambling. People said he was naive as he struggled in his first year with complex analysis and tried to apply Cauchy's Integral Formula to Texas Hold 'Em. Then he learned the probabilistic concept of a martingale, which is the natural formulation of a gambling system, and he was finally vindicated in the eyes of his critics. In this talk, we'll investigate the Passenger 57 Theory of Roulette which says that you should "always bet on black." If time permits, we'll take a look at other relevant scenarios, if there are any.




Date:	February 6, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Danny Scheinerman
Title:	More Sum Than Difference Sets
Abstract:	For S, a set of numbers in {1,2,3,...,n}, we call S a More Sum Than Difference (MSTD) set if |S+S|>|S-S|. We will answer such questions as: 1) Do such sets exist? (hint: yes, but it is a fun programming challenge to find one) 2) What is the probability that a random set drawn from {1,2,3,...,n} is MSTD? 3) How big can |S+S|-|S-S| be? We'll also discuss some open problems/conjectures.




Date:	January 30, 2013
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	P,NP,EXP,NEXP,co-NP,PH,L,NL,PSPACE,EXPSPACE,P/poly,BPP,RP,co-RP,ZPP,BP*NP,NC,AM,MA
Abstract:	This talk will basically be an overview of the aforementioned complexity classes, mostly focusing on what they are and how they relate to each other. It is intended for an audience with little to no familiarity with Complexity Theory. The commas in the title of this talk were added only as a concession to Matthew's ridiculous demands for title readability.

Fall 2012 Abstracts

Date:	December 5, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Patrick Devlin




Date:	November 28, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Gilmer
Title:	Boolean Functions
Abstract:	The study of boolean functions is motivated by questions in computer science, but turns out to give many nice combinatorial questions. We will begin by defining what a boolean function is, followed by block sensitivity (bs(f)) and certificate complexity (C(f)). We will then go over a well known fact that for any boolean function f, C(f) <= bs(f)^2, followed by a new construction of a family of functions which shows this upper bound is essentially tight. Time permitting we will mention some of the many open problems in this area that any combinatorialist would find interesting and accessible. No computer science knowledge necessary! Joint work with Michael Saks and Srikanth Srinivasan.




Date:	November 7, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Sidon Sets




Date:	October 24, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Nakamura
Title:	A Brief Survey on Permutation Patterns
Abstract:	Over the past few decades, the study of patterns in permutations has received significant attention. In this expository talk, we will survey a few of the general areas of research in this field. We will also discuss some of the interesting results and open problems in this area. No prior knowledge in permutation patterns will be assumed.




Date:	October 17, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Edinah Gnang
Title:	Revisiting Euclid's Proof of the Infinitude of Primes
Abstract:	We discuss a variation of Euclid's Proof so as to turns the proof into a combinatorial algorithm for sifting primes. We further modify our construction to sieve out totally odd numbers and describe our ongoing efforts to estimates their density among the integers. This is joint work with Patrick Devlin.




Date:	October 10, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Bobby DeMarco
Title:	Gluing Graphs
Abstract:	For a family of connected graphs, I will introduce the notion of unique composability, and perhaps discuss why this notion is of interest. I will then discuss which families of size 2 are uniquely composable, before describing conjectures and ideas about larger sized families. (Joint work with Amanda Redlich)




Date:	October 3, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ross Berkowitz
Title:	Rook Polynomials
Abstract:	How many ways can you put 8 nonattacking rooks can you place on the empty board? This is of course a trick question, as you can't put any rooks on a board with no squares, and so the answer is 0. However, rook placements can be used to solve to solve interesting problems too. In this talk I will give a re/introduction to enumeration using rook polynomials. A lot of problems in counting can be rephrased in terms of placements of rooks in specific locations on a chessboard. This often gives a nice visual aid, and comes with a whole host of prebuilt identities to exploit. In particular, time permitting, we will use rook polynomials to solve the probleme des menages and Simon Newcomb's problem.




Date:	September 26, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Tim Naumovitz
Title:	IP=PSPACE
Abstract:	Jake has two different colored socks and wants to convince Kellen, who is color blind, that they are different colors. In this talk, I'll explain what Jake can do to convince Kellen, and then go through the main ideas in the proof of IP=PSPACE, after giving a (hopefully short) explanation of what IP and PSPACE are.




Date:	September 19, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	Modeling and Constructing Crop Rotations
Abstract:	Crop rotation is an ancient practice that has been supplemented for many years by the insights of various sciences that describe and quantify aspects of agriculture and horticulture. Different crops have different impact on soil and other factors in crop growth, and crop rotation attempts to best balance the effects of various crops. I will (re)introduce the concept of mathematical modeling and describe one way of modeling crop rotations. I will then describe a few ways to apply some combinatorial structures to generate potentially well-balanced crop rotations. No agricultural background is necessary -- this talk will simplify and/or abstract the agricultural parameters of the problem in a way that should be compatible with a math-only background.

Spring 2012 Abstracts

Date:	April 25, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Oster (RutCOR)
Title:	Approximation Algorithm Techniques via Set Cover
Abstract:	For any optimization problem whose underlying decision problem is NP-Complete, no exact polynomial-time algorithm can exist, assuming P != NP. Naturally, an alternative approach is to attempt to design polynomial-time heuristics which yield provably "good" solution approximations. In this talk I will discuss some of the fundamental techniques in a line of research called Theory of Approximation Algorithms. Greedy and combinatorial methods, rounding, and primal-dual schema (if time permits) will all be demonstrated on the combinatorial problem Set Cover.




Date:	April 18, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Nakamura
Title:	On Synchronizing Automata
Abstract:	A deterministic finite automaton is called synchronizing if there exists a "reset" word that sends every state to one particular state. A number of questions have been asked about this class of automaton. In this talk, I will discuss some of those questions including an open problem known as the Cerny Conjecture. No prior background (in this area) will be assumed.




Date:	April 11, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Edinah Gnang
Title:	Sampling Permutation Matrices/Tensors
Abstract:	We describe an intriguing algebraic construction for sampling permutation matrices, if time permits I will discuss permutation 3-tensors which are generalizations of permutation matrices. As well as generalizations of the associated algebraic construction.




Date:	April 4, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Charles Wolf
Title:	Applying Graph Coloring to Partitions of Sum Free Sets
Abstract:	Sometimes when I go to a party, I see many people I know and many people that I don't. I wonder how many of them know already either know each other or don't. In this talk, I will discuss solutions of this problem using graph coloring called Ramsey's Theorem. I will also apply Ramsey's theorem to Schur numbers, which involves partitioning the first n natural numbers into sum free sets.




Date:	March 28, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Simão Herdade
Title:	Halving Edges of Point Sets in the Plane
Abstract:	Consider a set of n points in general position in the plane. Call the edge formed by any two of them a halving edge if both the closed halfplanes defined by the correspondent line contain n/2 points of the set. We'll talk about upper and lower bounds for the maximum number of halving edges among such sets.




Date:	March 21, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers, Bobby DeMarco, Brian Nakamura
Title:	Oral Qualifying Exam and Advisor Panel Discussion
Abstract:	We will discuss oral exams and advisors as a panel. (This is not a mathematical seminar this week.)




Date:	March 7, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Arran Hamm
Title:	Intersecting Families
Abstract:	A classic set system question is, how many k-subsets of [n] can you have such that every pair of sets is intersecting (i.e. an intersecting family)? This, of course, was answered by the Erdős-Ko-Rado Theorem stating that the maximum is n-1 choose k-1. One construction of a maximum sized intersecting family is to take all k-sets containing a particular element of [n]. Observe that for this type of family the intersection over all members of the family is nonempty. So naturally one can ask, how large of an intersecting family of k-subsets of [n] can you have such that the intersection over all members of the family is empty? This was answered by the Hilton-Milner Theorem whose statement and proof will be given. The remainder of the talk will be on a threshold-type question about random k-uniform hypergraphs with respect to the "EKR Property."




Date:	February 29, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Thompson
Title:	The Fountain of Life: Renewal Theory and Information Streams
Abstract:	Online social media such as Twitter capture thousands of instances of user-posted content every second. How can we harness these massive streams of data that are arriving almost as fast as we can process them? What can we learn about the way people interact, the way information spreads, and the roles of individual people, companies, or news sources? How can we leverage this to help us find relevant information and learn about the world around us? We'll take a look at an approach based on modeling the system as a set of renewal processes.




Date:	February 22, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Timothy Naumovitz
Title:	P=NP iff N=1
Abstract:	I'm sure most of us are roughly familiar with the ideas behind the P vs NP problem, but this talk will hopefully give us a better understanding of the process of proving NP completeness. After laying the formal framework for the problem, we will see several instances of proofs that certain problems are NP complete.




Date:	February 15, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Garnett
Title:	The Size of a Hypergraph and its Matching Number
Abstract:	Abstract: This is the title of a recent paper (which I will summarize) by Huang, Loh, and Sudakov. About 45 years ago, Erdős conjectured that the size of a k-uniform hypergraph with less than t (≤ n/k) disjoint edges has a certain upper bound and proved it for t ≤ O(n/k³). This paper improves the range to t ≤ O(n/k²). Next you guys can prove it for t ≤ n/k, and we'll be done with this!




Date:	February 8, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Humberto Montalvan
Title:	Super-Uniformity of Billiard Paths (and Planes)
Abstract:	Imagine a billiard ball traveling at unit speed in the unit square, bouncing off the walls elastically, for T seconds. Suppose that there is an irregularly shaped blob A on the surface of the table. The total length of the portions of the ball's trajectory that lie in A, divided by T, should give an approximation of the area of A. In this talk, I will present a recent result of Jozsef Beck which essentially states that the error in this approximation is surprisingly small for a typical billiard path, regardless of the 'ugliness' of A. I will also discuss the correct way of generalizing this result to higher dimensions.




Date:	February 1, 2012
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Fun with Exponential Generating Functions
Abstract:	Exponential generating functions provide a clever way to count sets, where order is not important - as opposed to ordinary generating functions, which usually count structured objects where order counts. We'll see some uses of their power - even a combinatorial proof of the Pythagorean Theorem.

Fall 2011 Abstracts

Date:	November 30, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Garnett
Title:	Hypergrpah Ramsey Numbers
Abstract:	Ramsey's Theorem for graphs can be extended to k-uniform hypergraphs: if we color the edges of a large enough complete k-uniform hypergraph, we can find a k-uniform subgraph of a given size with all edges the same color. We'll take a look at these Ramsey numbers, starting with k=3. As you might expect, Ramsey provides us with a terrible upper bound and Erdős provides a much better one.




Date:	November 16, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Justin Gilmer
Title:	The Theory of Graph Limits
Abstract:	This will be a general survey of a recent and exciting area of graph theory, graph limits. The general motivation of which stems from studying G(n,p) for p a fixed constant. A sequence of graphs G(n,p) with high probability "look the same" in terms of their subgraph counts (eg. number of edges, triangles, 4 cycles etc.). This suggests that these graphs should form a Cauchy sequence in some metric. We will define an appropriate metric (really a pseudometric), and then consider the completion of this metric which contain elements call "graphons". As this is a survey of a fairly technical theory, we will focus largely on examples, and many theorems will be stated without proof.




Date:	November 9, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Humberto Montalván
Title:	The Three-Distance Theorem in Music Theory
Abstract:	You might be familiar with the fact that in music there are 3 kinds of ordinary three-note chords (major, minor, and diminished) occurring naturally in the key of C major. Likewise there are 4 kinds of seventh chords, each of which has 4 notes. (Can you name them all?) These are but two examples of a classic result in mathematical music theory whose content is captured in the catchy phrase 'cardinality equals variety'. In this talk we will give a characterization of the 'well formed scales' that have the 'cardinality equals variety' property for chords. The music-theoretic concept of 'scale' corresponds to a simple mathematical construction. More precisely a 'scale with generator d' is a finite arithmetic progression on the unit circle with difference d. Vera Sós' classic three-distance theorem is intimately related to the music-theoretic results that we will derive.




Date:	November 2, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Jake Baron
Title:	Splitting Maximal Antichains
Abstract:	An antichain in a poset is maximal if and only if the union of its upset and its downset is the entire poset. Some maximal antichains admit a stronger property: they can be partitioned into two sets A, B such that the union of the upset of A with the downset of B is the entire poset. These antichains are said to split. Though it is hopeless to characterize the antichains that split in terms of a "quickly testable" criterion (unless P=NP), we give an elegant sufficient condition using the notion of denseness in a poset. Finally, we introduce a new, stronger property that a maximal antichain may satisfy, the reversible splitting property, and find a few classes of antichains that satisfy it and a few that don't.




Date:	October 26, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Nakamura
Title:	What I Did Last Summer, Part 2: Rubbling at the REU
Abstract:	This semester kicked off with a similarly named GCS talk on graph pebbling. In this talk, I will introduce the notion of graph rubbling, which generalizes the graph pebbling move in a natural way. Many of the questions asked in graph pebbling can be analogously asked in the graph rubbling setting. I will focus my talk on fairly basic results of graph rubbling, partly because not much has been done in the area yet. I will also talk about the work that my REU student did in this area this past summer and offer some problems that may be good undergraduate projects.




Date:	October 19, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Arran Hamm
Title:	Local Resilience of Graph Properties
Abstract:	For a graph G and a graph property P, the (global) resilience of G with respect to P is the minimum number of edges which must be altered (either added or removed) so that it no longer satisfies P. For example, Dirac's Theorem could be thought of as a resilience theorem for G=K_n. In the past few years the idea of local resilience has drawn some attention. For a graph G and a graph property P, the local resilience of G with respect to P is the minimum number of edges which must be altered at each vertex so that it no longer satisfies P. Most of the talk will be aimed at settling this question for G=G(n,p) and P is "has a perfect matching", "has a Hamiltonian Cycle", or "has chromatic number at most f(n,p)."




Date:	October 12, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Kuratowski's Theorem
Abstract:	A graph is planar if and only it does not have either K5 or K3,3 as a minor. We will prove this as many times as possible in fifty minutes.




Date:	October 5, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Elizabeth Kupin
Title:	Graphs and Colorful Paths
Abstract:	The classical coloring question for a graph is to determine its chromatic number: the minimum number of colors needed in a "proper coloring," that is, one where no two adjacent vertices have the same color. This is number denoted χ(G), and has been studied very extensively. We will look at the related question of determining when a given graph G has a proper coloring with χ(G) colors, with the additional constraint that each vertex is one endpoint of a "rainbow" path of length χ(G) (i.e. no vertices on this path have the same color). In this talk I'll present some known results about cases when this is possible, a new result of mine, and then highlight some open problems that should be fairly accessible for grad student research. This work came out of participating in the Illinois REGS program, which I highly recommend to grad students who interested in research in Combinatorics and who are currently in their first, second or third years.




Date:	September 28, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Bobby DeMarco
Title:	Cycle Spaces of Random Graphs
Abstract:	I will first introduce and define the cycle space and cut space of a graph. I will then talk about classic ways to find an independent set of generators of the cycle space. Finally, recent research into when the generators of the cycle space are of a certain type will be discussed. Time permitting, the motivation of this research will also be explored. (Joint with Arran Hamm and Jeff Kahn.)




Date:	September 21, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	What I Did Last Summer: Pebbling at the REU
Abstract:	In combinatorics, REU problems are often very much like the best research questions -- easy to state and quite hands-on, but much deeper and more difficult to prove than they seem at first. I will introduce graph pebbling, work through some examples (audience involvement will be encouraged), and present some basic results. I will then discuss Graham's conjecture and partial results to that effect and describe some of the work the DIMACS REU students did this summer (in which I was tangentially involved).

Spring 2011 Abstracts

Date:	April 27, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Andrew Baxter
Title:	The Umbral Transfer Matrix Method
Abstract:	In 2000 Zeilberger introduced the umbral transfer matrix method, which combines the umbral calculus with the transfer matrices. This expository talk will outline the transfer matrix method, and then demonstrate how umbral operators strengthen the method.




Date:	April 20, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Emilie Hogan
Title:	Somos Sequences - Past and Present
Abstract:	In this talk I will introduce the famed Somos sequences: integer sequences produced by rational recurrences. After Michael Somos introduced these recurrences and sequences, the research area took off. Many people found related recurrences and developed techniques to prove integrality. I will first talk about the three types of proofs that were used to prove integrality of the original Somos sequences. Then I will talk about a recurrence, inspired by Somos, that I discovered with Paul Heideman at University of Wisconsin - Madison while working with Jim Propp. Finally, I will talk about recurrences that surprisingly generate rational numbers (when complex numbers are expected) that I have studied as part of my thesis.




Date:	April 13, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Humberto Montalván
Title:	A New Result In Geometric Discrepancy
Abstract:	Given n points in the unit square Schmidt showed that there is an axis-parallel rectangle R for which the discrepancy (the difference between the number of given points lying in R and the area of R times n) is at least C*log(n) where C is an absolute constant. In this talk I will give a sketch of the proof of this result. Then I will show how to adapt Schmidt's argument to show that a fraction of all axis-parallel rectangles have large discrepancy.




Date:	April 6, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ke Wang
Title:	Optimal local semi-circle law and delocalization
Abstract:	Consider a random n×n Hermitian matrix Mn whose upper triangular entries are iid with mean 0, variance 1 and sub-exponential decay. The famous Wigner's semicircle law characterizes the limiting distribution of the eigenvalues of (1/√n) Mn on any fixed interval I=[a,b], which is known as the global spectral statistics. In this talk, I will discuss the local semicircle law, i.e. for intervals whose size may shrink with n, on an optimal scale. As a consequence, the eigenvector delocalization result is obtained. Joint work with Van H. Vu.




Date:	March 30, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Timothy Naumovitz
Title:	Combinatorial Games
Abstract:	Abstract: Given a two-player game in which one player will always win after a finite amount of time, how can we find a winning strategy for one player? This talk will attempt to answer this question by classifying such combinatorial games and then proving a few theorems that help us answer this question in the case of normal, impartial games. In particular, we will find a winning strategy for nim and attempt to do so for a few other games.




Date:	March 23, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Elizabeth Kupin
Title:	Compatible Geometric Matchings
Abstract:	Generally in graph theory we distinguish between a graph and a drawing, or embedding of the graph into the plane. In geometric graph theory, however, we work with a fixed drawing of a graph, and investigate its geometric properties. In particular, we'll be interested in planar, straight-line embeddings of perfect matchings. This is essentially a disjoint set of line segments. Some basic questions we could ask are does every set of 2n points in the plane have a straight line perfect matching? Can there be more than one? If we don't allow matchings to cross each other (in addition to not crossing themselves), how many can there be? These basic questions lead up to a beautiful open problem, that I will present some partial results on.




Date:	March 9, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Brian Nakamura
Title:	Consecutive Patterns in Permutations
Abstract:	In recent years, there has been increasing interest in consecutive pattern avoidance in permutations. This talk will give a brief overview of this area of research as well as some recent results and open problems. I will also spend some time discussing my research on consecutive pattern avoidance using the cluster method and experimental mathematics. Conscious effort will be made not to make the talk overly technical.




Date:	March 2, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Aleksandar Nikolov
Title:	Tight Hardness Results for Minimizing Discrepancy
Abstract:	In the discrepancy problem, we are given $M$ sets $\{S_1,\ldots,S_M\}$ on $N$ elements. Our goal is to find an assignment $\chi$ of $\{-1,+1\}$ values to elements, so as to minimize the maximum discrepancy $\max_{j} |\sum_{i \in S_j} \chi(i)|$. Recently, Bansal gave an efficient algorithm for achieving $O(\sqrt{N})$ discrepancy for any set system where $M=O(N)$, giving a constructive version of Spencer's proof that the discrepancy of any set system is at most $O(\sqrt{N})$ for this range of $M$. We show that from the perspective of computational efficiency, these results are tight for general set systems where $M=O(N)$. Specifically, we show that it is NP-hard to distinguish between such set systems with discrepancy zero and those with discrepancy $\Omega(\sqrt{N})$. This means that even if the optimal solution has discrepancy zero, we cannot hope to efficiently find a coloring with discrepancy $o(\sqrt{N})$. The hardness results in both settings are obtained from a common framework: we compose a family of high discrepancy set systems with set systems for which it is NP-hard to distinguish instances with discrepancy zero from instances in which a large number of the sets (i.e. constant fraction of the sets) have non-zero discrepancy. Our composition amplifies this zero versus non-zero gap. The framework provides a general method to derive computational hardness results from combinatorial lower bounds on discrepancy. No prior knowledge of discrepancy theory or complexity theory will be required. The proofs are short and I will try to present them in as much detail as possible. Joint work with Alantha Newman and Moses Charikar.




Date:	February 23, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Kellen Myers
Title:	Experimental Mathematics in Action
Abstract:	This talk will be highly audience-interactive! We will go through an overview of a few useful methods in experimental mathematics, followed by some hands-on demonstration. This will include, hopefully, audience-generated problems and ideas.




Date:	February 16, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Matthew Russell
Title:	Quantum Walks on Graphs
Abstract:	This talk is designed to provide an introduction to the concept of continuous-time quantum walks on graphs. A quantum analogue of the familiar random walks on graphs, quantum walks are important, as they can provide a way to develop fast quantum algorithms. One interesting phenomenon that can occur is perfect state transfer, which occurs when a particle that begins completely localized at one vertex can be found with probability 1 at some other vertex at some later time: a quantum state is perfectly transferred between vertices. We will explore some families of graphs that exhibit perfect state transfer.




Date:	February 9, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Vladimir Gurvich (RutCOR)
Title:	Metric and Ultrametric Spaces of Resistances
Abstract:	Given an electrical circuit each edge e of which is an isotropic conductor with a monomial conductivity function ye* = yer / μes, where, ye is the potential difference and ye* current in e, while μe is the resistance of e; furthermore, r and s are two strictly positive real parameters common for all edges. In particular, r = s = 1 is the standard Ohm law; r = 1/2 is typical for hydraulics or gas dynamics. For every two nodes a, b the effective resistance μa,b is well-defined and for every three nodes a,b,c the inequality μa,bs/r ≤ μa,cs/r + μc,bs/r holds. It implies the standard metric inequality whenever s ≥ r and ultramentric one when s(t)/r(t) → ∞, as t → ∞. One can get several metric and ultrametric spaces playing with parameters r and s. In particular, the effective Ohm resistance, the length of a shortest path, the inverse width of a bottleneck path, and the inverse capacity (maximum flow per unit time) between any pair of terminals.




Date:	February 2, 2011
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Robert DeMarco
Title:	Dependent Random Choice
Abstract:	I will discuss the surprisingly simple and effective (and relatively new) method of "Dependent Random Choice" in graph theory, relying on the recent survey paper on this method written by Benny Sudakov and Jacob Fox. Applications to Ramsey Theory and additive combinatorics (Balog-Szemeredi-Gowers theorem) will be sketched.

Fall 2010 Abstracts

Date:	December 8, 2010
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Amanda Redlich (Post-Doc, Mathematics)
Title:	Unbalanced Allocations
Abstract:	Recently, there has been much research on processes that are mostly random, but also have a small amount of deterministic choice; e.g., Achlioptas processes on graphs. This talk builds on the balanced allocation algorithm first described by Azar, Broder, Karlin and Upfal. Their algorithm (and its relatives) uses randomness and some choice to distribute balls into bins in a balanced way. Here is a description of the opposite family of algorithms, with an analysis of exactly how unbalanced the distribution can become.




Date:	December 1, 2010
Time:	12:10 PM
Place:	Graduate Student Lounge, 7th Floor, Hill Center
Speaker:	Ji Young Choi (DIMACS)
Title:	A Markov Chain Application on Multi-restricted Stirling numbers
Abstract:	Cows are drawn one after the other from a farm initially containing r whites, according to the following scheme: if white is drawn, place a black cow in the farm; if black is drawn, put it back. What is the probability to draw k white cows in n trials, if each black cow can be drawn no more than m times? In this talk, the solution for the above question will be presented using the Multi-restricted Stirling numbers of the second kind, which is the number of partitions of an n set with k nonempty subsets of size less than or equal to m.




Date:	November 22, 2010 [Rescheduled from Nov 17]
Speaker:	Emilie Hogan
Title:	Convergence of Rational Recurrences Using Experimental Methods
Abstract:	I will talk about my current research which involves proving convergence of sequences produced by rational recurrences. The goal is to create an algorithm which takes as input a rational recurrence and a conjectured limit, and outputs true if the sequence produced by the recurrence converges independently of the initial conditions. My approach is to reduce the problem to proving that a certain related polynomial is positive. I will outline how this reduction is done and also explain my method for proving that a polynomial is positive using simple algebraic manipulations and sufficient conditions. This is joint work with Doron Zeilberger.




Date:	November 10, 2010
Speaker:	Brian Thompson (Computer Science)
Title:	"A Streaming Model for Anomaly Detection in Communication Networks: A Renewal Theory Approach";               OR "Graph Algorithms and a Little Bit of Statistics, and Getting DHS to Pay For It"
Abstract:	Being a mathematician in a Computer Science department with a DHS fellowship poses an interesting research challenge: How can I still do math but get the Department of Homeland Security to fund me? Fortunately, many real-world security problems can be framed using mathematical constructs. Any type of human interaction (e.g. email, phone, face-to-face encounters, internet connections) can be modeled by a network graph, where vertices represent people or computers, and an edge signifies a relationship such as "friends". However, communication networks have a highly dynamic nature \96 that Alice and Bob are friends says nothing about the frequency or regularity of their communication. To analyze communication in a network, we first build a stochastic model based on temporal patterns across each edge, using tools from Renewal Theory. With a little help from statistics, we then define a quantitative measure of "anomaly" in an arbitrary subgraph. Finally, we develop graph algorithms to efficiently identify subgraphs with the most anomalous behavior.




Date:	November 3, 2010
Speaker:	Beth Kupin
Title:	Combinatorics for Analysts, and Other Adventures in Research
Abstract:	In grad school we think of ourselves as specializing in a single area of math, but often chasing a research problem can take us all over the place. When this happens it can be helpful to have friends in other disciplines! I'm going to talk about two small but sweet combinatorial results that helped some other grad students with their (not at all combinatorial) research. I'll also talk a little bit about my experiences with research throughout the talk, and what I've seen of the transition from just doing homework exercises to doing original work.




Date:	October 27, 2010
Speaker:	Humberto Montalvan
Title:	Arithmetic Progressions Instead of Billiard Paths
Abstract:	Prof. Beck recently discovered a phenomenon that he named super-uniformity of billiard paths. In essence he was able to prove that for an arbitrary measurable subset A of the unit square, most billiard paths of length T approximate the area of A with O(√( log T ) ) error. This led him to declare that "the set of typical billiard paths represents the family of most uniformly distributed curves in the square." He then wondered if there were any interesting discrete analogues of this result. In this talk we will consider the following situation. Let N be a fixed large number and S be an arbitrary subset of the discrete interval {1,2,...,N}. Is it true that the density of S is faithfully represented in most full-length arithmetic progressions taken from the set {1,2,...,N}? More precisely, is #{1 ≤ n ≤ N : n = r (mod m) and n is in S} close to (#S)/m for most choices of m and r? The answer is no, and this is quite obvious and unfortunate. Prof. Beck was nontheless able to prove something! I will present the precise statement of the result, discuss how it is fundamentally different from the billiard paths result, and give a sketch of its proof. If time permits I will also mention some related unanswered questions.




Date:	October 20, 2010
Speaker:	Robert DeMarco
Title:	Upper Tails for Triangles
Abstract:	Let ξn,p be the number of copies of K3 (triangles) in G(n,p). I will discuss various methods that have been used to bound the upper tail of this random variable, meaning to bound Pr( ξn,p > (1+ε) E[ξn,p] ). The last method discussed will be the one developed by myself and Professor Kahn to find an upper bound that is tight up to a constant factor in the exponent for all values of p. If time permits, I will briefly discuss extensions of this final method to the general clique case.




Date:	October 13, 2010
Speaker:	Arran Hamm
Title:	Some Algebraic Combinatorics
Abstract:	In this talk we will discuss the Chevalley-Warning Theorem and Combinatorial Nullstellensatz (two algebraic theorems) and their applications to combinatorial problems. The Cauchy-Davenport Theorem states that if we have two nonempty subsets, A and B, of Z_p for p prime, then |A+B| is at least the minimum of |A|+|B|-1 and p. We'll see an algebraic proof using CN and extend to a few related problems. If time permits, we'll discuss the formerly-known-as Kemnitz Conjecture.




Date:	October 6, 2010
Speaker:	Brian Nakamura
Title:	The Goulden-Jackson Cluster Method
Abstract:	One type of problem in enumerative combinatorics is to count words that avoid some set of "bad words". The Goulden-Jackson Cluster method provides a way to often find generating functions for such problems. In this talk, I will give an overview of the Cluster method along with some of its extensions. If time permits, I will also discuss its applications in consecutive pattern avoidance in permutations.




Date:	September 29, 2010
Speaker:	Andrew Baxter
Title:	Pattern Avoidance by Even Permutations
Abstract:	Questions regarding the containment/avoidance of permutation patterns have been considered for over 20 years. In particular, it is of interest to know the number of permutations of length n which avoid a given set of patterns. Recently, effort has gone into asking how many permutations of length n with a given property avoid a given set of patterns. For example, last year's seminar had a talk by Aaron Jaggard regarding pattern-avoiding involutions. In this talk I will summarize my work with Jaggard regarding the number of even permutations avoiding a set of patterns. No knowledge of permutation patterns will be assumed.




Date:	September 22, 2010
Speaker:	Amira Kebir (DIMACS)
Title:	Mathematical and computational modeling and analysis for hermaphrodite population dynamics
Abstract:	My research works deal with mathematical and computational modeling and analysis of a hermaphrodite populations. The main objective of these works is to study the implication of a density dependent sex allocation on the dynamic of these populations. Indeed, the sex-ratio of the hermaphrodite species depend on the sex-allocation function and it was proven for some species and in presence of sexual competition that this function is density dependent which lead to a complex population dynamics. Two surrounding areas of modelings were developed to study these species and to reflect their characteristics: a density deterministic approach and an Individuals Based Model approach. For individual based approach, the model allows us to take an account the variability of phenotypic (e.g. fitness) and behavioral characteristics (sexual allocation) and the interactions between individuals. This approach complements our information on the effect of sex allocation for hermaphrodite populations. By the analysis of these models we have proved the importance of sex allocation function form as well as survival parameters on the dynamics of hermaphroditic species. In fact, by the manipulation of the hermaphrodite life history parameters, we found the causes and the environmental conditions by which we can observe the stability, the explosion, the extinction or even a more complex dynamics like chaos. [Note: This talk will be a basic introduction into this research and related methods. -km]




Date:	September 15, 2010
Speaker:	Kellen Myers
Title:	The Fourier Transform and Enumeration
Abstract:	This talk will provide a brief and gentle introduction into applications of the Fourier transform to enumerative problems. Some definitions and explanations will be provided, leading to comparisons between elementary enumeration techniques (that is, counting) and the techniques using the Fourier transform.

Spring 2010 Abstracts

Date:	April 28, 2010
Speaker:	Nikos Leonardos (Computer Science)
Title:	Introduction to communication complexity
Abstract:	There are two parties, Alice and Bob. Each receives an n-bit string; Alice gets x, Bob gets y. Their goal is to compute a (boolean) function f(x,y). Since they can only see their own input, they need to communicate by sending bits to each other,until they both know f(x,y). We are interested in the amount of communication they need (say worst case over all x,y). We'll see some basic properties and simple lower-bounds for this model. Another interesting model is one where there are more players, say 3, and while they can see the input of any other player, they cannot see their own. Proving lower-bounds in this model seems to be hard. It also allows for some clever protocols, and we'll see one.




Date:	April 21, 2010
Speaker:	Ke Wang
Title:	Laplacian eigenmaps
Abstract:	Laplacian eigenmaps is a geometrically motivated algorithm in performing nonlinear dimensionality reduction. In this talk, I will describe this algorithm, explain the idea behind and show how the graph Laplacian is playing a role here and in other algorithms.




Date:	April 14, 2010
Speaker:	Jeff Kahn (Professor, Mathematics)
Title:	Extremal counting problems for matchings and independent sets
Abstract:	I'll mention one or two theorems, but will mostly focus on open problems. Sample question: how may independent sets can one have in a d-regular graph on n vertices? (An independent set is a set of vertices spanning no edges.) A mildly unifying theme that I'll try and probably fail to get to is the use of entropy in attacking some of these questions.




Date:	April 7, 2010
Speaker:	Fengming Wang (Computer Science)
Title:	VC Dimension and Learning Theory
Abstract:	Vapnik-Chervonenkis dimension (VC dimension) is an important combinatorial concept which measures the classification complexity of a set of boolean functions over any fixed domain. In this talk, we will introduces it by several interesting examples and demonstrate that this notion captures exactly the query complexity of any learning task within the PAC (Probably Approximately Correct) framework, one of the most popular models in computational learning theory.




Date:	March 31, 2010
Speaker:	Arran Hamm
Title:	Perfect and "Imperfect" Graphs
Abstract:	A perfect graph is one such that for every induced subgraph, the chromatic number equals the clique number. The PGT states that a graph is perfect if and only if its complement is perfect. In this talk an elementary proof of this will be given using a bit of linear algebra. On the other hand, graphs which are far from perfect will be discussed with a probabilistic theorem of Erdos and then an elementary (yet shocking) construction of such graphs will be given.




Date:	March 24, 2010
Speaker:	Kellen Myers
Title:	The Genus of Graphs and Groups: An Alliterative Survey
Abstract:	Kuratowski's theorem, a result presented in most introductory courses and texts on graph theory, characterizes precisely which graphs are planar (i.e. embeddable in the plane with no edges crossing). Extending this characterization to other surfaces, we can define the genus of a graph to be minimal genus for a surface into which the graph embeds. We can extend this definition to a group by examining the Cayley graph of the group (with respect to some set of generators), and taking the minimum over all generating sets. This talk will attempt to introduce these concepts in a broad, survey format, with examples, illustrations, and explanations for each definition, theorem, and observation. Major results will be presented to extend and motivate the elementary concepts in the talk, as well as to give some interesting level of results, but the focus of the talk will be to introduce the material at an elementary level.




Date:	March 10, 2010
Speaker:	David Wilson
Title:	A journey through Van der Waerden's Theorem
Abstract:	Van der Waerden's Theorem is one of the "classical Ramsey Theorems" and concerns the existence of monochromatic arithmetic sequences in arbitrary colorings of the natural numbers. I will talk through a proof of the theorem before talking a little on bounds on the VdW numbers (including the pretty cool wow and ack functions) and finish by mentioning a recent result on a similar problem involving geometric progressions, with a little twist.




Date:	March 3, 2010
Speaker:	Robert DeMarco
Title:	Expander graphs and applications of graph theory
Abstract:	Expander graphs are sparse regular graphs which, as one might expect, "expand" well. More mathematically, but still not precisely, these are graphs in which the neighborhood of any set of vertices is sufficiently large relative to the size of the initial set. The applications of such graphs to Monte Carlo algorithms (e.g. primality testing) will be discussed. In doing so we will discuss the relationship between the spectral properties of a graph and it's expanding properties, and discuss the extension of such ideas to quasi-random graphs. This talk will mostly follow much of the material from Alon-Spencer 9.2




Date:	February 24, 2010
Speaker:	Emilie Hogan
Title:	Recurrences that Generate Surprising Numbers
Abstract:	The most basic type of recurrence is a linear recurrence (e.g., Fibonacci). These types of recurrences generate integers, but this is not surprising. In order to get integers in an unexpected way you must consider non-linear recurrences. A well known example of a non-linear recurrence is the Somos-4 recurrence. In order to get the n^th number in the sequence you must take some combination of the n-1st, n-2nd, and n-3rd numbers and then *divide* by the n-4th number. Even though we divide, we still get integers. I will talk about this phenomenon generally and give a few other examples. Finally I will introduce the concept of a recurrence that does not generate a sequence, but instead generates multiple values at each step by solving a degree n polynomial. In this situation it becomes surprising that we generate rational numbers.




Date:	February 17, 2010
Speaker:	Jay Williams
Title:	An Introduction to Infinitary Combinatorics
Abstract:	You may think of set theory as a hideously abstract topic, removed completely from your preferred branch of study. But there is a strong combinatorial core to many results in set theory. In this talk, I will discuss how combinatorial ideas pop up, from the infinite Ramsey theorem to delta-systems to posets, and a few other things besides. I'll even mention a result due to Erdos and Rado! No set theory background will be assumed, so don't be afraid.




Date:	February 10, 2010
Speaker:	David John Wilson
Title:	A journey through Van der Waerden's Theorem
Abstract:	TALK WAS CANCELED, DUE TO SNOW - rescheduled for later in the semester




Date:	February 3, 2010
Speaker:	Elizabeth Kupin
Title:	Rectangle-Free Grid Coloring
Abstract:	Imagine a sheet of graph paper, that we will fill in entirely by assigning each square a color. How many colors do we need to be able to guarantee that no 4 squares that are the corners of an (axis-parallel) rectangle have the same color? This Ramsey-type question turns out to be similar to a question about bipartite Ramsey numbers, and lately there has been some effort in lowering the bounds and constructing exact solutions. I'll talk about some of the history of the problem, the many questions that are still open, and maybe a bit of the work I've done to try to tackle these problems.




Date:	January 27, 2010
Speaker:	Humberto Montalvan-Gamez
Title:	Regularity of Billiard Paths in Higher Dimensions
Abstract:	It is well known that billiard paths in a square table are evenly distributed: that one can use them to measure area approximately. Quite recently our own J. Beck discovered a surprising estimate of the error in such approximations. After stating Beck's result clearly and explaining the main ideas of the proof, I will explore possible extensions to higher dimensions. (A cubic billiard table? A billiard plane instead of a billiard path? Can Beck's argument be adapted to work in higher dimensions?)

Fall 2009 Abstracts

Date:	December 10, 2009
Speaker:	Dev Desai (Computer Science)
Title:	An upper bound on the bisection width of regular graphs.
Abstract:	T he 'bisection width' of a graph is defined as the minumum number of edges than need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large. In this talk, I will present a result of Noga Alon's, which gives an upper bound on the bisection width of any d-regular graphs, when the number of vertices is 'much more' than d. Time permitting, I will also discuss some other interesting cut problems and what we know about them.




Date:	December 2, 2009
Speaker:	James Abello (DIMACS)
Title:	Hierarchical Graph Maps
Abstract:	A variety of massive data sets exhibit an underlying structure that can be modeled as dynamic weighted multi-digraphs. Their sizes range from tens of gigabytes to petabytes. These include the World Wide Web, Internet Traffic and Telephone Call Detail. These data sets sheer volume brings with it a series of computational and visualization challenges due mainly to the I/O and Screen Bottlenecks. We present external memory algorithms for connectivity and minimum spanning trees together with heuristics for quasi-clique finding. We describe how hierarchical Graph Maps help us to cope in a unified manner with both, the I/O and screen bottlenecks. This line of research has suggested the need to look for "novel" graph representations in order to provide a user or a data-mining engine with informed navigation paths. We will discuss our results with graphs having on the order of 100 million vertices and several billion edges and we will point out some mathematical problems that have surfaced along the way. The overall goal is to extract useful information that can be brought into a user's palm top and to export these techniques to other mining domains.




Date:	November 18, 2009
Speaker:	Aaron Jaggard (DIMACS)
Title:	Parallels between classes of permutations
Abstract:	We discuss some different combinatorial ways in which two classes of permutations might resemble each other. We'll focus on parallels between involutions in the symmetric group and the symmetric group as a whole, in particular parallels related to pattern avoidance. We'll also suggest some related interesting questions.




Date:	November 11, 2009
Speaker:	Linh Tran
Title:	Combinatorics of Random Boxes
Abstract:	Consider a set of n random axis parallel boxes in the unit hypercube in R^d, where d is fixed and $n$ tends to infinity, with some overlaps here and there. What is the most economic way to shoot all the boxes, i.e. with the minimal amount of bullets? In the talk I will show you how to attack the problem using several tools and tricks from probabilistic combinatorics. There will also be a very bold (and still open) conjecture for someone who like a challenge!




Date:	November 4, 2009
Speaker:	Brian Thompson (Computer Science)
Title:	My Problem is Harder Than Yours: Complexity Theory for the Combinatorialist
Abstract:	A spaceship lands in the Mathematics Graduate Student Lounge during Pizza Seminar one day. An evil-looking alien hops out and threatens to destroy all of Hill Center next year unless we solve one of two problems: 1) Solve an order-n Sudoku puzzle. 2) Determine whether two graphs on n vertices are isomorphic. We get to choose the problem, then the alien will give us the hardest example he/she/it can conjure. Which should we choose? Oddly enough, there's a whole field of theoretical computer science devoted to answering these kinds of questions. We will discuss the idea of reduction, a key concept in Complexity Theory, and use it to compare the relative difficulties of various combinatorial problems.




Date:	October 28, 2009
Speaker:	Andrew Baxter
Title:	Using the cluster method to enumerate generalized permutation patterns.
Abstract:	In 2000, Babson and Steingrimsson introduced generalized permutation patterns, with definitions general enough to apply to words on n letters. Using the cluster method, we develop recurrences which count words according to the number of occurrences of certain generalized permutation patterns. From this we can determine qualities such as equidistribution and packing densities.




Date:	October 21, 2009
Speaker:	Wes Pegden
Title:	The Local Lemma and its Applications
Abstract:	The Lovasz Local Lemma is a power tool in probabilistic combinatorics. In contrast to simpler probabilistic proof techniques, the Local Lemma allows probabilistic proofs for the existence of even very rare combinatorial objects. In this talk, I will state and "interpret" the Local Lemma, and show how it can be applied in a variety of situations. I will also discuss some common pitfalls (we will "prove" that a triangle can be 2-colored). Time permitting, I will talk some about my research on applications of the Local Lemma to games.




Date:	October 14, 2009
Speaker:	Emilie Hogan
Title:	Recurrences that Generate Surprising Numbers
Abstract:	The most basic type of recurrence is a linear recurrence (e.g., Fibonacci). These types of recurrences generate integers, but this is not surprising. In order to get integers in an unexpected way you must consider non-linear recurrences. A well known example of a non-linear recurrence is the Somos-4 recurrence. In order to get the n^th number in the sequence you must take some combination of the n-1st, n-2nd, and n-3rd numbers and then *divide* by the n-4th number. Even though we divide, we still get integers. I will talk about this phenomenon generally and give a few other examples. Finally I will introduce the concept of a recurrence that does not generate a sequence, but instead generates multiple values at each step by solving a degree n polynomial. In this situation it becomes surprising that we generate rational numbers.




Date:	October 7, 2009
Speaker:	Hoi Nguyen
Title:	A Detour on the Littlewood-Offord Theorem
Abstract:	Several classical results on the Littlewood-Offord problems will be discussed. We then introduce a new perspective. Applications will be discussed if time permits.




Date:	September 30, 2009
Speaker:	Brian Nakamura
Title:	Graph Pebbling
Abstract:	Graph pebbling is a simple notion: scatter some pebbles onto the vertices of a connected graph and if there are at least 2 pebbles on the same vertex, we can remove one pebble and move the other pebble to a neighbor of that vertex. From this though, a number of interesting questions can be asked. This talk will provide a brief overview of some of those problems and a few interesting results.




Date:	September 23, 2009
Speaker:	Ke Wang
Title:	A quick introduction to Spectral Graph Theory
Abstract:	Spectral graph theory is concerned with the eigenvalues and eigenvectors of matrices associated with graphs (Laplacian matrix, adjacency matrix, etc), and their application. In this talk, I will introduce the Laplacian matrix, discuss some basic facts about the spectrum of a graph, and survey some older and newer results in the end.




Date:	September 16, 2009
Speaker:	Humberto Montalvan
Title:	A Proof of the Erdos-Stone Theorem
Abstract:	In this talk I will show how one can prove the celebrated Erdos-Stone theorem using Szemeredi's regularity lemma. Time permitting, I will discuss an intriguing application of the theorem.




Date:	September 9, 2009
Speaker:	Robert DeMarco
Title:	Applications of Graph Theory: Disease Spread and More
Abstract:	This talk will introduce the use of graphs in modeling of disease spread and vaccination. Similar models can also be used to help study crystal growth, forest fire-fighting and public opinion. I will note a few results in these areas, from the very real-world applicable to the completely non applicable yet beautiful. To ease us into the semester, the focus will be on stating and motivating pretty theorems and not on technical details.

Spring 2009 Abstracts

Date:	April 29, 2009
Speaker:	Humberto Montalvan
Title:	Chromatic Number of the Random Graph G(n,1/2)
Abstract:	Abstract: The aim of this talk is to present a proof of the amazing fact that almost always the random graph G(n,1/2) has chromatic number (n/(2*log_2(n)))*(1+o(1)). Naturally one has to show that two inequalities hold. I will give Bollobas' original proof (dating back to 1988) of the harder inequality, using martingales.




Date:	April 22, 2009
Speaker:	Ke Wang
Title:	Stein's Method
Abstract:	Stein's method was first introduced in the late 1960s by C.Stein in his lecture as a new way of proving the Central Limit theorem. Since then, the method has been developed and applied to many other distribution approximations. A feature of Stein's method is that it provides explicit estimates of the accuracy of the approximation of one probability distribution by another. I will first explain the general approach of Stein's method, and then apply it to prove the Central Limit theorem and the Berry-Esseen Theorem.




Date:	April 15, 2009
Speaker:	Emilie Hogan
Title:	Planarity and Wagner's Conjecture
Abstract:	Kuratowski and Wagner's theorems give us a characterization of planar graphs by forbidden minors and topological minors. The fact that we have such a characterization (by a finite number of forbidden minors!) is quite surprising. Wagner's conjecture is a generalization of this to other surfaces and says that given any surface, the graphs that can be embedded are characterized by finitely many forbidden minors. Eventually Paul Seymour and Neil Robertson proved Wagner's conjecture with the Graph Minor Theorem. I will talk about the proof of Kuratowski and Wagner's planarity theorems, and how the Graph Minor Theorem proves Wagner's big conjecture.




Date:	April 8, 2009
Speaker:	Dan Cranston (DIMACS)
Title:	Crossings, Colorings, and Cliques
Abstract:	There are three classical relaxations of planarity (which we define below): the genus of a graph, the thickness of a graph, and the crossing number of a graph. The {\it genus} of a graph is the minimum genus of a surface on which the graph can be embedded. The {\it thickness} of a graph is the minimum number of planar subgraphs needed to partition the edges of the graph. The {\it crossing number} of a graph is the minimum number of pairs of edges that cross in a drawing of G in the plane (the minimum is taken over all drawings). The relationship between the genus of a graph and its chromatic number has been studied extensively. This study culminated in the late 1960s with the Ringle-Youngs Theorem, which states that the maximum chromatic number of a graph embeddable in each surface S is precisely the size of the largest clique embeddable in S. Similar results are known for thickness; they say that the maximum chromatic number of a graph with thickness k is at most 1 more than the size of the largest clique with thickness k. What is surprising, then, is how little is known about the relationship between chromatic number and crossing number. In 2007, Mike Albertson conjectured that if graph G has chromatic number r, then G has crossing number at least that of K_r. The case r = 5 is equivalent to the 4 Color Theorem and the only other case verified until now was r = 6. Recently Albertson, Jacob Fox, and I verified the conjecture for 7 < r < 12.




Date:	April 1, 2009
Speaker:	Kellen Myers
Title:	Van der Waerden's theorem
Abstract:	In 1927, B.L. van der Waerden proved the theorem that bears his name: for given integers r and k, there exists an N so that any r-coloring of the integers 1 through N contains a monochromatic arithmetic progression of length k. Proof of this theorem will be presented, as well as an explanation of the sorts of bounds on N (w.r.t r and k) that are known. I will also discuss, if time permits, generalizations and related ideas, including the Hales-Jewett theorem and Szemeredi's theorem. If there is any extra time, I will also present an interesting new combinatorial proof of a famous conjecture of Fermat.




Date:	March 25, 2009
Speaker:	Robert DeMarco
Title:	Extremal Graph Theory
Abstract:	This talk will be a quick overview of this large topic in combinatorics. It will first review two of the famous theorems of Turan and Dirac that not only are important on their own but helped give rise to the field of extremal graph theory. The talk will then present a few more recent theorems and questions in this field with more (or less) detail depending on time. Yay!




Date:	March 11, 2009
Speaker:	Thomas Robinson
Title:	Umbral calculus
Abstract:	I will derive (mostly) a formula for the higher derivatives of a composite function. Using that result, I will get some adjoint formulas from the classical umbral calculus. I will also discuss the Riordan group which arises in the classical umbral calculus and give a combinatorial interpretation.




Date:	March 4, 2009
Speaker:	Jay Williams
Title:	Infinite trees, Konig's Lemma, and Aronszajn trees
Abstract:	Everybody loves graphs and trees, even set theorists. But, not content to work with just finite trees, they have developed large bodies of work regarding infinite trees. For instance, Konig's lemma states that an infinite tree in which each level is finite has an infinite branch. We will see an example of how this is useful. Then we'll discuss what it means for a tree to have uncountable height and construct an Aronszajn tree, an uncountable-height tree with some surprising properties. No set theory will be assumed, so don't be afraid.




Date:	February 25, 2009
Speaker:	Beth Kupin
Title:	Concentration Inequalities and Tail Bounds
Abstract:	Naively, we look at the expectation of a random variable to get a sense of what its value will be. Unfortunately, expectation doesn't always give a good picture, and so when we need more acurate information one possibility is to turn to more advanced methods to try to determine how close a random variable is to its expected value. I'll introduce a few of these "tail bound" inequalities (Markov, Azuma, and Talagrand), and focus on examples that compare their various strengths and weaknesses. No probability thoery required!




Date:	February 18, 2009
Speaker:	Mike Neiman
Title	List Coloring Bipartite Graphs
Abstract:	The list-coloring number of a graph is the minimum number k such that for every assignment of a list of at least k colors to each vertex there is a proper vertex coloring assigning to each vertex a color from its list. I'll talk about bounds for the list-coloring numbers of bipartite graphs, some of which are due to N. Alon. This will be an expository talk, with emphasis on some probabilistic techniques and an interesting open problem.




Date:	February 11, 2009
Speaker:	Phil Matchett Wood
Title:	On a Conjecture of Alon
Abstract:	Let f(n,m) be the cardinality of largest subset of {1,2,...,n} which does not contain a subset whose elements sum to m. I would give you some example values of f(n,m) that might lead you to conjecture an asymptotic formula, but I just crashed Maple (last time I use the graphical interface instead of the command line!), taking my tiny bit of code with it. In any case, in this talk, we will show that f(n,m) = (1+o(1)) n / snd(m), so long as n(\log n)^(1+\epsilon) <= m <= n2/(9\log^2n) , which matches the hypothesis that f(n,m) is near n/snd(m). This proves a conjecture of Alon posed in 1987 and demonstrates a structural approach to a sumset problem. Joint work with Linh Tran and Van Vu.




Date:	Feb 4, 2009
Speaker:	Andrew Baxter
Title:	An Introduction to Generating Functions, Part 2
Abstract:	In the second part of the two-part primer on generating functions, I will discuss exponential generating functions. Adding an extra twist can allow for better results when counting labeled objects like labeled trees. The two most general techniques are the Exponential Theorem and the Lagrange Inversion Formula, which will be discussed at length. If there is time, I will demonstrate further types of generating functions such as doubly-exponential or Eulerian generating functions.




Date:	January 28, 2009
Speaker:	Eric Rowland
Title:	An Introduction to Generating Functions, Part 1
Abstract:	The first installment in this acclaimed miniseries on generating functions introduces ordinary generating functions in one variable and some of their uses and properties, including the relationships generating functions have to closed formulas and recurrence equations. We'll see some basic and not-so-basic generating functions, and using them I'll give an outline of the generatingfunctionansatzcomplexityhierarchaeology. I'll also talk about the important role of generating functions in obtaining information about the asymptotic growth rate of sequences.

Fall 2008 Abstracts

Date:	December 3, 2008
Speaker:	Beth Kupin
Title	Szemeredi's Regularity Lemma
Abstract:	It's often hard to find true independence and/or true randomness arising naturally in a problem. To get around this, we cheat a bit; the Regularity Lemma proves the existence of a decomposition of a large, dense graph into smaller pieces, in which the edges between pieces are evenly distributed (i.e., regular). This means that the edges between these pieces will (more or less) behave as if they were randomly distributed, even though there was nothing random about the choice of the initial graph! I will talk a little bit about the proof of the lemma, but much more about how it is used to prove other results, such as the Erdos-Stone Theorem, or Roth's Theorem about 3-term arithmetic progressions. This will be an introductory talk, so no previous knowledge about extremal graph theory will be assumed.




Date:	November 19, 2008
Speaker:	Phil Matchett Wood
Title:	3-term Arithmetic Progressions in sufficiently dense sets, and the Erdos-Heilbronn Conjecture.
Abstract:	This talk will discuss the maximum density of a subset A of {1,2,3,...n} such that A contains no 3-term arithmetic progression. The first result in this vein was due to Roth in 1953, with subsequent improvements by Heath-Brown in 1987, by Szemeredi in 1990, and by Bourgain in 1999 and 2008. The talk will also discuss a recent application of the density bound on sets containing no 3-term arithmetic progression to the Erdos-Heilbronn Conjecture.




Date:	November 12, 2008
Speaker:	Paul Raff
Title:	Combinatorial Codes and Avoiding Difference Sets
Abstract:	In 1980, Perrin and Schutzenberger gave the so-called Triangle Conjecture on codes, but a counterexample was given by Peter Shor in 1984 and the Triangle Conjecture has been ignored since then. However, there is still a lot of information that is still unknown related to the conjecture, and Shor's counterexample provides motivation for finding large sets whose differences are not part of some prescribed set D. In this talk, I will define the codes, go over the Triangle Conjecture and its counterexample, give results pertaining to avoiding prescribed differences, and talk briefly about future potential work related to Szemeredi-type theorems on arithmetic progressions. This talk is self-contained, and all are encouraged to attend.




Date:	November 5, 2008
Speaker:	Mike Neiman
Title:	Correlation Inequalities
Abstract:	Correlation inequalities examine how probabilistic events positively or negatively reinforce each other. I will give an introduction to some correlation inequalities and applications to random graph models, in particular percolation and the more general random-cluster model. Since this is an introductory talk, I will assume very little previous knowledge.




Date:	October 29, 2008
Speaker:	Emilie Hogan
Title:	The Laurent Phenomenon for Non-Linear Recurrences
Abstract:	Non-linear recurrence relations that produce infinite sequences of integers are very surprising. Often this can be explained by the Laurent Phenomenon, when a non-linear recurrence of order k produces a sequence of Laurent polynomials in the first k terms. Some well known examples of this phenomenon are the Somos-k sequences. Somos-4 is defined by the recurrence: s(n)*s(n-4)=s(n-1)*s(n-3)+s(n-2)2When the first 4 terms are defined to be x1, x2, x3, x4 every term in the sequence is a Laurent polynomial in these 4 variables. I will give sufficient conditions for a non-linear recurrence to follow the Laurent Phenomenon, and show how the Somos-4 sequence satisfies these conditions. This talk will be based on the paper by Sergey Fomin and Andrei Zelevinsky, "The Laurent Phenomenon".




Date:	October 22, 2008
Speaker:	Brian Thompson
Title:	The Zarankiewicz Problem and Other X-tremal "Sports"
Abstract:	Wikipedia defines extreme sports as "activities perceived as having a high level of inherent danger." To protect ourselves against this threat of danger, we will first be equipped with some heavy-duty tools such as the Lov\87sz Local Lemma. Throughout the talk, we will be examining several problems in extremal graph theory; more specifically, we will focus on questions of the form, "What is the largest graph G that avoids H as a subgraph?" For those of you with a competitive spirit, we will see how to extend these into multi-player games of strategy and insight. And for the more introverted types, I will also present some games of "graph theory solitaire".




Date:	October 15, 2008
Speaker:	Kellen Myers
Title:	Ramsey Theory on the Integers & Rado Numbers
Abstract:	Ramsey theory is the study of the structure within a set, and whether such structure is preserved under (finite) partitions (thought of as "colorings"). A coloring with r colors is called an r-coloring. A structure preserved under colorings is called regular (or r-regular for only r-colorings). In any such problem, we can also ask what the minimal such n is (for fixed r and m), a question that is often bounded theoretically and/or computed via computer. Schur's theorem tells us that solutions to the equation x+y=z are regular. In this talk, we will consider the generalization of Schur's theorem to linear equations, done by Richard Rado, and other results (both "existence" and bounding/computational) pertaining to linear equations - of which some solution sets are regular and some are only 2-regular.




Date:	October 8, 2008
Speaker:	Jeffrey Amos
Title:	The Multi-dimensional Chicken McNugget problem
Abstract:	Millions of American have no doubt asked themselves this question: if I can only buy multiples of 6, 9, and 20 chicken McNuggets, what is that largest number of McNuggets that I can't buy? Mathematicians with a precise grasp on their level of hunger have pondered this riddle for over a century \D0 even since before McDonald's. I will be considering a generalization of this problem. Given a set of integer vectors, what is the largest vector that cannot be written as a sum of a sequence of the given vectors? I will be presenting results concerning what "largest vector" should mean, when it exists, and several 1-dimensional results that generalize into n-dimensions.




Date:	October 1, 2008
Speaker:	Eric Rowland
Title:	Pattern Avoidance in Binary Trees
Abstract:	Let T and t be binary trees. We say that T avoids the pattern t if T does not contain t as a (contiguous) subtree. A natural thing to do with a notion of 'pattern' is, of course, to count the objects (in this case n-leaf binary trees) that avoid a given pattern. We'll start by working out for small tree patterns the generating function that answers this question. Then we will consider the analogue of Wilf equivalence: Two tree patterns are equivalent if the trees that avoid them areequinumerous, i.e., they have the same generating function. It is not straightforward to understand these equivalence classes. However, I'll describe a method of restructuring trees that often lets us prove (bijectively) the equivalence of two equivalent tree patterns.




Date:	September 24, 2008
Speaker:	Andrew Baxter
Title:	Generalized Permutation Patterns and Mahonian Statistics
Abstract:	In their 2000 article, Babson and Steingrimsson introduce the concept of the generalized permutation pattern. These are meant to serve as atomic permutation statistics which can be combined to form more interesting permutation statistics such the major index MAJ or the number of inversions INV. In this talk I will introduce these generalized patterns (although Arvind metioned one in his talk) and how Babson and Steingrimsson used them to find previously-unknown Mahonian statistics, that is those statistics which have the same distribution over the symmetric group as INV. I will then discuss my own research in tying up some loose ends which Babson and Steingrimsson left behind.




Date:	September 17, 2008
Speaker:	Dan Cranston (DIMACS)
Title:	Injective Coloring of Sparse Graphs
Abstract:	An injective coloring is a vertex coloring such that every two vertices with a common neighbor receive distinct colors; it need not be a proper coloring. The injective chromatic number of G, denoted χi(G), is the least k such that G has an injective coloring with k colors. The discharging method is a bookkeeping technique for induction proofs on graphs. Specifically, we use discharging when we have a variety of different induction steps possible, no single one of which is always applicaple; the key is to prove that in all cases one of the induction steps is applicable. The goal of this talk is to introduce the discharging method, and we do so by proving two theorems about Injective Coloring. Let mad(G) denote the maximum average degree (over all subgraphs) of G. We prove that if the maximum degree is 3 and mad(G) < 5/2, then χi(G) ≤ 4. Similary, if the maximum degree is 3 and mad(G) < 36/13, then χi(G) ≤ 5. No background is assumed. This talk should be accessible to all grad students (even CS people ;).




Date:	September 10, 2008
Speaker:	Arvind Ayyer
Title:	Exclusion Processes: A Meeting Point for Probabilists, Combinatorialists and Statistical Mechanicians
Abstract:	An exclusion process is a Markov process defined on the integer lattice, or its subset, in which each site is either occupied by a particle or is empty. Motivated by statistical mechanical considerations, Derrida et al. considered a particular finite model and gave a formula for its steady state probability distribution using the so-called "matrix product ansatz". Taking this as the starting point, I will go through the literature and survey some interesting models studied by the three groups and end by describing an exclusion process with two kinds of particles which is joint work with Joel Lebowitz and Eugene Speer.