DCUCD Discrete Mathematics Seminar Series

Speaker: Cian O'Brien (MIC)

Title: The Bruhat order for Latin squares

(Based on joint work with Angela Carnevale, University of Galway)

Abstract: Alternating sign matrices arise naturally as a generalisation of permutation matrices in a number of different contexts. For example, they are the unique minimal lattice extension of the permutation matrices under the Bruhat order. In 2018, Brualdi and Dahl defined alternating sign hypermatrices, a 3-dimensional analogue of alternating sign matrices. Latin squares can be thought of as the 3-dimensional analogue of permutation matrices, since the positions of each of the n symbols in an n×n Latin square correspond to the non-zero entries in some n×n permutation matrix.

We have extended this idea further, by defining the Bruhat order for Latin squares and studying the resulting poset. This talk presents current work relating to this poset, including 3-dimensional analogues of related combinatorial objects, inversions and the Bruhat rank of a Latin square, a lattice extension of the Latin square poset, and a description of the elements in the resulting lattice.

Speaker: Beatriz Barbero Lucas (UCD)

Title: New quantum codes from Generalized Monomial-Cartesian Codes

Abstract: Quantum computers are a great tool to attack some intractable problems for classical computers, such as the prime factorization problem. However, quantum computer implementations have higher error rates than classical computers, making reliability a challenge. That is where quantum error correction codes come into play. In the first part of this talk I will explain how to construct Monomial-Cartesian codes and explain a generalization that we introduced in our paper in order to obtain new quantum error correction codes. I will also make a brief description of their good properties. This is a joint work with Fernando Hernando, Helena Martín-Cruz, Gary McGuire.

Speaker: Derek Kitson (MIC)

Title: d-dimensional algebraic connectivity

Abstract: The well-studied algebraic connectivity of a graph G is the second smallest eigenvalue of its Laplacian matrix (counting multiplicity). A graph is connected if and only if it has positive algebraic connectivity. Embedding the vertices of G in a d-dimensional normed space X we obtain a bar-joint framework and its accompanying framework Laplacian (or "stiffness matrix"). The framework is infinitesimally rigid if and only if the k+1 smallest eigenvalue of its framework Laplacian is positive, where k is the dimension of the isometry group for X. Taking the supremum of this set of eigenvalues over the set of all possible embeddings of G into X we obtain a d-dimensional variant of algebraic connectivity for the graph G. This quantity can be regarded as a measure of the graph's rigidity in X. We will survey recent results on d-dimensional algebraic connectivity and present some new results for rigid graphs in lp spaces. This is joint work with James Cruickshank and Sean Dewar.

 Speaker: John Sheekey (UCD)

Title: A guided tour through Finite Incidence Geometry with Pretty Pictures

Abstract: Many topics in combinatorics have arisen as generalisations of concepts in geometry; in particular, arrangements of points and lines with special properties. We throw away all information except incidence, viewing lines simply as sets of points. The addition of various additional properties leads to a rich variety of combinatorial and geometric object; configurations, projective and affine planes, generalised quadrangles, polar spaces, and so on.

In this talk we will take a tour through this landscape, touching on constructions, classifications, and pleasing pictures. We will pay special attention to the notions of "duality" and "polarity", covering well-known classifications in classical projective planes, and less well-known analogues in more general structures.

 Speaker: Padraig Ó Catháin (DCU)

Title: Constructing Legendre-type sequences with less finite geometry

Abstract: A binary sequence of prime length p, having j^th entry +1 if j is a quadratic residue and -1 otherwise has the remarkable property that all its non-trivial autocorrelations have the constant value -1. This is the smallest absolute value possible since the length of the sequence is odd. Such Legendre sequences find application throughout mathematics, but few other constructions are known. 

A recent paper of Jedwab & Pender gives new constructions of  sequences which can be used to build certain quaternary Hadamard matrices. We will focus on new proofs that they give for constructions of Legendre-type sequences which were previously obtained by Whiteman, by Turyn and by Goethal-Seidel, through methods described as difficult and rather opaque. The new proofs do away with finite geometry and rely on the algebra of 2x2 matrices over a finite field. 

 Speaker: Mark Dukes (UCD)

Title: On ascent sequences and Fishburn structures

