Delaware Miniworkshop on Discrete Mathematics

This half-day miniworkshop features four talks on the topics of coding theory, finite geometry, and graph theory.

Time | Location: May 8, 1:30PM -- 5:00PM | Ewing Hall 205, University of Delaware

Speakers:

Sam Adriaensen (Vrije Universiteit Brussel & Worcester Polytechnic Institute)

Alice M. W. Hui (Clemson University)

Shuxing Li (University of Delaware)

Ralihe R. Villagrán (Worcester Polytechnic Institute)

Organizers: Sebastian Cioabǎ, Robert Coulter, and Shuxing Li

Program:

1:30 -- 2:10, Shuxing Li, University of Delaware, joint work with Maosheng Xiong and Haode Yan.

Counting Fearlessly and Meticulously: Weight Distribution of Cyclic Codes with Generalized Niho-type Nonzeroes

Determining the minimum Hamming distance of an error-correcting code C has long stood as a fundamental challenge in coding theory. In this talk, we turn our attention to an even more ambitious problem: determining the full weight distribution of C. This means counting the number of codewords in C of each possible Hamming weight—an essential but notoriously difficult task, especially for general codes.

While computing the weight distribution for an arbitrary code remains largely out of reach, the problem becomes more tractable under additional structural assumptions. Specifically, if the code C is cyclic, one can follow a well-established approach to reduce the problem to the number-theoretic task of evaluating certain exponential sums.

In this talk, we focus on a family of cyclic codes characterized by generalized Niho-type nonzeroes. For these codes, we succeed in determining the value distribution of the associated exponential sums through a process of fearless and meticulous counting. Our approach draws upon a rich toolkit of mathematical ingredients, including exponential sums, elementary symmetric polynomials, binary Zetterberg codes, and the analysis of Vandermonde-like homogeneous linear systems.

2:20 -- 3:00, Alice M. W. Hui, Clemson University, joint work with Susan Barwick and Wen-Ai Jackson.

Inherited conics in Non-Desarguesian Planes

A k-arc in a projective plane of order q is a set of k points, no three of which are collinear. An arc has an upper bound of q+1 points if q is odd, and q+2 points if q is even.  A (q+1)-arc is referred to as an oval, with the classical example being a non-degenerate conic in the Desarguesian projective plane PG(2,q). While ovals in PG(2,q) have been studied for decades, though not classified, their behavior in non-Desarguesian settings remains a rich area of investigation. This talk explores arcs and ovals in non-Desarguesian planes, with particular focus those on André planes, which arise from PG(2,q) through André replacement, a generalized derivation process. We will examine how conics behave under this replacement and discuss conditions for their inheritance.

3:00 -- 3:20, break

3:20 -- 4:00, Sam Adriaensen, Vrije Universiteit Brussel & Worcester Polytechnic Institute, joint work with William J. Martin.

Possible automorphisms of Conway's infamous 99-graph

John Conway asked the following question:

Does there exist a graph on 99 vertices such that each edge is in a unique triangle, and each non-edge is a diagonal of a unique quadrangle?

He even awarded 1000$ for its resolution. It has been proven that if such a graph exists, it cannot have a lot of symmetries. The order of its automorphism group must divide either 6 or 27. We refine the result by proving that the automorphism group cannot have a subgroup of order 9. We conclude that its order must divide 6.

4:10 -- 4:50, Ralihe R. Villagrán, Worcester Polytechnic Institute, joint work with C. A. Alfaro, J. P. Serrano, and T. I. Hoekstra-Mendoza.

The Characterization of Graphs with Two Trivial Distance Ideals

The distance ideals of a graph are algebraic invariants associated with its distance matrix. In particular, through the distance ideals of a given graph, we can describe the Smith normal form (SNF) of any of its diagonal weighted distance matrices.

In our work, we characterize the set of all graphs with at most two trivial distance ideals. We prove that these graphs can be characterized by a set of forbidden induced subgraphs, including well-known small graphs such as the bull graph, and by the infinite set of all cycles with odd length greater than 5. 

There are important connections between this family and, for example, the distance-hereditary graphs, perfect graphs, and the 3-leaf power graphs. On the other hand, we also find that every invariant factor, except for the first and second, of bipartite graphs are even numbers, suggesting that the Graham-Pollak-Lovász formula $\det(D(T_{n+1})) = (-1)^n n 2^{n-1}$ and the Hou-Woo result stating that $\text{SNF}(D(T_{n+1})) = I_2 \oplus 2I_{n-2} \oplus (2n)$ for any tree $T_{n+1}$ with $n+1$ vertices, can be extended.