
Discrete Mathematics SeminarTuesdays 10:0010:50 (Room SH203 for D Term)Worcester Polytechnic Institute

D TERM 2019
 Tuesdays 10:0010:50am, in Room 203 Stratton Hall
 12 March: Jordan Tirrell, Mount Holyoke "Lucas analogues of combinatorial formulas"
Abstract: The Lucas sequence is a sequence of polynomials whose specializations include the Fibonacci numbers, the nonnegative integers, and the qintegers. Given a quantity which is expressed in terms of products and quotients of nonnegative integers, one obtains a Lucas analogue by replacing each factor in the expression with the corresponding term in the Lucas sequence. It is then natural to ask if the resulting rational function is actually a polynomial and, if so, what it counts. We will discuss some recent work, open problems, and future plans. This is joint work with Bruce Sagan. This talk should be accessible for undergraduates.
 19 March: No seminar. Kodalen thesis defense at noon in the Taylor Room in WPI's Campus Center
 26 March: Rosemary Bailey, St Andrews "Latin squares: Some history, with an emphasis on their use in designed experiments"
Abstract: In the 1920s, R. A. Fisher recommended Latin squares for crop experiments. However, there is evidence of their much earlier use in experiments.They have led to interesting special cases, arguments, counterintuitive results, and a spectacular solution to an old problem.
 2 April: Ashley Wheeler, Mount Holyoke "Posets and algebras with straightening law"
Abstract: The Pluecker relations are syzygies in the homogeneous coordinate ring for the Grassmann variety. In particular, they are equations satisfied by the columns of a matrix. They also impose a "straightening law", meaning they allow one to express any polynomial in the ring in a socalled standard form. The straightening law relies on a partial ordering on determinants, which can be encoded as Young tableaux. I am interested in how the straightening law is affected when we change the partial ordering.
 9 April: Bill Martin, WPI "Maximumsized cliques and cocliques in strongly regular graphs"
Abstract: A clique in a graph G is a subset C of the vertex set V(G) in which any two elements are adjacent; so C induces a complete subgraph of G. A coclique (also called an "independent set" or "stable set" in G) is just a clique in the complement graph. While it is, in general, NPhard to find the largest size of a clique or coclique in an arbitrary graph, the task is often easier when we are restricted to the family of strongly regular graphs. A graph G is kregular (or regular of valency k) if every vertex has exactly k neighbors. A strongly regular graph is a regular graph whose adjacency matrix has exactly three distinct eigenvalues.Let G be a strongly regular graph of valency k whose adjacency matrix A has smallest eigenvalue s. Delsarte proved that, for any clique C in G, we have C ≤ 1  k/s. Cliques attaining this bound have very nice structure. In this talk, we will prove the bound, introduce some families of strongly regular graphs and, where we can, give a full description of all cliques attaining the Delsarte bound. Much of the discussion is related to fintie geometry. For example, if G is the collinearity graph of a finite generalized quadrangle, then the cliques of the graph which attain the bound are simply the lines of the geometry and the cocliques attaining the corresponding bound for the complement are the ovoids: maximumsized sets of points such that no two are collinear.
 16 April: Brian Kodalen, WPI "Orthogonal projective double covers"
Abstract: Given a regular graph G, a projective double cover is a representation of the vertices of G as a set of lines in ℝ^{m} for some dimension m ≤ V(G) where the angle between two lines depends only on whether or not the corresponding vertices are adjacent in G. An orthogonal projective double cover of G is a projective double cover where one of the angles, namely the angle corresponding to nonadjacency, is 90°. In restricted cases, a projective double (with both angles less than 90°) corresponds to a 5class Qbipartite association scheme while an orthogonal projective double (OPD) gives a 4class Qbipartite association scheme. In this talk, we introduce these concepts and show that an OPD exists for every simple graph. We then examine the conditions required in order to produce 4class Qbipartite association schemes from an OPD  noting the extra conditions this imposes on the underlying graph. Finally, we rule out Hamming graphs as quotients of 4class Qbipartite association schemes using the combinatorial techniques developed here.
 23 April: Dan Dougherty, WPI "A Coq formalization of Boolean unification"
Abstract: We report on a verified implementation of two (wellknown) algorithms for unification modulo the theory of Boolean rings: Lowenheim's method and the method of Successive Variable Elimination. The implementations and proofs of correctness were done in the Coq proof assistant; we view this contribution as an early step in a larger project of developing a suite of verified implementations of equational unification algorithms.
 30 April: Phillip Heikoop, WPI "Dimensions of semisimple matrix algebras"
Abstract: The set of dimensions of semisimple subalgebras of the full matrix algebra M_{n}(k) can be easily described but is difficult to compute in general. We show that the problem can be reduced to a question on the partitioning of integers by squares and use this fact to bound the size of the dimension set. Notably, we demonstrate that the dimension set is dense in the naturals.
C TERM 2019
 Wednesdays 11:0011:50am, in Room 203 Stratton Hall
 9 January: No seminar (WPI first day of classes)
 16 January: Bill Martin, WPI "Discrete Geometry  The Greatest Hits CD"
Abstract: In the last 510, or (in some cases) 25 years, there have been remarkable breakthroughs in discrete geometry and I thought it would be nice to survey these recent results. (For instance, problems posed by Kepler and Kelvin have seen recent progress.) Without digging into details of any one topic, I intend to discuss exciting news related to sphere packings, kissing numbers, equiangular lines, spherical 2distance sets, the Erdos distinct distances problem and the chromatic number of the plane. This talk should be accessible to sharp undergraduate students and might be interesting to anyone in the Mathematical Sciences.
 23 January: Gabor Lippner, Northeastern University "Quantum state transfer on graphs  using magnetic fields"
