Discrete Math Seminar Schedule for Spring 2023:

C TERM 2023

• Mondays 4:00-4:50pm, Room SH202, Stratton Hall



• 16 January: No seminar (MLK Day)
  

• 23 January: Brigitte Servatius, WPI, "Self-dual maps on the sphere and other compact surfaces"
  Abstract: TBD

• 30 January: No seminar, take a break
  Abstract: TBD

• 6 February: Bill Martin, WPI, "Dispersed graph labellings"
  Abstract: I will discuss a fun problem that I recently worked on with Doug Stinson (Waterloo). Let G be a graph with vertex set V and path-length distance function d(.,.). A k-dispersed labeling of G is a linear ordering v₁, v₂, ..., v_n of the vertices such that d(v_i-1, v_i ) ≥ k for all i=2,...,n. Finding the best k for a given graph is an NP-hard problem but we have bounds and can find exact values for various families of graphs. I predict you can do better than I have done.

• 13 February: Brigitte Servatius, WPI, "Delta matroids"
  Abstract: They were invented by Andre Bouchet in 1987. We will go over their definition, explain why they are not matroids and use maps of graphs on surfaces as source of examples.

• 20 February: Neranga Fernando, College of the Holy Cross, "Quandles, racks and shelves"
  Abstract: A quandle is a set X with a binary operation ∗ : X × X → X satisfying:
  1. For all x ∈ X, x ∗ x = x
  2. For all y ∈ X, the map β_y : X → X defined by β_y(x)= x ∗ y is invertible.
  3. For all x,y,z ∈ X, (x ∗ y) ∗ z = (x ∗ z) ∗ (y ∗ z).
  The three axioms of a quandle algebraically encode the three Reidemeister moves in knot theory.

  A rack is a set with a binary operation that satisfies (ii) and (iii), and a shelf is a set with a binary operation satisfying self-distributivity (iii).

  I will begin this talk by giving an introduction to quandles. I will then talk about racks, shelves and quandle rings. Moreover, I will talk about a recent joint work with Matthew Pradeep Goonewardena and Mohamed Elhamdadi on shelves.

• 27 February: Speaker TBD, "Title TBA"
  Abstract: TBD

Past Seminars

A TERM 2022

• Wednesdays 3:00-3:50pm, Room SH106, Stratton Hall



• 31 August: Bill Martin, WPI, "Discovering new strongly regular graphs"
  Abstract: Can you construct a regular graph in which any two vertices have a unique common neighbor? How about a regular graph where any two vertices have λ > 1 common neighbors? What if we require λ triangles on each edge and λ+1 common neighbors for any two unequal non-adjacent vertices? Any connected graph with such regularity is strongly regular: it must be a regular graph with three distinct eigenvalues. Some rather small open problems in this area remain unsolved. (For example, a famous problem of John Conway asks if a 14-regular graph exists in which each edge lies in a unique triangle and each pair of non-adjacent vertices are the corners of a unique quadrilateral.)

  Until a few years ago, the smallest open parameter set for a strongly regular graph was (65,32,15,16): is there a 32-regular graph on 65 vertices in which each pair of adjacent (resp., non-adjacent, distinct) vertices have 15 (resp., 16) common neighbors? In a sense, this would resemble a "finite field" of order 65. Oleg Gritsenko produced such a graph in October 2020 and this is our point of departure. Inspired by Gritsenko, Jason Williford concocted a general recipe for strongly regular graphs of valency k on 2k+1 vertices. The Paley graph of any finite field gives an example. But we found more. I will describe our approach, the examples we found, and the many remaining open questions.

  The talk should be accessible to advanced undergraduate students.

• 7 September: Cristina Ballantine, College of the Holy Cross, "Hooks and contents in partitions"
  Abstract: The irreducible polynomial representations of the general linear group are indexed by partitions. The dimension of a representation is given by a formula involving the hook lengths and the contents of cells in the Young diagram of the indexing partition. There are also analogous formulas for irreducible polynomial representations of symplectic and orthogonal groups. I will discuss the combinatorial nature of identities involving the symplectic and orthogonal hook--content formulas. These have been conjectured by T. Amdeberhan. Time permitting, I will also introduce some auxiliary results. No knowledge of partition theory is required. I will introduce all notions discussed. The representation theory is mentioned only as motivation and I will not discuss it further in the talk. (Joint work with Tewodros Amdeberhan and George Andrews.)

• 14 September: Adam Zsolt Wagner, WPI, "Title"
  Abstract:

• 21 September: Guillermo Nuñez Ponasso, WPI, "Title"
  Abstract:

