Discrete Mathematics Seminar

Discrete Math Seminar Schedule for Spring 2020:

C TERM 2020

• Wednesdays 10:00-10:50am, in Room 203 Stratton Hall

  
  

• 22 January: Herman Servatius, WPI "Linear Algebra, Matroids, and Delta-Matroids applied to Geometric Constraint Systems"
  Abstract: A specific embodiment of a geometric constraint system may be analyzed with standard techniques of civil or mechanical engineering. Determining the general principles may involve moving to increasing levels of abstraction.

• 29 January: Herman Servatius, WPI "Linear Algebra, Matroids, and Delta-Matroids applied to Geometric Constraint Systems"
  Abstract: Continuation of January 22 discussion.

• 5   February: Bill Martin, WPI "Vector spaces of scaffolds"
  Abstract: Let X be a nonempty finite set and let A be a vector subspace of Mat_X(ℂ) where ℂ is the field of complex numbers. Consider a digraph G=(V(G),E(G)) with edge weight function w : E(G) → A and an ordered set R ⊆ V(G) of distinguished "root" nodes. For |R|=m, the scaffold S(G,R;,w) is then defined as a certain m^th order tensor over the space of complex-valued 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).

  Now, choosing a coherent algebra A contained in Mat_X(ℂ) and fixing the rooted diagram (G,R), we study the vector space of all scaffolds S(G,R;w) as w ranges over all functions from V(G) to A. For |R| fixed, we find interesting results about the partial order on such spaces as we vary the diagram.

  
  

• 12 February: Joseph Fehribach, WPI "Matroids and Their Kirchhoff Graphs"
  Abstract: Given a set of n vectors in any vector space over the rationals, suppose that k < n are linear independent. Kirchhoff graphs are graphs whose edges are these vectors, whose cycles represent their dependencies and whose vertex cuts are orthogonal to these cycles. In this regard, Kirchhoff graphs satisfy the Kirchhoff laws. Matroids can also be constructed based on cycles in graphs, though some matroids are non-graphic. We will discuss the construction of Kirchhoff graphs over ℤ₂ corresponding to any matroid. Indeed, although a number of matroids are non-graphic, every binary matroid is ℤ₂-Kirchhoff graphic.

• 19 February: Padraig Ó Catháin, WPI "Orthogonal designs"
  Abstract: We will review Jennifer Seberry's theory of orthogonal designs and work toward her proof of the asymptotic Hadamard conjecture.

• 26 February: Ada Chan, York University "Fractional revival on graphs"
  Abstract: Let X be a weighted graph and A be its adjacency matrix. The continuous-time quantum walk on X is given be the transition matrix e^{-i t A}. Let e_a and e_b denote the characteristic vectors of a and b in V(X). We say fractional revival occurs from vertex a to b at time τ if
  e^{-i τ A} e_a = α e_a+β e_b,
  for some complex numbers α and β satisfying |α|² +|β|²=1.

  When α=0, we have perfect state transfer from a to b. The spectral properties of graphs admitting perfect state transfer have been studied extensively in the past decade. In particular, perfect state transfer occurs only between strongly cospectral vertices.

  In this talk, we extend the notion of strong cospectrality to a necessary spectral condition on vertices having fractional revival. We give a characterization of graphs admitting fractional revival, and construct weighted graphs that have fractional revival between every pair of vertices.

  This is joint work with Gabriel Coutinho, Whitney Drazen, Or Eisenberg, Chris Godsil, Mark Kempton, Gabor Lippner, Christino Tamon and Hanmeng Zhan.

• 4   March: Guillermo Carlo Nuñez, WPI "The joints problem and arithmetic sequences"
  Abstract: A joint is a point in space where at least three lines meet. If we have L lines in ℝ³, how many joints can there be? Finding good estimates using arguments involving only points, lines and planes seems to be a hard problem. On the other hand using the polynomial method we can easily find better estimates. In this talk we will follow both approaches and discuss why the polynomial method does so well at this type of problem.

  This talk follows the exposition of Larry Guth in the book Polynomial Methods in Combinatorics, and is part of an independent study with Bill Martin.

• Fridays 3:00-3:50pm, in Room 202 Stratton Hall

Discrete Math Seminar Schedule for Fall 2019:

B TERM 2019

• Thursdays 10:00-10:50am, in Room 202 Stratton Hall

  
  

• 24 October: Guillermo Carlo Nuñez, WPI "Nonexistence of quaternary unit Hadamard matrices"
  Abstract: Quaternary unit Hadamard matrices are a family of complex Hadamard matrices with entries in a biquadratic extension of the rationals. We obtain nonexistence conditions for this family of matrices by studying prime ideal factorization on biquadratic number fields. Our approach generalizes the nonexistence results of Butson Hadamard matrices by Winterhof. This is joint work with Padraig Ó Catháin, Philip Heikoop and John Pugmire.