Abstract: Let a=(a_1,a_2,...,a_n) be a sequence of nonnegative integers. An ascent in the sequence a is an index k for which the entry at position k is less than the entry at position k+1. An ascent sequence is a sequence of non-negative integers that begins with zero and in which every entry is bounded by one more than the number of ascents preceding it. These sequences were introduced by Bousquet-Melou, Claesson, Dukes and Kitaev (2010) and enjoy a rich collection of properties. In particular, they uniquely encode a variety of combinatorial structures that have become known as Fishburn structures. These include Fishburn permutations, (2+2)-free posets, a class of integer matrices that have since become known as Fishburn matrices, and Stoimenow matchings. This talk will present an overview of several different aspects of these connections.

 Speaker: Rakhi Pratihar (Centre de Recherche Inria de Saclay, France)

Title: Generalizing shellable complexes and matroids

Abstract: Shellability is an important notion having interesting applications in combinatorics, commutative algebra, and algebraic topology. Historically, introduced to prove the Euler-Poincaré formula for higher-dimensional convex polytopes, the notion of shellability has been extended to more general structures, for instance, (non)pure simplicial complexes, multicomplexes and q-complexes. Moreover, much of the topological properties is retained for the shellable structures in these more general settings. For example, order complexes of shellable simplicial complexes, shellable multicomplexes as well as shellable q-complexes are weak homotopy equivalent to wedge sum of spheres and thus their (singular) homology groups are well understood. There are important classes of shellable complexes associated to matroids; the independence complex, the broken circuit complex, the order complex of lattice of flats. On the other hand, classical matroids have been generalized in many ways – (discrete) polymatroids, (sum) (q)-(poly)matroids and the independent sets (resp. spaces) of discrete polymatroids (resp. q-(poly)matroids) form shellable multicomplexes (resp. q-complexes).

This talk discusses a unifying lattice framework to study shellability for complexes (we call them P-complexes) in power lattices that brings the Boolean lattices, (Cartesian products of ) subspaces lattices, lattices of multiset subsets under one umbrella. We will see that order complexes of shellable P-complexes are shellable simplicial complexes, extending the known results for simplicial (multi)complexes and q-complexes. A non-trivial class of shellable P-complexes are obtained from the independent sets of matroids in power lattices, which we define to generalize (sum)(q)-(poly)matroids. We will see a construction of matroids in lattices of multiset subsets from weighted graphs. As an application to commutative algebra, I will discuss Stanley-Reisner rings associated to multicomplexes and their sequential Cohen-Macaulayness.

This talk is based on a joint work with Tovohery H. Randrianarisoa and Klara Stokes.

Speaker: Andrew Fulcher (UCD)

Title: The free product of q-matroids and nested q-matroids

Abstract: Matroids give an abstraction of the notion of linear independence. One type of machinery developed on matroids comprises the binary operations direct sum and free product. Both of these operations are methods for structural analyses of matroids. One of the structural analyses related to the free product is nested matroids, which are simpler objects that have been shown to form a basis for (a free module of) all matroids. 

Several generalisations of matroids have so far been developed. One of which is the q-matroid. While a matroid is defined on a Boolean lattice, a q-matroid is defined on a complemented modular lattice. Consequently, numerous interesting difficulties arise. q-Matroids have garnered attention recently in information theory and coding theory.

In this talk, a generalisation of the free product, such that it applies to q-matroids, will be presented. A large part of this definition is algebraic in nature, however, we have shown that the cyclic flats of a q-matroid provide a very intuitive (and possibly very fruitful) characterisation of the free product. On this note, some discussion of the notion of nested q-matroids will be given.

This is joint work with Gianira Alfarano and Eimear Byrne.

Speaker: Ronan Egan (DCU)

Title: Hadamard matrices of centraliser algebras of monomial representations

Abstract: An orthogonal matrix with complex entries all of norm 1 is a (complex) Hadamard matrix. The term Hadamard matrix more commonly refers to the special case where the entries are all real, i.e., are either 1 or -1. These are known only to exist when the order is 1, 2, or a multiple of 4, and it is a longstanding open conjecture that this condition is sufficient. Despite this being unresolved, it appears that even up to equivalence, at permissible orders the number of (real) Hadamard matrices appears to grow exponentially with the order, and classifications even at relatively small orders seem computationally infeasible. This motivates the restriction to matrices with additional algebraic structure, such as group developed and cocyclic matrices. Our goal is to develop computational machinery to construct and classify Hadamard matrices acted upon by some assumed automorphism group.