• 28 September: Mason DiCicco, Department of Computer Science, WPI, "Expected length of the longest common subsequence"
  Abstract: Given two random binary sequences of length n, what is L(n), the expected length of their longest common subsequence? Chvátal and Sankoff (1975) proved that L(n) is asymptotically equal to γn for some constant γ (which we call the Chvátal–Sankoff constant). However, the exact value of γ is still unknown. (The best bounds are 0.788 < γ < 0.826 due to Lueker (2009).) In this talk I will describe the general method used to calculate upper bounds for γ.

• 5 October: Bill Martin, WPI, "Synchronization and designs in the symmetric group"
  Abstract: Entering the maze, you will be randomly placed in one of these eight rooms. The rooms all look identical to one another; each room has four exit doors: Red, Blue, Green, and White. The White door exiting Room 1 leads to safety while the White door in each other room leads to certain death. Can you find your way to safety?

  

  You don't know where you will start -- and you can't see what room you are in at any point in time -- yet you want to specify a word in the alphabet {R, B, G} which will bring you to Room 1: you want to be certain that, after you follow directions, choosing doors according to this word, you’ll finish in Room 1 and can safely walk through the white door. What's the synchronizing word?

  This talk will start and end with such puzzles, but will mainly deal with designs in association schemes. The classical motivating example is a collection of k-element subsets of [v] = {1, . . . , v} such that each t-element subset of [v] is contained in exactly one of them. A more recent analogue, still closely tied to classical ideas, is the concept of λ-transitive sets of permutations. This is based on joint work with Bruce Sagan [J. London Math. Soc., 2006] where we apply a coding theory approach to such collections of permutations using character theory. In the past 11 years, this concept of λ-transitive (or λ-homogeneous) sets of permutations has been applied by Araújo et al. to the study of synchronizing automata, which is where we started the talk!

• 12 October: No seminar
  

B TERM 2022

• Tuesdays 2:00-2:50pm, Room SH203, Stratton Hall



• 25 October: Bill Martin, WPI, "Ideals of strongly regular graphs and ETFs"
  Abstract:

• 1 November: Samuel Tripp, WPI, "Grid homology"
  Abstract: Knot Floer homology is a powerful suite of knot invariants introduced in the early 2000's. A few years later, this theory was made combinatorial in the form of grid homology, allowing for much greater computational ability. In this talk, we will introduce grid homology, then discuss potential ways to generalize grid homology to the study of tangles.

• 8 November: Adam Zsolt Wagner, WPI, "Title TBA"
  Abstract:

• 15 November: Nathan Uricchio, WPI, "Title TBA"
  Abstract:?

• 22 November: Oleg Karpenkov, University of Liverpool, "Title TBA"
  Abstract:?

• 29 November: Speaker?, "Title?"
  Abstract:?

• 6 December: Neranga Fernando, College of the Holy Cross, "Quandles, racks and shelves"
  Abstract: A quandle is a set X with a binary operation ∗ : X × X → X satisfying:
  1. For all x ∈ X, x ∗ x = x
  2. For all y ∈ X, the map β_y : X → X defined by β_y(x)= x ∗ y is invertible.
  3. For all x,y,z ∈ X, (x ∗ y) ∗ z = (x ∗ z) ∗ (y ∗ z).
  The three axioms of a quandle algebraically encode the three Reidemeister moves in knot theory.

  A rack is a set with a binary operation that satisfies (ii) and (iii), and a shelf is a set with a binary operation satisfying self-distributivity (iii).

  I will begin this talk by giving an introduction to quandles. I will then talk about racks, shelves and quandle rings. Moreover, I will talk about a recent joint work with Matthew Pradeep Goonewardena and Mohamed Elhamdadi on shelves.

• 13 December: No seminar?
  

D TERM 2022

• Wednesdays 2:00-2:50pm, Room SH308, Stratton Hall



• 16 March: Sheila Sundaram, Pierrepont School "Quasisymmetric functions, descent sets and 0-Hecke actions on tableaux"
  Zoom Meeting ID: 994 4731 7557
  Abstract: I will introduce all the terms in the title, and then survey various bases for the algebra of quasisymmetric functions, and their associated modules for the 0-Hecke algebra. I hope to make the talk self-contained, and time permitting, also hope to report on recent joint work with Elizabeth Niese, Stephanie van Willigenburg, Julianne Vega and Shiyun Wang.