• 31 October: Ronan Egan, Rijeka Croatia "Constructions of various related combinatorial designs"
  Abstract: In this talk I will discuss a variety of combinatorial structures such as Hadamard matrices, weighing matrices and their generalizations. It will be a broad introduction to the topic, including constructions and theoretical results regarding existence. Particular attention will be paid to a fruitful construction of these objects based on sequences that are complementary under some autocorrelation function.

• 7   November: Cristina Ballantine, Holy Cross "Almost partition identities"
  Abstract: An almost partition identity is an identity for partition numbers that is true asymptotically 100% of the time and fails infinitely often. We prove a new kind of almost partition identity, namely the number of parts in all self-conjugate partitions of n is almost always equal to the number of partitions of n in which no odd part is repeated and there is exactly one even part (possibly repeated). Not only does the identity fail infinitely often, but also the error grows without bound. In addition, we prove several identities involving the number of parts in restricted partitions. (Joint work with George Andrews.)

• 14 November: Duncan Wright, WPI "Quantum Walk Algorithms on Graphs"
  Abstract: Graphs can be used as a framework to pose many questions from varied disciplines. As such, it is of general interest to develop algorithms on graphs to, for example, find the shortest path between two points. In this talk, we will review the use of Unitary Quantum Random Walks in graph algorithms that exhibit speed-up over their classical counterparts. Our discussion will start with one of the earliest examples, namely, Grover's algorithm for a database search.

• 21 November: Miklós Bóna (University of Florida), "A method to prove that the solution to some enumeration problems is a non-rational generating function"
  Abstract: The solution of an enumeration problem is very often a generating function F. Some problems are too difficult for us to find the explicit form of F. In this talk, we will introduce a method that leads to negative results that are rare in this part of combinatorics. When our method applies, it shows that F is not a rational function, which provides at least some explanation of the fact that the original enumeration problem is difficult. As an example, we will discuss a 22-year old conjecture of Zeilberger and Noonan.

  The talk will be accessible to graduate students.

• 5   December: No seminar

• 12   December: No seminar

• Thursdays 2:00-2:50pm, in Room 106 Stratton Hall

  
  

• 5   September: Bill Martin, WPI "An update on scaffolds"
  Abstract: Star-triangle diagrams are a useful but poorly understood tool in the theory of association schemes. Similar ideas have been used to rule out distance-regular graphs using different language. Meanwhile the same object is encoded in the partition function of link diagrams in the development of spin models. I gave a talk on these objects last year.

  Today's goal is to simply focus on lower order objects: vectors, matrices, and third-order tensors. I will try to keep things concrete.

  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 S ⊆ V(G) of distinguished ("solid") nodes. For |S|=m, the scaffold S(G,S,w) is then defined as a certain m^th order tensor over the space of complex-valued functions on X. For example, when m=0 the scalar S(G,S,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).

  
  

• 12 September: Daniel Reichman, WPI "Contagious sets in bootstrap percolation"
  Abstract: Consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors. This process (commonly referred to as bootstrap percolation) has been studied in several fields including combinatorics, computer science, statistical physics and viral marketing. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m(G,r) be the minimal size of a contagious set.

  I will survey upper and lower bounds for m(G,r) in general graphs and for graphs with special properties (random and pseudo-random graphs, graphs without short cycles) and discuss many unresolved questions.

  Based on joint work with Amin Coja-Oghlan, Uriel Feige and Michael Krivelevich.

• 19 September: Andrew Uzzell, College of the Holy Cross "Graph Limits, Entropy, and Counting" Abstract: The theory of graph limits provides an analytic framework for studying large graphs.We use graph limits to analyze the typical structure of networks that come from various families of graphs, including graphs defined by forbidden substructures and spatially defined graphs. Our proofs rely on both combinatorial arguments and analytic and topological properties of the space of graph limits. This is joint work with Victor Falgas-Ravry, Svante Janson, Kelly O'Connell, and Johanna Stromberg.

• 26 September: Carolyn Mayer, WPI "Service Rates in Coded Distributed Storage"
  Abstract: In distributed storage systems, information is stored across multiple servers or nodes. The service rate region of a distributed storage system is the set of file request rates that the system can support. We consider the achievable service rate region for systems in which a combination of replication and coding is used to store K files across N > K nodes.

  This talk is based on joint work with Mehmet Aktas, Sarah E. Anderson, Ann Johnston, Gauri Joshi, Swanand Kadhe, Gretchen L. Matthews, and Emina Soljanin.