Motivated by pioneering work of D. G. Higman, in this talk we will summarise and extend results on monomial group representations and their centraliser algebras.  We will locate the theory of group developed and cocyclic Hadamard matrices within the study of such representations. We will see how we can apply techniques of computational algebra to search for complex Hadamard matrices in the centraliser of a monomial representation. The problem can be translated into one where we need to solve a system of polynomials, for which we use Groebner basis techniques. Under the conditions we impose, this is feasible up to very high orders. The talk will be furnished with illustrative examples and computational results.

This is joint work with Santiago Barrera Acevedo, Heiko Dietrich and Padraig Ó Catháin.

Speaker: Patrick Browne (TUS)

Title: Erdős–Ko–Rado type problems in root systems 

Abstract: Given a Lie algebra, two roots are said to be strongly orthogonal if neither their sum nor difference is a root. In this talk, we investigate sets of mutually strongly orthogonal roots. In particular, those such that any two such sets have the property that the difference between their sums can itself be expressed as the sum of a strongly orthogonal set of roots. We discuss this property and its relationship to Erdős–Ko–Rado type problems and finally discuss applications in terms of the existence of finite projective planes of certain orders. This is joint work with Qëndrim R. Gashi, University of Prishtina and  P Ó Catháin at DCU. 

Speaker: Lukas Klawuhn (Paderborn)

Title: Why everyone should know association schemes: An introduction to Delsarte Theory

Abstract: Interesting combinatorial structures can often be characterised as special subsets of association schemes. In his PhD thesis, Philippe Delsarte developed powerful linear programming techniques to prove non-existence and uniqueness results for such structures. Ideas of this type were fundamental in the work for which Marina Viazovska was awarded the Fields medal in 2022. This talk will begin with an overview of Delsarte theory. 

The association scheme of the symmetric group is well known. We will introduce it, and then study generalised permutations. They act on the set {1,2,...,n}, whose elements are coloured with one of r possible colours. We consider different notions of transitivity and interpret these algebraically in the appropriate association scheme . We will give existence results showing that there exist transitive sets of generalised permutations that are small compared to the size of the group. Many of these results extend results previously known for the symmetric group.

No particular knowledge of association schemes will be required to appreciate this talk. 

Speaker: Alena Ernst (Paderborn)

Title: Designs in finite general linear groups 

Abstract: It is known that the notion of a transitive subgroup of a permutation group G extends naturally to subsets of G.  It turns out that transitive subsets of the symmetric group give a combinatorial interpretation of the rather algebraic Delsarte T-designs in the corresponding association scheme. In this talk we give an overview of results known for the symmetric group and discuss a q-analog setting: we characterise Delsarte T-designs in the finite general linear group GL(n,q) in terms of subsets of GL(n,q) acting transitively on flag-like structures. 

Speaker: Daniel Hawtin (Rijeka)

Title:  Packings of spreads and designs in projective spaces

Abstract: A (line-)spread of a projective space is a set of lines of the space that induce a partition of the point set. One generalisation of this is the q-analogue of a design. A t-fold packing of a projective space is a collection P of spreads such that each line is contained in precisely t of the spreads in P. Similar concepts have been investigated for designs. We will discuss some of the history of t-fold packings, and their generalisations, and some applications in graph theory and coding theory. We also present some recent results regarding (q-1)-fold packings in odd dimensional projective spaces over GF(q), where q is a power of 2, and in infinite dimensional projective spaces.

Speaker: Andrew Fulcher (UCD)

Title: The cyclic flats of L-polymatroids

Abstract: In recent years, q-polymatroids have drawn interest because of their connection with rank-metric codes. For a special class of q-polymatroids called q-matroids, the fundamental notion of a cyclic flat has been developed as a way to identify the key structural features of a q-matroid. In this talk, we will see a generalisation of the definition of a cyclic flat that can apply to q-polymatroids, as well as a further generalisation, L-polymatroids. The cyclic flats of an L-polymatroid is essentially a reduction of the data of an L-polymatroid such that the L-polymatroid can be retrieved from its cyclic flats. As such, in matroid theory, cyclic flats have been used to characterise numerous invariants.

Speaker: Padraig Ó Catháin (DCU)

Title: Sequencing of Steiner Triple Systems

Abstract: A Steiner Triple System (STS) on the set {1, 2, ..., v} is a collection of blocks (subsets) of size three, such that each pair is contained in a unique block. Over the past few years, applications to problems in data storage suggested the problem of finding STSs such that no block is contained in a short interval of consecutive integers. With Daniel Horsley, we found the optimal bounds for this question (up to some log factors). In this talk, I'll give all the necessary background and explain why a naive application of the Lovasz Local Lemma fails for this problem, but a two-step version works surprisingly well.