• 23 March: Bill Martin, WPI "An introduction to the Paley graphs"
  Abstract: Let F_q be the finite field of prime power order q. The Paley graph P_q has vertex set F_q with a directed edge from a to b if b-a is a perfect square. I will describe the basic properties of these amazing graphs. For instance, the graph is undirected if and only if q ≡ 1 (mod 4). This is the case we focus on. Here, the graph is strongly regular, giving us one of the simplest examples of a non-trivial association scheme. We fully work out the parameters and eigenvalues of the Paley graph as preparation to focus on their pseudorandom properties.

  With Ethan Washock in Summer 2021, I was interested in collisions among entrywise products u ∘ v = u' ∘ v' of eigenvectors of the Paley graph and we knew our task would be easier if any three vertices of the graph have a common neighbor. (This is among the most elementary of the pseudorandom properties.) I got stuck on this and Andries Brouwer helped me past a hurdle. I'll explain how we used the Hasse bound on the number of q-rational points on an elliptic curve to estimate the number of vertices in the Paley graph at distance h from a, distance i from b, and distance j from c for any three vertices a,b,c. If time permits, I'll show how this relates to my project with Ethan.

  30 March: Bill Martin, WPI "Kantor's construction for mutually unbiased bases"
  Abstract: This talk introduces mutually unbiased bases; these are collections of measurements of finite-dimensional quantum mechanical systems which have numerous applications including quantum cryptography and quantum state tomography.

  Two unitary bases B and B' for ℂⁿ are unbiased relative to one another if the Hermitian inner product ❬b,b'❭ has constant modulus as b ranges over vectors in B and b' ranges over vectors in B'. A fundamental question in quantum information theory is "What is the maximum number of pairwise (or mutually) unbiased bases in ℂⁿ?" It is not hard to show that n+1 is an upper bound on the number of such bases and a collection of n+1 mutually unbiased bases ("MUBs") for ℂⁿ is said to be complete. Complete sets of MUBs are known whenever n is a prime power and in no other cases. In this talk, I will present a construction of complete sets of MUBs due to Bill Kantor. I will then discuss our attempt to extend this idea to non-prime-power dimensions. I will also mention some joint work with former WPI students on the real case.

• 6 April: Guillermo Nuñez Ponasso, WPI "Type II matrices in Association Schemes"
  Abstract: A Type II matrix is an n × n matrix M satisfying MM^(-) = n I_n, where M^(-) is the Schur inverse of M. These matrices are very interesting in Knot Theory, since some can be used to obtain link invariants. I will present some of the results by Chan and Godsil on the classification of Type II matrices on Strongly Regular Graphs, along with some subsequent work by Munemasa and Ikuta. Then I will present a new construction using the theory of cyclotomy.

• 13 April: Miklós Bóna, U. Florida "Superpatterns and superpermutations"
  Abstract: At least how long does a permutation have to be if it is to contain all patterns of length k? At least how long does a word over the alphabet {1,2,...,n} have to be if it is to contain all permutations as a subsequence. As a factor? These questions are easy to formulate, but surprisingly difficult to answer, even at the level of bounds. It is quite possible that for some of these questions, the best answers will come from constructions of geometric nature. No previous knowledge of the combinatorics of permutations or pattern avoidance will be assumed.

• 20 April: Jessica Wang, WPI "Exploring numerical semigroups through polyhedral geometry"
  Abstract: A numerical semigroup is a cofinite subset of the non-negative integers that is closed under addition and contains zero. The Group cone, C(ℤ_m), is a family of rational polyhedra whose congruent integer points are in bijection with numerical semigroups with fixed multiplity. Each face of C(ℤ_m) corresponds to a poset that describes the structure of the numerical semigroups found on that face. Interestingly, some faces of C(ℤ_m) do not have any integer points on them. In this talk, we present conditions to classify which faces of C(ℤ_m) contain integer points by examining their poset.

  Zoom Meeting ID: 952 4265 8134. For passcode, contact us.

• 27 April: Joseph Fehribach, WPI, "The Prime Number Theorem: an overview"
  Abstract: The prime number theorem is one of the most famous results in (analytic) number theory.

  This presentation is a 45-minute sketch of an analytic proof.

  Meeting ID: 952 4265 8134 Passcode + ZIP code: 483243

• Tuesdays 3:00-3:50pm, Room SL011, Salisbury Labs



• 18 January: No seminar
  