• 3   October: Jonathan Jedwab, Simon Fraser University "New Constructions of Difference Matrices"
  Abstract: Difference matrices are a type of combinatorial design that is closely connected to many other objects from design theory and algebra, including orthogonal arrays, transversal designs, mutually orthogonal Latin squares, and orthogonal orthomorphisms. The study of difference matrices has received renewed interest following the recent discovery that they can be used to construct linking systems of difference sets and so provide new examples of linked symmetric designs and cometric association schemes.

  I shall show that there are special examples of difference matrices in abelian groups that can be concisely encoded using a much smaller matrix. This is analogous to the use of a generator matrix to represent a linear code in coding theory. I shall show that several of the principal previous constructions of difference matrices can be stated and proved much more simply in terms of these smaller matrices. I shall then present four examples of difference matrices in abelian groups having twice as many rows as the best previously known, each of which gives rise to a new infinite family of examples.

  Joint work with Koen van Greevenbroek.

• 10   October: No seminar - last day of A Term

  
  

Discrete Math Seminar Schedule for Spring 2019:

D TERM 2019

• Tuesdays 10:00-10: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 q-integers. 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, counter-intuitive 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 so-called 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 "Maximum-sized 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, NP-hard 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 k-regular (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: maximum-sized 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 non-adjacency, is 90°. In restricted cases, a projective double (with both angles less than 90°) corresponds to a 5-class Q-bipartite association scheme while an orthogonal projective double (OPD) gives a 4-class Q-bipartite 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 4-class Q-bipartite association schemes from an OPD -- noting the extra conditions this imposes on the underlying graph. Finally, we rule out Hamming graphs as quotients of 4-class Q-bipartite 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 (well-known) 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 semi-simple 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:00-11: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 5-10, 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 2-distance 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 number-theoretic 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₆ using a complex Hadamard matrix and the algebra of split-quaternions. 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 q-integers. 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 C-Matrices"
  Abstract: TBA C-matrices, also known as conference matrices, are matrices satisfying the equation CC^T=(n-1)I_n which are 0 on the main diagonal and +/-1 elsewhere. The existence (or non-existence) of C-matrices 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 C-Matrices of Arbitrary Powers, which provides a technique for blowing up a C-matrix of order n into a new one of order n^m for arbitrary natural numbers m. To this end, Turyn introduces combinatorial objects called G-strings, which have many interesting properties. We present simplified, more explicit proofs of Turyn's results, including new intermediate results on the properties of G-strings.

  
  

• 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 d-dimensional 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 quasi-symmetric 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 ℝ⁶. 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₈ lattice with the projection onto an 8-dimensional subspace of a sub-lattice of the Leech lattice defined by 276 equiangular lines in ℝ²³. 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 ℝ²³.

  
  

• 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 (Round-Robin 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).

  
  

Discrete Math Seminar Schedule for Fall 2018:

B TERM 2018

• Tuesdays 3:00-3: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 Chen-Chvá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 error-correcting 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 (2n-1) 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 Erdos-Ginzburg-Ziv 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: Quasi-Monte 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 quasi-Monte Carlo method employs deterministic point sets which are distributed ``uniformly'' with respect to some pre-specified 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 Schmid-Lawrence Theorem which connects (T,M,S)-nets to orthogonal arrays and error-correcting 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) if
  • G is regular of valency k
  • every pair of adjacent vertices in G have λ common neighbors
  • every pair of non-adjacent vertices in G have μ common neighbors.
  The class of strongly regular graphs is connected to many interesting objects such as Steiner triple systems, generalized quadrangles, projective two-weight codes, quasi-symmetric 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.

  
  
  

• 11     December: No seminar, Reading Day
  

  
  

A TERM 2018

• Tuesdays 2:00-2: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₁ ≤ d₂ ≤ . . . ≤ d_n and, for i up to (n-1)/2, we have d_i ≤ i ⇒ d_n-i ≥ n-i, 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 list-coloring exists. All is not lost, though, as Carsten Thomassen proved in 1994 that every planar graph admits a proper list-coloring 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 list-colorable graphs. The second is a recent non-refereed 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 so-called nonassociative groups. Mendelsohn triple systems may be realized as idempotent, semisymmetric quasigroups, which are quasigroups satisfying the identities x² = 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 2-connected Kirchhoff graphs are always uniform -- each edge vector occurs a fixed number of times.

  
  

Discrete Math Seminar Schedule for Spring 2018:

D TERM 2018

• Mondays 3:00-3: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 graph-based system for computations with certain tensors"
  Abstract: Star-triangle diagrams are a useful but poorly understood tool in the theory of association schemes. Similar ideas have been used to rule out distance-regular 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 complex-valued 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 Bose-Mesner 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 distance-regular graphs and one structure theorem for Q-polynomial association schemes.

  
  

