We revisit the Bose-Mesner algebra of the perfect matching association scheme (aka the Hecke algebra of the Gelfand pair (S_2n, H_n), where H_n is the hyperoctahedral group). Our main results are: (1) An algorithm to compute the eigenvalues from symmetric group characters by solving linear equations. (2) Universal formulas, as content evaluations of symmetric functions, for the eigenvalues of fixed orbitals (generalizing a result of Diaconis and Holmes). (3) An inductive construction of the eigenvectors (generalizing a result of Godsil and Meagher).

We revisit the Bose-Mesner algebra of the perfect matching association scheme (aka the Hecke algebra of the Gelfand pair (S_2n, H_n), where H_n is the hyperoctahedral group). Our main results are: (1) An algorithm to compute the eigenvalues from symmetric group characters by solving linear equations. (2) Universal formulas, as content evaluations of symmetric functions, for the eigenvalues of fixed orbitals (generalizing a result of Diaconis and Holmes). (3) An inductive construction of the eigenvectors (generalizing a result of Godsil and Meagher).

The conjecture of Erdos-Heilbronn (1964) states the following: Suppose G is a a finite group and and we have a G-sequence (g_1,g_2,...,g_l) of pairwise distinct g_i where l>2|G|^{1/2}, there is a subsequence (g_{i_1},g_{i_2},..,g_{i_t}) (for some t) such that \prod_{j} g_{i_j} = 1. The conjecture is open in its fullness, but has been settled (up to a constant) in some special cases of groups. We will see the proof of the E-H conjecture for cyclic groups, by Szemeredi.

Let A be a finite subset of a field F. Define A+A and AA to be the set of pairwise sums and products of elements of A, respectively. We will see a theorem of Bourgain, Katz and Tao that shows that if neither A+A nor AA is much bigger than A, then A must be (in some well-defined sense) close to a subfield of F.

We show that in a finite group G of bouded torsion, any set A \subseteq G such that |A + A| = O(|A|) generates a subgroup H of size O(|A|). We will introduce some standard techniques in additive combinatorics to prove this theorem.

Given a finite set of points P in R^2 and a finite family of lines L in R^2, an incidence is a pair (p,l), where p\in P, l\in L and p is a point in l. The Szemeredi-Trotter Theorem states that the number of incidences is atmost a constant multiple of (|L||P|)^{2/3} + |L| + |P|. We give a proof by Tao, which uses the method of cell partitions.

Given a finite set of points P in R^2 and a finite family of lines L in R^2, an incidence is a pair (p,l), where p\in P, l\in L and p is a point in l. The Szemeredi-Trotter Theorem states that the number of incidences is atmost a constant multiple of (|L||P|)^{2/3} + |L| + |P|. We give a proof by Tao, which uses the method of cell partitions.

The classical task of compression, made famous by the works of Shannon and Huffman, asks the question: Given a distribution on possible messages, how can one build a dictionary to represent the messages so as to (approximately) minimize the expected length of the representation of a random message sampled from this distribution. Given the centrality of compression as a goal in all, natural or designed, communication, we introduce and study the uncertain compression problem. Here the goal is to design a compression scheme that associates a dictionary to each distribution such that messages can be recovered even by receivers that do not know the distribution exactly, but only know them approximately. Understanding the limits of uncertain compression leads to intriguing challenges and in particular leads to the challenge of understanding the chromatic number of an explicit family of graphs. In this talk we will describe some of the graphs, and attempts to bound their chromatic number. Based on joint works with Badih Ghazi, Elad Haramaty, Brendan Juba, Adam Kalai, Pritish Kamath and Sanjeev Khanna.

The Steiner diversity is a type of multi-way metric measuring the size of a Steiner tree between vertices of a graph and it generalizes the geodetic distance. The Steiner Wiener index is the sum of all Steiner diversities in a graph and it generalizes the Wiener index. Recently the Steiner Wiener index has found an interesting application in chemical graph theory as a molecular structure descriptor composed of increments representing interactions between sets of atoms, based on the concept of the Steiner diversity. Amon other results a formula based on a vertex contributions of the Steiner Wiener index by a newly introduced Steiner betweenness centrality, which measures the number of Steiner trees that include a particular vertex as a non-terminal vertex, will be presented. This generalizes Krekovski and Gutman's Vertex version of the Wiener Theorem and a result of Gago on the average betweenness centrality and the average distance in general graphs.

We will discuss results given by Csikvari who proved that certain graph parameters have their extreme points at the star and at the path among the trees on a fixed number of vertices. He gave many applications of the so-called generalized tree shift which induces a partially ordered set on trees having fixed number of vertices. He proved that certain graph parameters (Wiener-index, Estada index, the number of closed walks of a fixed length, largest eigenvalue of the adjacency matrix A and Laplacian matrix L, coefficients of independence polynomial, coefficients of the edge cover polynomial, coefficients of the characteristic polynomials of A and L in absolute value) increase or decrease along this poset of trees