Abstract: Transmitting quantum information losslessly through a network of particles is an important problem in quantum computing. Mathematically this amounts to studying solutions of the discrete Schrödinger equation
d/dt φ = i H φ
where H is typically the adjacency or Laplace matrix of the graph. This in turn leads to questions about subtle numbertheoretic behavior of the eigenvalues of H.It has proven to be difficult to find graphs which support such information transfer. I will talk about recent progress in understanding what happens when one is allowed to apply magnetic fields (that is, adding a diagonal matrix to H) to the system of particles.
 30 January: Padraig Ó Catháin, WPI "Automorphisms of Symmetric groups"
Abstract: The automorphisms of the symmetric groups were classified in the nineteenth century by Sylvester and Hoelder. Apart from an exceptional outer automorphism at n = 6, it turns all automorphisms can be described by relabelling of the underlying point set  these are inner automorphisms. In this talk, I will describe a new construction of the outer automorphism of S_{6} using a complex Hadamard matrix and the algebra of splitquaternions. This is joint work with Cheryl Praeger and Neil Gillespie (who is visiting WPI in February!)
 6 February: Padraig Ó Catháin, WPI "Automorphisms of Symmetric groups" (continued)
Abstract: see above
 12 February 3:00 pm in SH203: (POSTPONED due to weather) Jordan Tirrell, Mount Holyoke "Lucas analogues of combinatorial formulas"
Abstract: The Lucas sequence is a sequence of polynomials whose specializations include the Fibonacci numbers, the nonnegative integers, and the qintegers. Given a quantity which is expressed in terms of products and quotients of nonnegative integers, one obtains a Lucas analogue by replacing each factor in the expression with the corresponding term in the Lucas sequence. It is then natural to ask if the resulting rational function is actually a polynomial and, if so, what it counts. We will discuss some recent work, open problems, and future plans. This is joint work with Bruce Sagan. This talk should be accessible for undergraduates.
 20 February: John Pugmire, WPI "Blowing up CMatrices"
Abstract: TBA Cmatrices, also known as conference matrices, are matrices satisfying the equation CC^{T}=(n1)I_{n} which are 0 on the main diagonal and +/1 elsewhere. The existence (or nonexistence) of Cmatrices has only been shown for certain orders n and is closely related to the Hadamard conjecture. One notable construction is due to Turyn's 1971 paper, On CMatrices of Arbitrary Powers, which provides a technique for blowing up a Cmatrix of order n into a new one of order n^{m} for arbitrary natural numbers m. To this end, Turyn introduces combinatorial objects called Gstrings, which have many interesting properties. We present simplified, more explicit proofs of Turyn's results, including new intermediate results on the properties of Gstrings.
 26 February (TUESDAY! in SH202): Neil Gillespie, University of Bristol "Equiangular lines in Euclidean space and Incoherent sets"
Abstract: The problem of finding the maximum number of equiangular lines in ddimensional Euclidean space has been studied extensively over the past 80 years, in part because it is a fundamental problem in discrete geometry, but also because of its applications in signal processing, communications and coding theory. The absolute upper bound on the number of equiangular lines that can be found ℝ^{d} is d(d+1)/2. However, examples of sets of lines that saturate this bound are only known to exist in dimensions d=2,3,7 or 23, and it is an open question whether this bound is achieved in any other dimension. By considering the additional property of incoherence, we prove that there exists a set of equiangular lines that saturates the absolute bound and the incoherence bound if and only if d=2,3,7 or 23.For a given angle κ, there exists a relative upper bound on the number of equiangular lines in ℝ^{d} with common angle κ. We show that classifying sets of lines that saturate this bound along with the incoherence bound is equivalent to classifying certain quasisymmetric designs, which are combinatorial designs with two block intersection numbers. We will also show how such sets of lines are related to the integer points of an elliptic surface.
Interestingly, given a further natural assumption, we can classify the known sets of lines that saturate the relative and incoherence bounds. This family comprises of the known sets of lines that saturate the absolute bound along with the the maximal set of 16 equiangular lines found in ℝ^{6}. There are infinitely many known sets of lines that saturate the relative bound, so this result is surprising. To understand these sets of lines further, we identify the E_{8} lattice with the projection onto an 8dimensional subspace of a sublattice of the Leech lattice defined by 276 equiangular lines in ℝ^{23}. This allows us to identify many of the maximal sets of of equiangular lines in small dimensions with subsets of the 276 equiangular lines in ℝ^{23}.
 27 February: Guillermo Carlo Nuñez, WPI "Entropic Uncertainty Relations for single POVMs"
Abstract: Uncertainty relations are a useful tool to prove the security of quantum cryptographic protocols. Motivated by the RRDPS (RoundRobin Differential Phase Shift) encoding we consider the study of uncertainty relations for a single measurement. We obtain a first general uncertainty bound for the Renyi entropy, which turns out to be sharp for a family of POVMs (Positive Operator Valued Measures). This work was part of my master's thesis under the supervision of Serge Fehr (CWI).
B TERM 2018
A TERM 2018
 Tuesdays 3:003:50pm, in Room 203 Stratton Hall
 23 October: Peter Christopher, WPI "Minimal graphs with a given automorphism group"
