Date of Award
Fall 2025
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Joshua Cooper
Abstract
We investigate the combinatorial properties of the characteristic polynomial $\phi_\mathcal{H}\ev{t}$ of a hypergraph $\mathcal{H}$, in particular, its coefficients. Due to a classical result of Jacobi, the generating function of closed walks at a vertex $u$ in a graph $G$ is determined by the rational function $\phi_{G-u}(t) / \phi_G(t)$. The connection between closed walks of $G$ and its characteristic polynomial has a known elegant proof via an application of Viennot's Heaps of Pieces framework, where cycles are taken as pieces and the concurrence relation is sharing a vertex. Here, we prove a bijection between heaps with a unique maximal piece containing $u$ and closed walks at $u$; thereby making some informal references in the literature precise.
Next, we generalize some of the theory to hypergraphs: The Harary-Sachs Theorem for hypergraphs expresses the coefficients of $\phi_\mathcal{H}\ev{t}$ in terms of certain substructures, called ``infragraphs'' of $\mathcal{H}$. We derive a version of Kocay's Lemma, which allows an interpretation of $\phi_\mathcal{H}\ev{t}$ in the language of Heaps of Pieces framework, where connected infragraphs are taken as pieces, with the same concurrence relation: sharing a vertex. Next, we establish an identity relating the Martin polynomial of a digraph $D$ to the collection of chromatic polynomials obtained from the vertex intersection graphs of partitions of $D$ into cycles. As a corollary of this identity, we derive a cancellation property: Unless an Eulerian digraph $D$ is a directed cycle, it satisfies $\sum_{k\geq 1} (-1)^{k} f_k(D)=0 $, where $f_k(D)$ is the number of partitions of Eulerian circuits of $D$ into $k$ circuits. As an application, this cancellation property is used to deduce the Harary-Sachs Theorem for graphs from the hypergraph generalization thereof.
In the next chapter, we characterize Eulerian multigraphs with a unique partition into cycles, as well as digraphs with a unique Eulerian circuit. An Eulerian multigraph has a unique partition into cycles if and only if it belongs to the family $\mathcal{S}$, ``bridgeless cactus multigraphs'', that are obtained by replacing every edge of a tree with a cycle of length $\geq 2$. Furthermore, for a digraph $D$, we list conditions equivalent to having a unique Eulerian circuit, thereby generalizing a result of Arratia-Bollob\'{a}s-Sorkin. In particular, digraphs with a unique Eulerian circuit constitute a subfamily of $\mathcal{S}$, called ``Christmas cactus digraphs''.
In the final chapter, we establish that the characteristic polynomial of a $3$-uniform hypergraph is not determined by its ``polynomial deck'', the multiset of characteristic polynomials of its vertex-deleted subgraphs, thus settling the ``polynomial reconstruction problem'' for hypergraphs in the negative. The proof proceeds by showing that a construction due to Kocay of an infinite family of non-isomorphic pairs of $3$-uniform hypergraphs with the same vertex deck, in fact, have different principal eigenvalues, and so, different characteristic polynomials. The question remains unresolved for ordinary graphs.
Rights
© 2025, Utku Okur
Recommended Citation
Okur, U.(2025). Coefficients of the Characteristic Polynomial of a Hypergraph and Their Combinatorial Properties. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/8621