• 25 January: Bill Martin, WPI "A surprising duality property of scaffolds"
  Abstract: In this first part of the talk, we present some motivation and the necessary background to present (on February 1st) a proof by Liang, Tan, Tanaka and Wang of a special case of a conjecture I made in 2021 about planar scaffolds for association schemes. The proof is quite technical, involving character theory of finite abelian groups and duality of circular planar graphs.

  This preparatory talk will review association schemes, important families of examples such as finite groups and distance-transitive graphs, and the structure of Bose-Mesner algebras. Then we will define scaffolds, review important examples, and present Martin's conjecture (Linear Algebra and its Applications, 2021).

  Let X be a finite non-empty set and let Mat_X(ℂ) denote the algebra of matrices with rows and columns indexed by the elements of X. Let G=(V(G),E(G)) be a finite digraph with some specified ordered set R ={r₁, . . . ,r_m}⊆ V(G) of "root nodes" and let w: E(G) → Mat_X(ℂ) assign a matric weight to each directed edge of G. Then the scaffold S(G,R;w) is defined to be the sum over all φ :V(G) → X of the tensor φ(r₁) ⊗ ⋯ ⊗ φ(r_m) weighted by the product of all w(e)_φ(a),φ(b) over directed edges e=(a,b) in E(G). While this seems like a mouthful, it captures a number of very natural enumerations of substructures. So the first part will end with examples of scaffolds and their evaluation on coherent algebras and Bose-Mesner algebras.

• 1 February: Rafael Gonzalez D'Leon, Pontificia Universidad Javeriana "Mathematical coincidences: Euler, Catalan, and RNA folding"
  Abstract: Posted elsewhere.

• 8 February: Bill Martin, WPI "A surprising duality property of scaffolds" (continued)
  Abstract: We continue the presentation from January 25, aiming to sketch the proof of the new result of Tan, et al.

• 15 February: Duncan Wright, WPI "Putting Errors First -- A Graph-Theoretic Approach to Quantum Error Correction"
  Abstract: We investigate a novel class of quantum error correcting codes to correct errors on both qubits and higher-level quantum systems represented as qudits, and we develop a graph-theoretic representation for both an arbitrary error set and this new class of reflexive stabilizer codes. In this new framework, we represent the algebraic conditions for error correction in terms of edge avoidance between graphs providing a visual representation of the interplay between errors and error correcting codes. Most importantly, this framework supports the development of quantum codes that correct against a predetermined set of errors, in contrast to current methods. A heuristic algorithm is presented, providing steps to develop codes that correct against an arbitrary noisy channel. We benchmark the correction capability of reflexive stabilizer codes for the case of single qubit errors by comparison to existing stabilizer codes that are widely used. In addition, we present two instances of optimal encodings: a minimal encoding for single qudit errors on a four-state system, and an optimal encoding for fully correlated noise which achieves a higher encoding rate than previously known. Joint work with Robert Vandermolen.

• 22 February: Jessica Wang, WPI "Tiling of Prime and Composite of Kirchhoff Graphs"
  Abstract: A Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. We present an algorithm that constructs all Kirchhoff graphs up to a fixed edge multiplicity. We explore the tiling of prime Kirchhoff graphs, specifically, the number of possible prime Kirchhoff graphs given a set of initial fundamental Kirchhoff graphs.

• 1 March: Guillermo Nuñez Ponasso, WPI "Small sums of roots of unity"
  Abstract: Consider a sum of n k-th roots of unity. How small can its absolute value be? We study this problem from different points of view and give bounds using ideas from Diophantine approximation. For the case k=5 we present a novel upper bound involving Lucas numbers. Conjecturally this explains the whole behaviour of minimal-norm sums for the 5^th roots of unity.

Future Term

Previous Semesters

• Tuesdays 3:00-3:50pm, Room SL402, Salisbury Labs



• 26 October: Michael Simkin, Harvard "The number of n-queens configurations"
  Abstract: The n-queens problem is to determine 𝒬(n), the number of ways to place n mutually non-threatening queens on an n×n board. We show that there exists a constant α= 1.942 ± 3 ×10^-3 such that 𝒬(n) = ((1 ± o(1))ne^-α)ⁿ. The constant α is characterized as the solution to a convex optimization problem in 𝒫([-1/2,1/2]²), the space of Borel probability measures on the square.

  The chief innovation is the introduction of limit objects for n-queens configurations, which we call queenons. These are a convex set in 𝒫([-1/2,1/2]²). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.

• 2 November: No seminar
  

• 9 November: Guillermo Nuñez Ponasso, WPI "The Hasse-Minkowski Theorem in Combinatorics"
  Abstract: The Hasse-Minkowski theorem states that given a quadratic form f with rational coefficients, f has rational zeroes if and only if f has zeroes in every completion of the rationals. This result can be used to characterize quadratic forms on the rationals up to equivalence.

  In combinatorics, objects such as projective planes or designs can be characterized by a matric equation satisfied by the Gram matrix of their incidence matrix. Since this Gram matrix is symmetric, it has an associated quadratic form and the Hasse-Minkowski theorem applies. In this talk we will go through the basic theory of local fields and quadratic forms, and explain how the Hasse-Minkowski theorem is applied to obtain non-existence results in combinatorics, such as the Bruck-Ryser-Chowla theorem.

