Here is a brief history of the seminar, as relayed by Tom Robinson:
I think Stephen Hartke began it... His advisor was Fred Roberts, and as far as I know DIMACS always provided the funding. After Stephen, I think Nick Weininger took over and then Bill Cuckler and then Paul Raff and then me (with Mike Neimann's help) then Beth and now [Kellen]. Subway sandwiches have been the most usual food, but there've been lots of exceptions by now.
Here is another account, as relayed by Paul Raff:
To my recollection, Bill Cuckler ... he's at the NSA now ... organized it before me and Phil did, and Nick did before Bill ... I think the GCS is just a natural consequence of the awesomeness of the discrete math program at Rutgers.
This website supports linking to individual talk descriptions. To link to a specific talk, add #yyyymmdd to the end of this URL, where yyyymmdd is the date of the talk in the format (4 digit year)(2 digit month)(2 digit day). For example, to link to a (nonexistent) talk on July 3, 2014, you would visit .../GCSArchive.html#20140703. (The period after that URL is a period at the end of a sentence; it is not part of the URL.)
| Date: | Wednesday, March 30 |
|---|---|
| Speaker: | George Spahn |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | How many ways can you solve a Ring-Ring puzzle starting from an empty grid? |
| Abstract: | Ring-Ring is a pencil and paper logic puzzle. In addition to solving puzzles together, we will see how to count possible solutions using finite state machines (and linear algebra). |
| Date: | Wednesday, March 23 |
|---|---|
| Speaker: | Hannah Hasan |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | Oh My God They Were Roommates: Achieving Envy-Free Rent Division |
| Abstract: | Given a 3-bedroom apartment, is it possible to find a rent distribution so that all 3 roommates get their first-choice room? This problem can be solved by coloring triangles and using a proof from "The Book." If you know what triangles and colors are, you are well equipped for this talk! |
| Date: | Wednesday, March 9 |
|---|---|
| Speaker: | Kayla Gibson |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | A talk on the Diameters of Commuting Graphs of Matrix Rings |
| Abstract: | A commuting graph of a ring is a graph whose vertices are non-central elements of the ring. 2 distinct vertices x and y are said to be adjacent if and only if xy=yx in the ring. I will be discussing the commuting graph of the ring of matrices. We can say some interesting things about the size of the diameter of this graph (when it is connected). I will go through some examples to become comfortable working with these structures. Then I will go over some interesting proofs and results in this field as well as discussing some open problems in the area. This talk will rely pretty heavily on linear algebra. |
| Date: | Wednesday, March 2 |
|---|---|
| Speaker: | Brian Pinsky |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | Combinatorics so easy my undergrads can do it |
| Abstract: | In this well prepared talk about material specifically chosen for a GCS audience, I will cover results that I could (hypothetically) have covered with my 461 students. These include various applications of Konig's lemma/compactness (tools for generalizing finite results to infinite ones). I'll even define a couple things you may not have heard of, like unfriendly graph colorings and the paris harrington theorem. |
| Date: | Wednesday, February 23 |
|---|---|
| Speaker: | Ishaan Shah |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | The Chromatic Symmetric Function of Trees |
| Abstract: | There's a function not unlike the ordinary chromatic function which is defined via colorings of a graph. But this function, defined as a polynomial in countably many variables, has other interpretations as well and hides many other invariants of a graph in its coefficients. It is conjectured to be a complete invariant for trees, and this talk will explore that. |
| Date: | Wednesday, February 16 |
|---|---|
| Speaker: | Quentin Dubroff |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | Cancellative families |
| Abstract: | A family of subsets is cancellative if A U B = A U C implies B = C for any A,B,C in the family. Frankl and Furedi proved an upper bound on the size of cancellative families using a very short probabilistic argument. Surprisingly, this upper bound is essentially exact, and the example is another quick(ish) application of the probabilistic method. After presenting these two nice results, I'll mention some related questions which remain unsolved. |
| Date: | Wednesday, February 9 |
|---|---|
| Speaker: | Charles Kenney |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | List Lengths and Color Degrees |
| Abstract: | Graph coloring is a central topic in combinatorics with many applications, from cartographers' paints to chemists' refrigerators. An instance of a list coloring problem inputs a graph G=(V,E) together with sets S(v) of 'colors' for each v in V. One is asked to produce a coloring function s on V with the properties that s(v) is in S(v) for every v in V, and for each w adjacent to v, s(w) is not equal to s(v). In this talk I discuss an interesting family of conditions on the lists S(v) which guarantee the existence of a coloring. Based primarily on Asymptotically the List Colouring Constants are 1 by Bruce Reed and Benny Sudakov. |
| Date: | Wednesday, February 2 |
|---|---|
| Speaker: | Natasha Ter-Saakov |
| Time: | 12:15PM |
| Place: | Hill Center for Mathematical Sciences, Graduate Lounge (7th Floor) and Zoom |
| Title: | Packing and Covering Triangles in Graphs |
| Abstract: | If we let v(G) be the maximal cardinality of a set of pairwise disjoint triangles in G, and t(G) be the minimal cardinality of an edge cover with an edge in each triangle, Tuza conjectured that v(G) \leq t(G) for all graphs G. In this talk, we will discuss progress made on this conjecture for different families of graphs. |
| 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. |
| 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
|
| 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. |
| 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. |
| 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. |
| 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/ |
| 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. |
| 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:
|
| 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. |
| 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. |
| 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\F6bius 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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! |
| 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. |
| 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. |
| 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. |
| 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). |
| 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. |
| 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. |
| 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?) |
| 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. |
| 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. |
| 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. |