•   2     April: Ronan Egan, Rijeka Croatia "Self-orthogonal 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 self-orthogonal and Hermitian self-orthogonal linear codes over some finite fields. Consequentially, under certain conditions, their orbit matrices generate self-orthogonal and Hermitian self-orthogonal 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 self-orthogonal codes with good error-correcting 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 well-known 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) self-dual, 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 well-understood 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 sub-quadratic 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 Bose-Mesner 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 Bose-Mesner Algebras.

  
  

C TERM 2018

• Thursdays 10:00-10: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 Q-polynomial structure of LSSDs, we then construct linked simplices showing the equivalence between these two objects. Finally we review known examples such as the Cameron-Seidel association scheme and, in restricted cases, use the linked simplices to construct real mutually unbiased bases.

  
  

• 18     January: Bill Martin, WPI "Ideals for combinatorial t-designs"
  Abstract: Let X be a finite set and let (X,D) be a k-uniform 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 t-design if every t-element 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: γ₁(D) is the smallest degree of a non-trivial polynomial in the ideal I(D) and γ₂(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₂^d for a given d ∈ N. Then, for some C ⊆ Z₂^d, we have that, given any a,b ∈ Z₂^d, ab ∈ E(Γ) ⇔ a-b ∈   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₂^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 a-periodicity 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₂^d, and we show that the remaining cubelike graphs are a-periodic for each a ∈ Z₂^d at time π/2. Let S_d denote the set of cubelike graphs over Z₂^d that are a-periodic 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: Wei-Hsuan 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 graph-theoretic approach to prove that all the currently best known constructions in d-dimensional 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 Y-systems 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:

Previous Semesters

Discrete Math Seminar Schedule for Fall 2017:

B TERM 2017

• Tuesdays 9:00-9:50am, in Room 203 Stratton Hall

  
  

• 24     October: Randy Paffenroth, WPI "The Restricted Isometry Property, Hadamard Matrices, and Quasi-random 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 skew-Hermitian 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 j-th 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 j-th column of some U(t) has just one non-zero entry), pretty good state transfer (where the j-th 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 M-hat 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 D-matrix. Gnilke, Greferath and Pavcevic have studied the problem of decomposing the all-ones matrix into D-matrices. Independently, Bryant and Horsley posed a problem about characterizing the D-matrices M such that M+I is also a D-matrix.

  In this talk, I will provide the complete solution to the Bryant-Horsley 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 r-gaps. 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³). 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 edge-partitions''
  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, distance-regular graphs, and association schemes. After introducing this well-known theory of equitable vertex partitions, this talk extends these notions by defining equitable edge-partitions of multi-digraphs. We demonstrate that these edge partitions satisfy the same properties of their vertex counterparts, and show that equitable edge-partitions can give rise to Kirchhoff graphs.

• 12     December: No seminar (Reading Day)

Discrete Math Seminar Schedule for Spring 2017:

C TERM 2017

• Tuesdays 1:00-1:50pm, in Room 202 Stratton Hall
• 17       January: "User-private information retrieval via finite geometries", Padraig Ó Catháin
• 24       January: "Some mathematical remarks on the D-Wave 'quantum' computer", Bill Martin
• 31       January: Marcel Gietzmann-Sanders
•   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) "Ramsey-type 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 t-edge 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 "in-between" 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)

D TERM 2017

• Tuesdays 1:00-1: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 much-studied 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 Schur-positivity 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 near-root 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)

Discrete Math Seminar Schedule for Fall 2016:

A TERM 2016

• 29       August: Organizational meeting in AK218 at 11:00am
•   5 September: Labor Day -- No seminar
• 12 September: Tyler Reese AK218, 11:00-11:50
• 19 September: "Ramanujan graphs and bigraphs", Cristina Ballantine (College of the Holy Cross), AK218, 11:00-11:50
• 26 September: "Quantum walks on graphs", Bill Martin (WPI), AK218, 11:00-11:50
•   3    October: "Quantum walks on graphs -- a physicists's perspective" P K Aravind (WPI), AK218, 11:00-11:50
• 10    October: No seminar (Columbus Day)

B TERM 2016

• Tuesdays 2:00-2: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 edge-coloring 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 non-singleton 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 distance-regular graphs"
  Abstract: A non-complete distance-regular 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 distance-regular graphs. In particular, we give a diameter bound for geometric distance-regular graphs with smallest eigenvalue -m. Moreover, we characterize geometric distance-regular 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 distance-regular graphs with smallest eigenvalue -m.