Abstract: Forthcoming.
 Thursday, 25 October: The Northeast Combinatorics Network presents a Virtual Combinatorics Colloquium at 3:00pm on Thursday October 25th. Vasek Chvátal, Concordia University (emeritus) will speak on the ChenChvátal Conjecture. His title is "Points and lines".
 30 October: Bill Martin "Delsarte's linear programming bound and extensions"
Abstract: This talk will introduce linear programming tools for errorcorrecting codes, various types of designs, and spherical codes. My goal is to give a complete treatment for the binary Hamming scheme and then to outline the analogous approach for symmetric association schemes and the sphere. I will finish by mentioning semidefinite programming and the kissing number problem that will arise in Friday's Conant Lecture.
 Friday, 2 November: WPI's 2018 Conant Lecture will be given by Henry Cohn, Microsoft Research New England and MIT. More information can be found on WPI's website. The title of Henry's lecture is "A conceptual breakthrough in sphere packing".
 6 November: Sheila Sundaram, Pierrepont School, Westport, CT "On conjugacy classes of S_{n} containing all irreducibles "
Abstract: The action of S_{n} on itself by conjugation is a permutation representation whose orbits are the conjugacy classes. It is known that this action contains all the irreducible S_{n}modules; several proofs of this fact appear in the literature. Here we establish the fact that there are single classes which contain all the irreducibles, and give a simple characterisation of the orbits containing ALL the irreducibles of S_{n}. The precise result is the following:If n ≠ 4,8, the conjugacy class indexed by the integer partition λ of n contains all S_{n}irreducibles if and only if λ has all parts distinct and odd, and has at least two parts.
 13 November: Gábor Sárközy, WPI "Rainbow matchings (or transversals in Latin squares)"
Abstract: Rainbow matchings (or equivalently transversals in Latin squares) have received a lot of attention. We'll mention some conjectures and results. In particular, we'll prove the following result. If a bipartite multigraph G is the union of (2n1) matchings of size n, then G contains a rainbow matching (where each edge comes from a different matching) of size n. Alon observed, that this immediately implies the classical ErdosGinzburgZiv theorem in number theory.
Joint work with J. Barat and A. Gyarfas
 20 November: No seminar Thanksgiving Break
 27 November: Bill Martin, WPI "The story of (T,M,S)nets"
Abstract: QuasiMonte Carlo methods are used for numerical integration, simulation, and optimization. In contrast to the true Monte Carlo approach, where points are chosen at random, a quasiMonte Carlo method employs deterministic point sets which are distributed ``uniformly'' with respect to some prespecified statistics. These requirements often have combinatorial meaning. Such is the case with (T,M,S)nets.This talk focuses on the combinatorics and how I got involved in the subject. Beginning with the definition and small examples, we review the SchmidLawrence Theorem which connects (T,M,S)nets to orthogonal arrays and errorcorrecting codes. In the 1990s, a puzzle arose as to whether these strange codes have meaningful duals. Doug Stinson and I answered this question and, bringing in the theory of association schemes, introduced the linear programming bound for (T,M,S)nets, which proved to be quite powerful. The story involves an interesting assortment of researchers in a wonderful mix of geographic locations. So the slides emphasize this social aspect of the tale.
 4 December: Bill Martin, WPI "Strongly regular graphs"
Abstract: This talk will be an introduction to strongly regular graphs and a review of the known infinite families of such graphs. A graph G is strongly regular with parameters v, k, λ and μ (and we write G ∈ srg(v, k, λ , μ) or something less formal) ifThe class of strongly regular graphs is connected to many interesting objects such as Steiner triple systems, generalized quadrangles, projective twoweight codes, quasisymmetric designs, and systems of equiangular lines. This talk will survey a few of these connections and derive expressions for the four fundamental parameters of G, mentioned above, in terms of the eigenvalues of the graph.
 G is regular of valency k
 every pair of adjacent vertices in G have λ common neighbors
 every pair of nonadjacent vertices in G have μ common neighbors.
 11 December: No seminar, Reading Day
 Tuesdays 2:002:50pm, in Room 106 Stratton Hall
 28 August: Bill Martin, WPI "What can you say about a graph from its degree sequence?"
Abstract: Dirac proved that every graph on n vertices with all vertex degrees d_{i} ≥ n/2 has a Hamilton cycle. In 1972, Chvátal improved this as follows: if the vertex degrees d_{i} are ordered so that d_{1} ≤ d_{2} ≤ . . . ≤ d_{n} and, for i up to (n1)/2, we have d_{i} ≤ i ⇒ d_{ni} ≥ ni, then the graph is Hamiltonian. I've read some really interesting theorems about such things and will talk about degree sequence hypotheses that guarantee desired graph properties. The talk should be accessible to undergraduates.
 4 September: Eric Swartz, William and Mary "Reachable pairs in digraphs and zero pattern matrix rings"
Abstract: Given distinct vertices u and v in a directed graph (digraph) Γ, we say that the ordered pair (u,v) is a reachable pair if there exists a path of directed edges from u to v. If the digraph Γ has n vertices, what are the possibilities for the total number of reachable pairs in Γ? This problem, along with its connection to zero pattern matrix rings, will be discussed. This is joint work with Nicholas Werner, and this talk should be accessible to undergraduates.
 11 September: Cristina Ballantine, Holy Cross "Partitions decorated with bit strings"