• 16 November: Brendan Rooney, RIT "Combinatorial Orthogonality and the Inverse Eigenvalue Problem for Graphs"
  Abstract: The inverse eigenvalue problem for graphs asks: given a graph G, what spectra are realizable from its vertex and edge-weightings? The parameter q(G) is the smallest number of distinct eigenvalues over all matrices M compatible with G (i.e., the off-diagonal zero pattern of M is the same as A(G)).

  Two vectors are combinatorially orthogonal if the size of the intersection of their supports is not 1. An n×n symmetric matrix is combinatorially orthogonal if every pair of rows, or columns, is combinatorially orthogonal. Every orthogonal pair of vectors is combinatorially orthogonal, and every orthogonal matrix is combinatorially orthogonal.

  For a graph G, we give a simple structural condition that guarantees the existence of a combinatorially orthogonal matrix M compatible with G. We will see how this connects with work done by Reid and Thomassen on graphs for which every path of length r is contained in a cycle of length s. Finally we discuss implications for characterizing graphs G with q(G)=2.

• 23 November: Thanksgiving Week No seminar.
  

• 30 November: Brigitte Servatius, WPI
  "Chebychev said, and I say it again:
  There is always a prime between n and 2n."
  Abstract: As an "advertisement" of Chvatal's new book : "The discrete mathematical charms of Paul Erdos" we will present Paul Erdos' proof of Bertrand's Postulate and compare it to earlier proofs, as laid out in the first chapter of Chvatal's book.

• 7 December: Nikolaos Kalampalikis, WPI "A graph theoretic proof for the Sensitivity Conjecture"
  Abstract: The Sensitivity Conjecture has been important problem in theoretical computer science. In this presentation, we will go over Huang's proof of showing that every (2^n-1 +1)-vertex induced subgraph of the n-dimensional cube graph has maximum degree of at least √n. As a direct consequence we will show that sensitivity and degree of a boolean function are polynomially related.

A TERM 2021

• Mondays 2:00-2:50pm, in Room 309 Stratton Hall

  
  

• 30 August: Bill Martin, WPI "Strongly regular graphs and spherical designs"
  Abstract: I will give a basic introduction to these two topics we have been studying recently. A strongly regular graph is a regular graph with three distinct eigenvalues. A spherical t-design is a finite subset of the d-dimensional unit sphere which approximates the entire sphere in the sense that the corresponding Riemann sum is exactly equal to the integral of f(x) over the sphere for any polynomial f(x) of degree at most t in d variables.

• 6 September: No seminar, Labor Day

• 13 September: Benjamin Gobler, WPI "Listing the Rationals using Continued Fractions"
  Abstract: It is well known that the rational numbers are countable. From a list which includes each rational number exactly once, we may ask, "What is the 200th rational in the list?" or "Where does 22/7 appear in the list?" To answer these questions, we will explore an original method which uses continued fractions to evaluate and locate terms in the Calkin-Wilf sequence, one such list of the rationals.

• 20 September: Padraig Ó Catháin, WPI "Fischer's proof of Fischer's Inequality"
  Abstract: Fischer's Inequality is a standard tool for working with positive definite matrices. In many textbooks (and on Wikipedia) there is a short proof using the square root of a positive definite matrix and the AGM inequality. The original proof is entirely different, and I will present it in its entirety.

• 27 September: Ashwin Sah, MIT "Large deviations in random Latin squares"
  (This talk will be given over Zoom. Please contact Bill Martin if you wish to receive the Zoom Meeting ID.)
  Abstract: We study large deviations of the number N of intercalates (2 x 2 combinatorial subsquares which are themselves Latin squares) in a random n x n Latin square. In particular, for constant δ > 0 we prove that Pr(N ≤ (1-δ)n²/4 )≤ exp(-Ω(n²)) and Pr(N ≥ (1+δ)n²/4 )≤ exp(-Ω(n^4/3(log n)^2/3)) both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-n Latin square has (1+o(1))n²/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.

  This work is joint with Matthew Kwan and Mehtaab Sawhney.

• 4 October: Mason DiCicco, WPI "The Communication Complexity of Subsequence Detection"
  Abstract: The subsequence detection problem is, given a string of length n and a pattern of length k < n, to determine whether the pattern appears in the string as a (not-necessarily contiguous) subsequence. I will give an introduction to the study of Communication Complexity, and prove several bounds with respect to the subsequence detection problem.

• 11 October: No seminar.