Abstract: Euler's famous partitions identity states that the number of partitions of n into distinct parts equals the number of partitions of n into odd parts. What happens if we relax the conditions in this identity? Let a(n) be the number of partitions of n such that the set of even parts has exactly one element and let and c(n) be the number of partitions of n in which exactly one part is repeated. Moreover, let b(n) be the difference between the number of parts in all odd partitions of n and the number of parts in all distinct partitions of n. Beck conjectured that a(n)=b(n) and Andrews, using generating functions, proved that a(n)=b(n)=c(n). Using partitions decorated with bit strings, we give a combinatorial proof of Andrews' result. If time permits, I will introduce some Watson type identities whose combinatorial proofs also use partitions decorated with bit strings.
 18 September: Padraig Ó Catháin, WPI "Characteristic Polynomials of Hadamard matrices and incidence matrices"
Abstract: While a fixed graph may have many different adjacency matrices, we can speak without ambiguity of the characteristic polynomial of that graph. This is because reordering the vertices of a graph induces the same permutation on the rows and columns of the adjacency matrix, so that all adjacency matrices for a fixed graph are similar. For many other classes of combinatorical structures (e.g. projective planes or Hadamard matrices) we do not insist that all incidence matrices are similar. So an equivalence class of Hadamard matrices is associated with many different characteristic polynomials. In this talk, I will discuss some recent work with Ronan Egan and Eric Swartz in which we developed some techniques for constructing Hadamard matrices with irreducible minimal polynomials, and some applications of our result.
 25 September: Bill Martin, WPI "Some remarks on list coloring"
Abstract: I will survey a few results about graph list coloring. Graph coloring is a rich area of research and many intriguing open problems remain. In this variation, each vertex is provided a "list" of colors allowable at that vertex and one asks, for a given graph and a given collection of color lists at its vertices, whether or not a proper coloring can be found in which each vertex chooses its color from its own list.Surprises include the fact that, for every positive integer k, there exists a bipartite graph and an assignment of lists each of size k with respect to which no proper listcoloring exists. All is not lost, though, as Carsten Thomassen proved in 1994 that every planar graph admits a proper listcoloring provided each list has size five or more.
While I will try to survey a few of these results, I will focus on two of my papers. The first, written with Jeff Dinitz, pursues an algebraic approach of Alon and Tarsi, especially in the case of uniquely listcolorable graphs. The second is a recent nonrefereed paper describing an example discovered by the late Fields Medalist Maryam Mirzakhani when she was very young. The talk should be mostly accessible to undergraduates.
 2 October: Alex Nowak, Iowa State "Representation theory for certain combinatorial designs"
Abstract: In combinatorial design theory, Mendelsohn triple systems (sometimes referred to as cyclic triple systems) generalize Steiner triple systems, and in universal algebra, quasigroups are the socalled nonassociative groups. Mendelsohn triple systems may be realized as idempotent, semisymmetric quasigroups, which are quasigroups satisfying the identities x^{2} = x and y(xy) = x. Exploiting this universal algebraic description, I will present a theory of modules over Mendelsohn triple systems. As in the group case, the module theory for these nonassociative algebras prompts questions regarding extension. I will address some of these extension problems, and if time permits, I will also discuss the interplay between representations of Steiner and Mendelsohn triple systems.
 9 October: Joseph Fehribach, WPI "Uniformity in Kirchhoff Graphs"
Abstract: One of the first things that might be noticed about Kirchhoff graphs is that in many but not all cases, the number of times each edge vector of occurs in the graph is constant. This talk will discuss this issue in some detail. First a linear algebraic formulation of Kirchhoff will be derived, and then this formulation will be used to show that 2connected Kirchhoff graphs are always uniform  each edge vector occurs a fixed number of times.
D TERM 2018
C TERM 2018
 Mondays 3:003:50pm, in Room 106 Stratton Hall
 19 March: No seminar (please consider attending Tyler Reese's thesis defense at 2pm instead)
 26 March: Bill Martin, WPI "Scaffolds: A graphbased system for computations with certain tensors"
Abstract: Startriangle diagrams are a useful but poorly understood tool in the theory of association schemes. Similar ideas have been used to rule out distanceregular graphs using different language. Meanwhile the same object is encoded in the partition function of link diagrams in the development of spin models. This talk is an attempt to unify those results. Let X be a nonempty finite set and let A be a vector subspace of Mat_{X}(C) where C is the field of complex numbers. Consider a digraph G=(V(G),E(G)) with edge weight function w : E(G) → A and a set R ⊆ V(G) of distinguished ("red") nodes. For R=m, the scaffold S(G,R,w) is then defined as a certain m^{th} order tensor over the space of complexvalued functions on X. For example, when m=0 the scalar S(G,R,w) is the sum over all functions φ :V(G) → X of the product, over all e ∈ E(G), of the (a,b)entry of w(e) where e=(a,b).A scaffold with a single red dot and a loop labelled M is the diagonal of M while the same scaffold with a hollow dot is the trace of M. If A is the adjacency matrix of a simple graph Γ, the scaffold formed by a triangle with all edge weights equal to A and two red nodes records, for each pair of adjacent vertices in Γ, their number of common neighbors.
The aim of this talk is to outline a basic theory of scaffolds mainly in the case where A is the BoseMesner algebra of some association scheme. After briefly touching on graph limits and spin models (invariants of knots and links) we will discuss triple intersection numbers for distanceregular graphs and one structure theorem for Qpolynomial association schemes.
 2 April: Ronan Egan, Rijeka Croatia "Selforthogonal codes via orbit matrices"
Abstract: We introduce orbit matrices of integer matrices, and of matrices with entries in a finite field. Matrices with suitable orthogonality properties such as weighing matrices and Hadamard matrices often generate selforthogonal and Hermitian selforthogonal linear codes over some finite fields. Consequentially, under certain conditions, their orbit matrices generate selforthogonal and Hermitian selforthogonal codes. Laplacian and Seidel matrices of strongly regular graphs have similar properties that allow us to apply similar techniques. We demonstrate by constructing orbit matrices for various families of combinatorial structures, many of which yield selforthogonal codes with good errorcorrecting properties. (This is joint work with Dean Crnković and Andrea Švob.)
 9 April: Cristina Ballantine "Quasisymmetric power sums"
Abstract: The ring of symmetric functions Sym has two important generalizations: the ring QSym of quasisymmetric functions, and the ring NSym of noncommutative symmetric functions. Most wellknown bases of Sym generalize nicely to bases of QSym and NSym. More, a duality between QSym and NSym as Hopf algebras interconnects their structure in powerful ways, lifting the traditional Hall inner product on Sym. We explore analogues to the symmetric power sum bases in QSym. With respect to the pairing on Sym, the power sum basis is (up to a constant) selfdual, a relationship expected to hold between analogues in QSym and NSym. Two types of noncommutative power sum bases were already defined by Gelfand, et. al. The quasisymmetric duals to the noncommutative power sums have briefly appeared in the literature but very little has been said about their structure or their relationship to other bases. We define two types of quasisymmetric power sum bases as scaled duals to the noncommutative power sums. We give combinatorial interpretations of their coefficients, and use those to show that they both refine the symmetric power sums. If time permits, I will also discuss transition matrices to other wellunderstood bases and explicit formulas for products of quasisymmetric power sums. (This is joint work with Z. Daugherty, A. Hicks, S. Mason, E. Niese.)
 16 April: No Seminar (Patriot's Day)
Abstract: TBA
 23 April: Padraig Ó Catháin, WPI "Binary correlation amplifiers"
Abstract: Suppose that X, Y are sets of vectors of length n with entries 1,1 each of size N. Suppose further that there are a small number of pairs x ∈ X and y ∈ Y which are highly correlated; while all other pairs of vectors are weakly correlated. In 2015 G. Valiant presented a novel subquadratic time (in N) algorithm for solving the Outlier Detection Problem under certain hypotheses. In this talk, I will give a precise description of the Outlier Detection Problem, of Valiant's algorithm, and an overview of a derandomised algorithm for the same problem which also has subquadratic running time. Our derandomisation uses a family of expander graphs. This is joint work with Petteri Kaski, Matti Karppa and Jukka Kohonen at Aalto University, Finland.
 30 April: Randy Paffenroth, WPI "The Restricted Isometry Property and BoseMesner Algebras"
Abstract: Compressed sensing has a role to play in many fields, including signal processing, image processing, and machine learning. Appropriate sensing matrices with the Restricted Isometry Property play a pivotal role in the theory underlying such methods. However, at the current time, there are no known deterministic constructions of sensing matrices that match the performance of randomized constructions. In this talk, we will explore such deterministic constructions, discuss some of the difficulties that arise, and show connections to several other branches of mathematics including graph theory and BoseMesner Algebras.
 Thursdays 10:0010:50am, in Room 203 Stratton Hall
 11 January: Brian Kodalen, WPI "Linked simplices"
Abstract: Let X and Y be sets of unit vectors corresponding to regular simplices in R^{v} (v+1 vectors with pairwise inner products 1/v). We call X and Y a pair of linked simplices if, for every x ∈ X and y ∈ Y, we have ⟨ x,y ⟩ ∈ {γ,ζ} for some fixed values of γ and ζ. We ask the question of when you can find large sets of simplices for which every pair of them are linked using the same inner products γ and ζ. In this talk, we show that any set of w linked simplices corresponds to a linked system of symmetric designs (LSSD) on w fibers. Using the Qpolynomial structure of LSSDs, we then construct linked simplices showing the equivalence between these two objects. Finally we review known examples such as the CameronSeidel association scheme and, in restricted cases, use the linked simplices to construct real mutually unbiased bases.
 18 January: Bill Martin, WPI "Ideals for combinatorial tdesigns"
Abstract: Let X be a finite set and let (X,D) be a kuniform hypergraph on point set X. We call the elements of D blocks and identify each b ∈ D with its incidence vector c_{b}. We seek a nice description of the ideal I(D) of all polynomials F in X variables which vanish on the point set { c_{b}  b ∈ D }. The pair (X,D) is a tdesign if every telement subset of X is contained in exactly λ blocks b in D for some constant λ. In this joint work with Doug Stinson, I explore the relationship between t and two parameters: γ_{1}(D) is the smallest degree of a nontrivial polynomial in the ideal I(D) and γ_{2}(D) is the smallest integer s such that I(D) is generated by a set of polynomials all having total degree at most s.
 25 January: Luke Brown, WPI "Quantum walks on cubelike graphs"
Abstract: Let Γ be a Cayley graph whose underlying group is Z_{2}^{d} for a given d ∈ N. Then, for some C ⊆ Z_{2}^{d}, we have that, given any a,b ∈ Z_{2}^{d}, ab ∈ E(Γ) ⇔ ab ∈ C. In this case, we call Γ the cubelike graph with connecting set C and denote it Γ(C). Recall that, if A is the adjacency matrix of Γ(C), then the transition operator, U(t), is given by U(t)=e^{iAt}.If ψ is a state vector on Z_{2}^{d}=V(Γ(C)), then we express the continuous time quantum walk on Γ(C) as φ(t)=U(t)ψ. Recall that (a,b)perfect state transfer, or PST on Γ(C) at time t=τ is defined as the condition, U(τ)_{ab}=1, while aperiodicity at t=τ is defined as U(τ)_{aa}=1. We classify all cubelike graphs which have (a,a+σ)PST at time π/2, where σ denotes a permutation on Z_{2}^{d}, and we show that the remaining cubelike graphs are aperiodic for each a ∈ Z_{2}^{d} at time π/2. Let S_{d} denote the set of cubelike graphs over Z_{2}^{d} that are aperiodic for each a at time π/2. We then extend this result by classifying the bipartite double covers of the graphs of S_{d} that have (a,a+σ')PST at time π/2 for each a.
By considering the cubelike graphs, we provide a class of examples where we can easily construct graphs which have PST. However, we also introduce the notion of group state transfer, or GST, which is a more relaxed condition than PST. Let ψ be a state vector over graph, Γ, which is only nonzero on some strict subset S ⊆ V(Γ). Suppose that, for some τ ∈ R, the vector φ=U(τ)ψ is only nonzero on a strict subset, T ⊆ V(Γ). If such a τ, S, and T exist, then Γ is said to have (S,T)group state transfer, or GST, at time τ. We show that, on a graph with PST, it is easy to also demonstrate GST. However, we also discuss the difficulties of finding graphs without PST, but which have GST.
 1 February: WeiHsuan Yu, ICERM at Brown U. "Saturated equiangular lines in Euclidean space"
Abstract: A set of lines through the origin in a Euclidean space is called equiangular when any pair of lines from the set intersects with each other at a common angle. We study the maximum size of equiangular lines in Euclidean space and use a graphtheoretic approach to prove that all the currently best known constructions in ddimensional Euclidean space cannot be extended to form a larger equiangular set of lines for the cases d=14, 16, 17, 18, 19 and 20.
 8 February: Tom Roby, UConn "Dynamical Algebraic Combinatorics and the Homomesy Phenomenon"
Abstract: Dynamical Algebraic Combinatorics explores actions on sets of discrete combinatorial objects, many of which can be built up by small local changes, e.g., Schutzenberger's promotion and evacuation, or the rowmotion map on order ideals. There are strong connections to the combinatorics of representation theory and with Coxeter groups. Birational liftings of these actions are related to the Ysystems of statistical mechanics, thereby to cluster algebras, in ways that are still relatively unexplored.The term "homomesy" (coined by Jim Propp and the speaker) describes the following widespread phenomenon. Given a group action on a set of combinatorial objects, a statistic on these objects is called homomesic if its average value is the same over all orbits. Along with its intrinsic interest as a kind of "hidden invariant", homomesy can be used to prove certain properties of the action, e.g., facts about the orbit sizes. Proofs of homomesy often involve developing tools that further our understanding of the underlying dynamics, e.g., by finding an equivariant bijection.
This talk will focus on the combinatorial side, giving a number of examples of homomesy due to the author and others.
 15 February: No seminar Academic Advising Day
 22 February: Joseph Fehribach, WPI "Recent Developments on Kirchhoff Graphs: Existence and Construction"
Abstract: Kirchhoff graphs are vector graphs which satisfy the Kirchhoff laws and can be used as circuit diagrams for chemical and other reaction networks. The construction of Kirchhoff graphs associated with a given matrix can be a difficult problem, and in general it is still an open question whether or not there exists a Kirchhoff graph for any matrix with rational entries. This talk will discuss the existence of Kirchhoff graphs and a number of recent developments concerning their construction. These include existence and construction for matrices over finite fields, constructions based on equitable partitions, a numerical algorithm for their construction based on the rank and nullity of the matrix, and a explicit construction for rank 2, nullity 2 matrices over the rationals.
 1 March: Padraig Ó Catháin, WPI "TBA"
Abstract:
B TERM 2017
 Tuesdays 9:009:50am, in Room 203 Stratton Hall
 24 October: Randy Paffenroth, WPI "The Restricted Isometry Property, Hadamard Matrices, and Quasirandom Constructions"
Abstract: Compressed sensing has a role to play in many fields, including signal processing, image processing, and machine learning, and sensing matrices with the Restricted Isometry Property play a pivotal role in the theory underlying the method. However, at the current time, there are no known deterministic constructions of matrices that match the performance of random matrix constructions. In this talk we will explore such deterministic constructions, discuss some of the difficulties that arise, and show connections to several other branches of mathematics.
 31 October: Brian Kodalen, WPI "Recommendations from Social Media"
Abstract: Recommender systems are prevalent across many of the applications we use on a weekly basis. Netflix, Amazon, Google searches, and even the ads popping up on the sidebars of various websites are many of such examples. In this talk we introduce the notion of a recommender system and showcase a specific example of their use in the case of sparse data. We will discuss areas such as data filtering, topic modeling, building total distance while missing data, and a few viable graph based approaches to building a recommender. We then will examine a prototype based on the methods discussed and suggest further improvements.
 7 November: Bill Martin, WPI "Continuous time quantum walks on highly regular graphs"
Abstract: Quantum walks on graphs are not at all well understood but play a fundamental role in quantum information theory and could lead to new insights about quantum computer algorithms. We will look at the simplest case.Let G be a finite simple graph on n vertices with adjacency matrix A. Since A is Hermitian with zero diagonal, the matrix iA t is skewHermitian for any real t, so the exponential U(t) = exp(i At) is unitary. If x denotes an initial quantum state, then the continuous time quantum walk on G is defined to take value U(t) x at time t, where U(t)x is a superposition of basis states indexed by the vertices of G. For each j in V(G), the jth column of U(t) is a unit vector. So replacing each entry by its squared modulus, we obtain a probability distribution on V(G) which we interpret as the probability that the (random) walk starting at vertex j ends at any given k at time t.
After reviewing basic concepts such as perfect state transfer (where the jth column of some U(t) has just one nonzero entry), pretty good state transfer (where the jth column of U(t) can be made arbitrarily close to a unit scalar multiple of some column of the identity matrix), uniform mixing and periodic graphs, we explore some recent results on the average mixing matrix Mhat and we consider examples where G is a basis relation in some association scheme such as the Johnson scheme.
 14 November: Padraig Ó Catháin, WPI "Nesting symmetric designs"
Abstract: The incidence matrix of a symmetric design is a (0,1) matrix, with constant row and column sums, in which the inner product of any pair of distinct rows (or columns) is some fixed integer λ. Call such a matrix a Dmatrix. Gnilke, Greferath and Pavcevic have studied the problem of decomposing the allones matrix into Dmatrices. Independently, Bryant and Horsley posed a problem about characterizing the Dmatrices M such that M+I is also a Dmatrix.In this talk, I will provide the complete solution to the BryantHorsley problem, and discuss some recent work on this problem carried out jointly with Oliver Gnilke.
 21 November: Cristina Ballantine (College of the Holy Cross) "Bisected theta series"
Abstract: Euler's pentagonal number theorem (EPNT) is a special case of a classical theta identity. Recently, Merca considered a bisection of EPNT, which led to new partition identities. It is natural to consider bisections for other classical theta identities. This leads to new partition identities relating polygonal numbers and new partition functions involving least rgaps. This is joint work with Mircea Merca. If time permits, I will also discuss some results about truncations of theta series.
 28 November: Zimu Li, WPI "Fast matrix multiplication using the group algebra"
Abstract: Cohn and Umans developed a method of embedding matrix multiplication into group algebras of finite groups which in some cases allows for matrix multiplication with complexity less than O(n^{3}). In this talk, we will present a proof for this result, and investigate the complexity of matrix multiplication in certain group algebras.
 5 December: Tyler Reese, WPI ``Equitable edgepartitions''
Abstract: Equitable partitions of graphs, introduced in the late 1960's, allow one to study the eigenvectors and eigenvalues of a graph by considering those of a smaller quotient graph. Traditionally applied to the vertex set of a graph, equitable partitions are closely related to orbits of graph automorphisms, walk partitions, distanceregular graphs, and association schemes. After introducing this wellknown theory of equitable vertex partitions, this talk extends these notions by defining equitable edgepartitions of multidigraphs. We demonstrate that these edge partitions satisfy the same properties of their vertex counterparts, and show that equitable edgepartitions can give rise to Kirchhoff graphs.
 12 December: No seminar (Reading Day)
C TERM 2017
D TERM 2017
 Tuesdays 1:001:50pm, in Room 202 Stratton Hall
 17 January: "Userprivate information retrieval via finite geometries", Padraig Ó Catháin
 24 January: "Some mathematical remarks on the DWave 'quantum' computer", Bill Martin
 31 January: Marcel GietzmannSanders
 7 February: Randy Paffenroth (WPI) "Musings On the Restricted Isometry Property and Deterministic Matrices"
Abstract: Compressed sensing has a role to play in many fields, including signal processing, image processing, and machine learning, and sensing matrices with the Restricted Isometry Property play a pivotal role in the theory underlying the method. However, at the current time, there are no known deterministic constructions of matrices that match the performance of random matrix constructions. In this talk we will explore such deterministic constructions, discuss some of the difficulties that arise, and show connections to several other branches of mathematics.
 14 February: Gábor Sárközy (WPI) "Ramseytype problems"
Abstract: We survey some results on the following problem: Say we are given fixed positive integers s, t and a family of graphs F. Minimizing over all tedge colorings of the complete graph on n vertices, we ask for the maximum number of vertices that can be covered by at most s monochromatic members of F. This problem unites two classical problems: at one end of the spectrum (s = 1) we have the Ramsey problem, while at the other end we have cover problems. But there are some interesting problems "inbetween" as well. Several of the results are joint with András Gyárfás and/or Endre Szemerédi.
 21 February: Miklós Ruszinkó (University of Memphis)
 28 February: Cristina Ballantine (Holy Cross) "A brief introduction to integer partitions (biased toward parity results)"
Abstract: A partition of an integer n is a way of writing n as a sum of positive integers without regard to order. The partition function p(n), which counts the number of partitions of n, has been studied extensively since Euler and has applications in many areas of mathematics as well as in other sciences. We will discuss several classical identities and illustrate the power and beauty of two of the main tools used for proving such identities: bijective proofs and generating functions. I will also present recent work (joint with M. Merca) on the parity of certain partition functions.
 7 March: No seminar (Spring break)
 Tuesdays 1:001:50pm, in Room 106 Stratton Hall
 14 March: Snow day
 21 March: Richard Brualdi (University of Wisconsin), "Permutation Matrices, Alternating Sign Matrices, and the Bruhat Order"
Abstract: Permutations and Permutation Matrices are classical combinatorial objects with a rich and muchstudied structure. Alternating Sign Matrices (ASMs) are more recently studied combinatorial objects which contain permutation matrices as special instances. The Bruhat order on permutations generalizes to ASMs via MacNeille's classical theorem. The Birkhoff polytope of doubly stochastic matrices (convex hull of permutation matrices) extends to the ASM polytope (convex hull of ASMs). In his talk we shall discuss all these things.
 28 March: Bill Martin (WPI) "Complementary decompositions and unextendible mutually unbiased bases"
 4 April: Cristina Ballantine (Holy Cross), "The Kronecker product for symmetric group representations indexed by a hook and a rectangle"
Abstract: The representations of the symmetric group are indexed by Schur functions. Recently Blasiak gave a combinatorial interpretation for the coefficients in the Schur basis decomposition of the Kronecker product when one representations is indexed by a hook. The case when one representation is indexed by a hook and the other is indexed by a rectangle is helpful in understanding the quantum Hall effect. Using Blasiak's interpretation, we show that, as the size of the symmetric group grows, the decomposition of the Kronecker product of a hook and a rectangle displays an interesting stability property which allows for the decomposition to be completely determined from a minimal size case. (This is joint work with Bill Hallahan.) If time permits, I will also talk about another result related to the Kronecker product of a hook and a rectangle, the Schurpositivity of a particular difference of products of symmetric functions. (This is joint work with Rosa Orellana.)
 11 April: Miklós Bóna (University of Florida), "Counting vertices in labeled rooted trees"
Abstract: Various parameters of many models of random rooted trees are fairly well understood if they relate to a nearroot part of the tree or to global tree structure. In recent years there has been a growing interest in the analysis of the random tree fringe, that is, the part of the tree that is close to the leaves. Distance from the closest leaf can be viewed as the protection level of a vertex, or the seniority of a vertex within a network.In this talk we will review a few recent results of this kind for a number of tree varieties, as well as indicate the challenges one encounters when trying to generalize the existing results. One tree variety, that of decreasing binary trees, will be related to permutations, another one, phylogenetic trees, is frequent in applications in molecular biology.
 18 April: Jeanne Scott, "Discrete harmonicity for finite graphs and periodic planar triangulations"
Abstract: This talk will begin with an introduction to discrete Laplacians and the Dirichlet problem for locally finite graphs with boundary. We'll discuss two results in this area: (1) a combinatorial formula of D. Ingerman to explicitly construct harmonic functions for a finite graph using Kirchhoff's matrix tree theorem and (2) a residue formula of R. Kenyon to express the Green's function of the discrete Laplacian for a periodic isoradial triangulation of the plane. If time permits I'll comment on work in progress with F. David concerning the Green's function for perturbations of isoradial embeddings.
 25 April: Padraig Ó Catháin (WPI)
 2 May: No seminar (last day of class)
A TERM 2016
B TERM 2016
 29 August: Organizational meeting in AK218 at 11:00am
 5 September: Labor Day  No seminar
 12 September: Tyler Reese AK218, 11:0011:50
 19 September: "Ramanujan graphs and bigraphs", Cristina Ballantine (College of the Holy Cross), AK218, 11:0011:50
 26 September: "Quantum walks on graphs", Bill Martin (WPI), AK218, 11:0011:50
 3 October: "Quantum walks on graphs  a physicists's perspective" P K Aravind (WPI), AK218, 11:0011:50
 10 October: No seminar (Columbus Day)
 Tuesdays 2:002:50pm, in Room 203 Stratton Hall
 31 October: No seminar
 7 November: Bill Martin "Algebraic manipulation detection codes: using characters to study strong external difference families"
 (Special day and room!) 14 November: Padraig Ó Catháin "Finite Fields and Fourier Analysis, 1" This seminar will be held in SH106 at 2pm on Monday
 22 November: Padraig Ó Catháin "Finite Fields and Fourier Analysis, 2"
 29 November: Tyler Reese "Binary Matroids and Kirchhoff graphs"
 6 December: Brian Kodalen "Connectivity of nearest neighbor graphs in association schemes"
Abstract: A symmetric association scheme can be viewed as an edgecoloring of a complete graph with many regularity properties. Denoting one such color as the "nearest neighbor relation", we form a graph induced by that color and wish to understand the structure of this graph. One question that arises in this context is the connectivity of such a graph. Godsil conjectured that the smallest cutset has cardinality equal to the valency of the graph. However the current best lower bound is only half this value. In this talk we give a brief introduction to association schemes and their regularity properties. We will then use these properties to examine a specific cutset given by the neighborhood of any vertex. We will show that deleting this neighborhood with the original vertex leaves behind at most one nonsingleton component with isolated vertices only arising in specific cases. Finally, we use this result to show that a vertex and any proper subset of its neighborhood can never serve as a cutset for our graph.
 13 December: Sejeong Bang (Busan National University/MIT) "Antipodal and geometric distanceregular graphs"
Abstract: A noncomplete distanceregular graph Γ is called geometric if there exists a set of Delsarte cliques ℭ such that each edge of Γ lies in a unique clique in ℭ. In this talk, we introduce antipodal and geometric distanceregular graphs. In particular, we give a diameter bound for geometric distanceregular graphs with smallest eigenvalue m. Moreover, we characterize geometric distanceregular graphs with smallest eigenvalue at least 4. Moreover, we show that for given a positive integer m, there are only finitely many antipodal and geometric distanceregular graphs with smallest eigenvalue m.