Search

It is possible to completely describe the representation of any integer by binary quadratic forms of a given discriminant when the discriminant’s class group is a Boolean group (also known as an elementary abelian 2-group). For other discriminants, we can partially describe the representation using the structure of the class group. The goal of the present project is to find whether any class group with 32 elements and a primitive positive definite discriminant is a Boolean group. We find that no such class group is Boolean.

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the internal structure of these graphs, and prove that asteroidal quadruples may provide diameter bounds. Then, we extend the notion of polarity to dominating targets by defining the concept of polar targets. We investigate dominating targets in cycle graphs and show that they cannot have polar targets. Then, we provide a sufficient condition for a graph to have a polar target of size 3. Advisor: Andrew J. Radcliffe

We consider how the domination number of an undirected graph changes on the removal of a maximal matching. It is straightforward that there are graphs where no matching removal increases the domination number, and where some matching removal doubles the domination number. We show that in a nontrivial tree there is always a matching removal that increases the domination number; and if a graph has domination number at least $2$ there is always a maximal matching removal that does not double the domination number. We show that these results are sharp and discuss related questions.

An SLₖ-frieze is a bi-infinite array of integers where adjacent entries satisfy a certain diamond rule. SL₂-friezes were introduced and studied by Conway and Coxeter. Later, these were generalized to infinite matrix-like structures called tilings as well as higher values of k. A recent paper by Short showed a bijection between bi-infinite paths of reduced rationals in the Farey graph and SL₂-tilings. We extend this result to higher kby constructing a bijection between SLₖ-tilings and certain pairs of bi-infinite strips of vectors in ℤᵏ called paths. The key ingredient in the proof is the relation to Plucker friezes and Grassmannian cluster algebras. As an application, we obtain results about periodicity, duality, and positivity for tilings.

Polyhedral cones are of interest in many fields, like geometry and optimization. A simple, yet fundamental question we may ask about a cone is how large it is. As cones are unbounded, we consider their solid angle measure: the proportion of space that they occupy. Beyond dimension three, definitive formulas for this measure are unknown. Consequently, devising methods to estimate this quantity is imperative. In this dissertation, we endeavor to enhance our understanding of solid angle measures and provide valuable insights into the efficacy of various approximation techniques. Ribando and Aomoto independently discovered a Taylor series formula for solid angle measures of certain simplicial cones. Leveraging Brion--Vergne Decomposition, we extend their findings, devising an algorithm for approximating solid angle measures of polyhedral cones, including those where the series is not applicable. We compare our method to other estimation techniques, and explore the practical applications of these methods within optimization. Gomory and Johnson established the use of facets of master cyclic group polyhedra to derive cuts for integer programs. Within this framework, the size of the solid angle subtended by a facet determines its importance. We apply various approximation techniques to measure facet importance, provide computational results, and discuss their implications.

In some sense, chemical graph theory applies graph theory to various physical sciences. This interdisciplinary field has significant applications to structure property relationships, as well as mathematical modeling. In particular, we focus on two important indices widely used in chemical graph theory, the Merrifield-Simmons index and Hosoya index. The Merrifield-Simmons index and the Hosoya index are two well-known topological indices used in mathematical chemistry for characterizing specific properties of chemical compounds. Substantial research has been done on the two indices in terms of enumerative problems and extremal questions. In this thesis, we survey known extremal results and consider the generalized version of both topological indices.

We consider the use of combinatorics to solve representation theory problems. We looked closely at Kronecker Coefficients and the Tensor Square Conjecture, with different conjec- tures that spiral from it. Li came up with a conjecture that progresses on the Saxl Con- jecture, and we came up with a conjecture that progresses on Li’s Conjecture. We verified the Tensor Square Conjecture for a number of partitions, and examined patterns for the partitions that satisfied this conjecture.

Several measures of vulnerability of a graph look at how easy it is to disrupt the network by removing/disabling vertices. As graph-theoretical parameters, they treat all vertices alike: each vertex is equally important. For example, the integrity parameter considers the number of vertices removed and the maximum number of vertices in a component that remains. We consider the generalization of these measures of vulnerability to weighted vertices in order to better model real-world applications. In particular, we investigate bounds on the weighted versions of connectivity and integrity, when polynomial algorithms for computation exist, and other characteristics of the generalized measures.

The changes in computing paradigms to shift computations to third parties have resulted in the necessity of these computations to be provable. Zero-knowledge arguments are probabilistic arguments that are used to to verify computations without secret data being leaked to the verifying party. In this dissertation, we study zero-knowledge arguments with specific focus on reductions. Our main contributions are: Provide a thorough survey in a variety of zero-knowledge techniques and protocols. Prove various results of reductions that can be used to study interactive protocols in terms of subroutines. Additionally, we identify an issue in the analogous definition of zero-knowledge for reductions. We propose a potential solution to this issue. Design a novel matrix multiplication protocol based on reductions. Design protocols for arithmetic of fixed-point values of fixed-length.

Mixed-integer optimization problems (MIPs) pose a class of challenges crucial to a range of real-world applications, from space exploration to healthcare. Traditional approaches to solving MIPs have predominantly focused on identifying a single optimal solution, neglecting the considerable advantages of generating a Diverse Rashomon set—a set of diverse near-optimal solutions. This dissertation aims to bridge the gap between conventional optimization methods and emerging machine learning paradigms, thereby significantly enhancing both the speed and diversity of near-optimal solution sets in MIPs. The first part of the dissertation introduces an innovative approach for incorporating diversity into node selection within a branch-and-bound framework. Experimental results indicate that our method surpasses conventional node selection rules, such as best-first search, achieving diversity improvements ranging from 12\% to 190\%. This portion of the work elucidates the branch-and-bound tree exploration techniques that emphasize diversity during the MIP-solving process. The second part of the dissertation adopts graph neural networks (GNNs) to further accelerate and diversify the generation of near-optimal solutions. The research establishes that traditional methods follow a sequential node-by-node exploration to solve and generate near-optimal solutions for MIPs. Given the expansive solution space typically associated with MIPs, this sequential approach falls short of covering the near-optimal solution landscape adequately. To overcome this limitation, we employ machine learning in the form of generative models trained to produce near-optimal solutions across the entire solution space. In both segments of the dissertation, the merits of generating a Diverse Rashomon set—a collection of diverse near-optimal solutions—are discussed. Such a set offers a robust ensemble of solutions applicable to various domains. Finally, the dissertation rigorously tests the proposed methods against state-of-the-art techniques and reports superior results.

Attempts at approaching the well-known and difficult problem of constructing Ramsey graphs via machine learning lead to another difficult problem posed by Zykov in 1963 (now commonly referred to as the Trahtenbrot-Zykov problem): For which graphs F does there exist some graph G such that the neighborhood of every vertex in G induces a subgraph isomorphic to F? Chapter 1 provides a brief introduction to graph theory. Chapter 2 introduces Ramsey theory for graphs. Chapter 3 details a reinforcement learning implementation for Ramsey graph construction. The implementation is based on board game software, specifically the AlphaZero program and its success learning to play games from scratch. The chapter ends with a description of how computing challenges naturally shifted the project towards the Trahtenbrot-Zykov problem. Chapter 3 also includes recommendations for continuing the project and attempting to overcome these challenges. Chapter 4 defines the Trahtenbrot-Zykov problem and outlines its history, including proofs of results omitted from their original papers. This chapter also contains a program for constructing graphs with all neighborhood-induced subgraphs isomorphic to a given graph F. The end of Chapter 4 presents constructions from the program when F is a Ramsey graph. Constructing such graphs is a non-trivial task, as Bulitko proved in 1973 that the Trahtenbrot-Zykov problem is undecidable. Chapter 5 is a translation from Russian to English of this famous result, a proof not previously available in English. Chapter 6 introduces Cayley graphs and their relationship to the Trahtenbrot-Zykov problem. The chapter ends with constructions of Cayley graphs Γ in which the neighborhood of every vertex of Γ induces a subgraph isomorphic to a given Ramsey graph, which leads to a conjecture regarding the unique extremal Ramsey(4, 4) graph.

We introduce and investigate a natural problem regarding unit cube tilings/partitions of Euclidean space and also consider broad generalizations of this problem. The problem fits well within a historical context of similar problems and also has applications to the study of reproducibility in randomized computation. Given $k\in\mathbb{N}$ and $\epsilon\in(0,\infty)$, we define a $(k,\epsilon)$-secluded unit cube partition of $\mathbb{R}^{d}$ to be a unit cube partition of $\mathbb{R}^{d}$ such that for every point $\vec{p}\in\R^d$, the closed $\ell_{\infty}$ $\epsilon$-ball around $\vec{p}$ intersects at most $k$ cubes. The problem is to construct such partitions for each dimension $d$ with the primary goal of minimizing $k$ and the secondary goal of maximizing $\epsilon$. We prove that for every dimension $d\in\mathbb{N}$, there is an explicit and efficiently computable $(k,\epsilon)$-secluded axis-aligned unit cube partition of $\mathbb{R}^d$ with $k=d+1$ and $\epsilon=\frac{1}{2d}$. We complement this construction by proving that for axis-aligned unit cube partitions, the value of $k=d+1$ is the minimum possible, and when $k$ is minimized at $k=d+1$, the value $\epsilon=\frac{1}{2d}$ is the maximum possible. This demonstrates that our constructions are the best possible. We also consider the much broader class of partitions in which every member has at most unit volume and show that $k=d+1$ is still the minimum possible. We also show that for any reasonable $k$ (i.e. $k\leq 2^{d}$), it must be that $\epsilon\leq\frac{\log_{4}(k)}{d}$. This demonstrates that when $k$ is minimized at $k=d+1$, our unit cube constructions are optimal to within a logarithmic factor even for this broad class of partitions. In fact, they are even optimal in $\epsilon$ up to a logarithmic factor when $k$ is allowed to be polynomial in $d$. We extend the techniques used above to introduce and prove a variant of the KKM lemma, the Lebesgue covering theorem, and Sperner's lemma on the cube which says that for every $\epsilon\in(0,\frac12]$, and every proper coloring of $[0,1]^{d}$, there is a translate of the $\ell_{\infty}$ $\epsilon$-ball which contains points of least $(1+\frac23\epsilon)^{d}$ different colors. Advisers: N. V. Vinodchandran & Jamie Radcliffe

This thesis investigates Cohen-Macaulay properties of squarefree monomial ideals, which is an important line of inquiry in the field of combinatorial commutative algebra. A famous example of this is Villareal’s edge ideal [11]: given a finite simple graph G with vertices x1, . . . , xn, the edge ideal of G is generated by all the monomials of the form xixj where xi and xj are adjacent in G. Villareal’s characterization of Cohen-Macaulay edge ideals associated to trees is an often-cited result in the literature. This was extended to chordal and bipartite graphs by Herzog, Hibi, and Zheng in [7] and by Herzog and Hibi in [6]. In 2020, Sharifan and Moradi [10] introduced a related construction called the closed neighborhood ideal of a graph. Whereas an edge ideal of a graph G is generated by monomials associated to each edge in G, the closed neighborhood ideal is generated by monomials associated to its closed neighborhoods. In 2021, Sather-Wagstaff and Honeycutt [8] characterized trees whose closed neighborhood ideals are Cohen-Macaulay. We will provide a generalization of this characterization to chordal graphs and bipartite graphs. Additionally, we will survey the behavior of the depth of closed neighborhood ideals under certain graph operations.

In this dissertation we study the geometry of pipe dream complexes with the goal of gaining a deeper understanding of Schubert polynomials. Given a pipe dream complex PD(w) for w a permutation in the symmetric group, we show its boundary is Whitney stratified by the set of all pipe dream complexes PD(v) where v > w in the strong Bruhat order. For permutations w in the symmetric group on n elements, we introduce the pipe dream complex poset P(n). The dual of this graded poset naturally corresponds to the poset of strata associated to the Whitney stratification of the boundary of the pipe dream complex of the identity element. We examine pipe dream complexes in the case a permutation is a product of commuting adjacent transpositions. Finally, we consider pattern avoidance results. For 132-avoiding permutations, the Rothe diagram forms a Young diagram. In the case a permutation w has exactly one 132-pattern, the associated pipe dream complex is an m-dimensional simplex, where m = n choose 2 − l(w) − 1 and l(w) is the length of w. In the case of exactly two 132 patterns, there are three possible configurations. We include generalizations of these cases.

Chip firing is a category of games played on graphs. The gonality of a graph tells us how many chips are needed to win one variation of the chip firing game. The focus of this dissertation is to provide a variety of new strategies to compute the gonality of various graph families. One family of graphs which this dissertation is particularly interested in is rook graphs. Rook graphs are the Cartesian product of two or more complete graphs and we prove that the gonality of two dimensional rook graphs is the expected value of (n − 1)m where n is the size of the smaller complete graph and m is the size of the larger.

Polytopes are geometric objects that generalize polygons in the plane and polyhedra in 3-dimensional space. Of particular interest in geometric combinatorics are families of lattice polytopes defined from combinatorial objects, such as graphs. In particular, this dissertation studies symmetric edge polytopes (SEPs), defined from simple undirected graphs. In 2019, Higashitani, Jochemko, and Michalek gave a combinatorial description of the hyperplanes that support facets of a symmetric edge polytope in terms of certain labelings of the underlying graph.Using this framework, we explore the number of facets that can be attained by the symmetric edge polytopes for graphs with certain structure. First, we establishformulas or bounds for the number of facets attained by families of sparse, connected graphs, and give conjectures concerning the maximum and minimum facet counts for more general families. We also consider the number of facets of SEPs arising from graphs generated by several random graph models and investigate a conjectured connection between facet counts for SEPs and clustering metrics on their underlying graphs.

We study a partial ordering on pairings called the uncrossing poset, which first appeared in the literature in connection with a certain stratified space of planar electrical networks. We begin by examining some of the relationships between the uncrossing poset and Catalan combinatorics, and then proceed to study the structure of lower intervals. We characterize the lower intervals in the uncrossing poset that are isomorphic to the face lattice of a cube. Moving up in complexity certain lower intervals are isomorphic to the poset of simple vertex labeled minors of an associated graph. Inspired by this structure, we define a notion of minors for lattices enriched with a generating set that abstracts the notion of simple vertex labeled minors of a graph. We can associate a generator-enriched lattice to any polymatroid, a far reaching generalization of graphs, and we show that conversely, any generator-enriched lattice has an associated polymatroid. The generator-enriched lattice encodes the simple information of the closure operator of the polymatroid analagous to how a geometric lattice encodes the simple information of a matroid. For a generator-enriched lattice associated to a graph we show the minors of the generator-enriched lattice are in bijection with the simple vertex labeled minors of the graph. This bijection is generalized to any generator-enriched lattice and its associated polymatroid. We proceed to study a partial order structure on the minors of a given generator-enriched lattice called the minor poset whose relations correspond to performing deletions and contractions. A construction for minor posets in terms of the zipping operation introduced by Reading is given. This construction implies any minor poset is isomorphic to the face poset of a regular CW sphere, and in particular, implies minor posets are Eulerian. This construction also yields cd-index inequalities for minor posets. We characterize the generator-enriched lattices whose minor poset is itself a lattice as meet-distributive lattices avoiding a single forbidden minor. As a special case, minor posets of distributive lattices avoiding this forbidden minor are isomorphic to the face lattice of the order polytope of the dual of the poset of join-irreducibles.\ The deletion and contraction operations of generator-enriched lattices do not commute. We introduce a modified version of contractions, called weak contractions that does commute with deletions and from this operation define weak minor posets whose relations correspond to performing deletions and weak contractions. The theory of weak minor posets closely parallels that of minor posets. Most notably, weak minor posets are shown to be complemented lattices and strong maps between generator-enriched lattices induce meet-preserving maps between the weak minor posets in analogy with the zipping construction for minor posets. We characterize graded weak minor posets and induce EL-labelings for weak minor posets of generator-enriched lattices whose minors each have an EL-labeling. In particular, we find any graded weak minor poset is also shellable.

Matroid theory was first introduced to generalize the notion of linear independence. Since its introduction, the theory has found many applications in various areas of mathematics including coding theory. In recent years, q-matroids, the q-analogue of matroids, were reintroduced and found to be closely related to the theory of linear vector rank metric codes. This relation was then generalized to q-polymatroids and linear matrix rank metric codes. This dissertation aims at developing the theory of q-(poly)matroid and its relation to the theory of rank metric codes. In a first part, we recall and establish preliminary results for both q-polymatroids and q-matroids. We then describe how linear rank metric codes induce q-polymatroids and show how some invariants of rank-metric codes are fully determined by the induced q-polymatroid. Furthermore, we show that not all q-polymatroids arise from rank metric codes which gives rise to the class of non-representable q-polymatroids. We then define the notion of independent space for q-polymatroids and show that together with their rank values, those independents spaces fully determine the q-polymatroid. Next, we restrict ourselves to the study of q-matroids. We start by studying the characteristic polynomial of q-matroids by relating it to the characteristic polynomial of the projectivazition matroid. We establish a deletion/contraction formula for the characteristic polynomial of q-matroids and prove a q-analogue of the Critical Theorem. Afterwards, we study the direct-sum of q-matroids. We show the cyclic flats of the direct sum can be nicely characterized in terms of the cyclic flats of each summands. Using this characterization, we show all q-matroids can be uniquely decomposed (up to equivalence) into the direct sum of irreducible components. We furthermore show that unlike classical matroids, the direct sum of two representable q-matroids over some fixed field is not necessarily representable over that same field. Finally we consider q-matroids from a category theory perspective to study the theoretical similarities and differences between classical matroids and q-matroids. We define several type of maps between q-matroids and consider the resultant categories. We then proceed to show that the direct sum of q-matroids is a coproduct in only one of those categories which stands in contrast to categories of classical matroids. We conclude by showing the existence of a functor from categories of q-matroids to categories of matroids which provide an alternative method to study the former categories.

Much of algebraic geometry is the study of curves. One tool we use to study curves is whether they can be embedded in a K3 surface or not. If the Wahl map is surjective on a curve, that curve cannot be embedded in a K3 surface. Therefore, studying if the Wahl map is surjective for a particular curve gives us more insight into the properties of that curve. We simplify this problem by converting graph curves to dual graphs. Then the information for graphs can be used to study the underlying curves. We will discuss conditions for the Wahl map to be surjective on a cubic graph. The Wahl map on a cubic graph has two parts, one map onto the vertices and another onto the edges. We found that if the cubic graph is 3-edge-connected and non-planar, then the map on the vertices is surjective. Surjectivity of the map on the edges is not as clear. However, if the Wahl map is surjective on a cubic graph, the girth of the graph must be at least 5. Finally, based on data collected, we have observed that as the size of cubic graphs of girth at least 5 increases, the probability that the Wahl map is surjective on those graphs appears to approach 1.

A graph {\color{black}$G$} is Hamilton-connected if for any pair of distinct vertices {\color{black}$u, v \in V(G)$}, {\color{black}$G$} has a spanning $(u,v)$-path; {\color{black}$G$} is 1-hamiltonian if for any vertex subset $S \subseteq {\color{black}V(G)}$ with $|S| \le 1$, $G - S$ has a spanning cycle. Let $\delta(G)$, $\alpha'(G)$ and $L(G)$ denote the minimum degree, the matching number and the line graph of a graph $G$, respectively. The following result is obtained. {\color{black} Let $G$ be a simple graph} with $|E(G)| \ge 3$. If $\delta(G) \geq \alpha'(G)$, then each of the following holds. \\ (i) $L(G)$ is Hamilton-connected if and only if $\kappa(L(G))\ge 3$. \\ (ii) $L(G)$ is 1-hamiltonian if and only if $\kappa(L(G))\ge 3$. %==========sp For a graph $G$, an integer $s \ge 0$ and distinct vertices $u, v \in V(G)$, an $(s; u, v)$-path-system of $G$ is a subgraph $H$ consisting of $s$ internally disjoint $(u,v)$-paths. The spanning connectivity $\kappa^*(G)$ is the largest integer $s$ such that for any $k$ with $0 \le k \le s$ and for any $u, v \in V(G)$ with $u \neq v$, $G$ has a spanning $(k; u,v)$-path-system. It is known that $\kappa^*(G) \le \kappa(G)$, and determining if $\kappa^*(G) > 0$ is an NP-complete problem. A graph $G$ is maximally spanning connected if $\kappa^*(G) = \kappa(G)$. Let $msc(G)$ and $s_k(G)$ be the smallest integers $m$ and $m'$ such that $L^m(G)$ is maximally spanning connected and $\kappa^*(L^{m'}(G)) \ge k$, respectively. We show that every locally-connected line graph with connectivity at least 3 is maximally spanning connected, and that the spanning connectivity of a locally-connected line graph can be polynomially determined. As applications, we also determined best possible upper bounds for $msc(G)$ and $s_k(G)$, and characterized the extremal graphs reaching the upper bounds. %==============st For integers $s \ge 0$ and $t \ge 0$, a graph $G$ is $(s,t)$-supereulerian if for any disjoint edge sets $X, Y \subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. Pulleyblank in [J. Graph Theory, 3 (1979) 309-310] showed that determining whether a graph is $(0,0)$-supereulerian, even when restricted to planar graphs, is NP-complete. Settling an open problem of Bauer, Catlin in [J. Graph Theory, 12 (1988) 29-45] showed that every simple graph $G$ on $n$ vertices with $\delta(G) \ge \frac{n}{5} -1$, when $n$ is sufficiently large, is $(0,0)$-supereulerian or is contractible to $K_{2,3}$. We prove the following for any nonnegative integers $s$ and $t$. \\ (i) For any real numbers $a$ and $b$ with $0 < a < 1$, there exists a family of finitely many graphs $\F(a,b;s,t)$ such that if $G$ is a simple graph on $n$ vertices with $\kappa'(G) \ge t+2$ and $\delta(G) \ge an + b$, then either $G$ is $(s,t)$-supereulerian, or $G$ is contractible to a member in $\F(a,b;s,t)$. \\ (ii) Let $\ell K_2$ denote the connected loopless graph with two vertices and $\ell$ parallel edges. If $G$ is a simple graph on $n$ vertices with $\kappa'(G) \ge t+2$ and $\delta(G) \ge \frac{n}{2}-1$, then when $n$ is sufficiently large, either $G$ is $(s,t)$-supereulerian, or for some integer $j$ with $t+2 \le j \le s+t$, $G$ is contractible to a $j K_2$. %==================index For a hamiltonian property $\cp$, Clark and Wormold introduced the problem of investigating the value $\cp(a,b) = \max\{\min\{n: L^n(G)$ has property $\cp$\}: $\kappa'(G) \ge a$ and $\delta(G) \ge b\}$, and proposed a few problems to determine $\cp(a,b)$ with $b \ge a \ge 4$ when $\cp$ is being hamiltonian, edge-hamiltonian and hamiltonian-connected. Zhan in 1986 proved that the line graph of a 4-edge-connected graph is Hamilton-connected, which implies a solution to the unsettled cases of above-mentioned problem. We consider an extended version of the problem. Let $ess'(G)$ denote the essential edge-connectivity of a graph $G$, and define $\cp'(a,b) = \max\{\min\{n: L^n(G)$ has property $\cp$\}: $ess'(G) \ge a$ and $\delta(G) \ge b\}$. We investigate the values of $\cp'(a,b)$ when $\cp$ is one of these hamiltonian properties. In particular, we show that for any values of $b \ge 1$, $\cp'(4,b) \le 2$ and $\cp'(4,b) = 1$ if and only if Thomassen's conjecture that every 4-connected line graph is hamiltonian is valid.

The purpose of this thesis is to present new different spaces as attempts to generalize the concept of topological vector spaces. A topological vector space, a well-known concept in mathematics, is a vector space over a field \mathbb{F} with a topology that makes the addition and scalar multiplication operations of the vector space continuous functions. The field \mathbb{F} is usually \mathbb{R} or \mathbb{C} with their standard topologies. Since every vector space is a finitary matroid, we define two spaces called finite matroidal spaces and matrological spaces by replacing the linear structure of the topological vector space with a finitary matroidal structure. The idea is to combine a finitary matroidal closure operator like the linear closure operator with a topological closure operator into a single closure operator called a common closure operator. Therefore, one may take a set with a finitary matroidal closure operator and a topological closure operator like the topological vector space. The study starts with basic definitions, some fundamental properties and a collection of examples. The finite matroidal spaces and matrological spaces are then presented. Furthermore, the idea of a common closure operator is introduced and then a discussion is given of when to obtain from a set and a common closure operator a finite matroidal space or a matrological space. Finally, relationships of topological vector spaces with both finite matroidal spaces and topological vector spaces are presented.

We investigate algebra structures on resolutions of a special class of Cohen-Macaulay simplicial complexes. Given a simplicial complex, we define a pure simplicial complex called the purification. These complexes arise as a generalization of certain independence complexes and the resultant Stanley-Reisner rings have numerous desirable properties, e.g., they are Cohen-Macaulay. By realizing the purification in the context of work of D'alì, et al., we obtain a multi-graded, minimal free resolution of the Alexander dual ideal of the Stanley-Reisner ideal. We augment this in a standard way to obtain a resolution of the quotient ring, which is likewise minimal and multi-graded. Ultimately, we propose an explicit product on the resolution and prove that, if associative, this product imparts a differential graded (DG) algebra structure on the minimal resolution.

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemer\'edi proved that any on-line algorithm could be forced to use $\binom{w+1}{2}$ chains to partition a poset of width $w$. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In the survey paper by Bosek et al., variants of the problem were studied where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size $d$. We prove two results for this problem. First, we prove that any on-line algorithm can be forced to use $(2-o(1))\binom{w+1}{2}$ chains to partition a $2$-dimensional poset of width $w$. Second, we prove that any on-line algorithm can be forced to use $(2-\frac{1}{d-1}-o(1))\binom{w+1}{2}$ chains to partition a poset of width $w$ presented via a realizer of size $d$. Chrobak and \'Slusarek considered variants of the on-line chain partitioning problem in which the elements are presented as intervals and intersecting intervals are incomparable. They constructed an on-line algorithm which uses at most $3w-2$ chains, where $w$ is the width of the interval order, and showed that this algorithm is optimal. They also considered the problem restricted to intervals of unit-length and while they showed that first-fit needs at most $2w-1$ chains, over $30$ years later, it remains unknown whether a more optimal algorithm exists. We improve upon previously known bounds and show that any on-line algorithm can be forced to use $\lceil\frac{3}{2}w\rceil$ chains to partition a semi-order presented in the form of its unit-interval representation. As a consequence, we completely solve the problem for $w=3$. We also consider entirely new variants and present the results for those.

Matroids are combinatorial structures that generalize the properties of linear independence. But not all matroids have linear representations. Furthermore, the existence of linear representations depends on the characteristic of the fields, and the linear characteristic set is the set of characteristics of fields over which a matroid has a linear representation. The algebraic independence in a field extension also defines a matroid, and also depends on the characteristic of the fields. The algebraic characteristic set is defined in the similar way as the linear characteristic set. The linear representations and characteristic sets are well studied. But the algebraic representations and characteristic sets received much less attention, and the possible algebraic characteristic sets are still not completely known. This dissertation is a study of possible pairs of linear-algebraic characteristic sets of matroids. Furthermore, if a matroid has an algebraic representation over a positive characteristic field, then the matroid can be represented by a particular set of linear matroids in a field of the same characteristic, called Frobenius flock. In this dissertation, we also have studied Frobenius flock representations, and possible flock characteristic sets.

This dissertation considers several problems in extremal graph theory with the aim of finding the maximum or minimum number of certain subgraph counts given local conditions. The local conditions of interest to us are saturation and covering. Given graphs F and H, a graph G is said to be F-saturated if it does not contain any copy of F, but the addition of any missing edge in G creates at least one copy of F. We say that G is H-covered if every vertex of G is contained in at least one copy of H. In the former setting, we prove results regarding the minimum number of copies of certain subgraphs, primarily cliques and stars. Special attention will be given to the somewhat surprising challenge of minimizing the number of cherries, i.e. stars with two vertices of degree 1, in triangle-saturated graphs and its connection to Moore graphs. In the latter setting, we are interested in maximizing the number of independent sets of a fixed size in H-covered graphs, primarily when H is a star, path, or disjoint union of edges. Along the way, we will introduce and prove several results regarding a new style of question regarding graph saturation, namely determining for which graphs F there exist trees that are F-saturated. We will call such graphs tree-saturating. Adviser: Jamie Radcliffe

The worm domain developed by Diederich and Fornæss is a classic example of a boundedpseudoconvex domains that fails to satisfy global regularity of the Bergman Projection, due to the set of weakly pseudoconvex points that form an annulus in its boundary. We instead examine a bounded pseudoconvex domain Ω ⊂ C2 whose set of weakly pseudoconvex points form a crescent in its boundary. In 2019, Harrington had shown that these types of domains satisfy global regularity of the Bergman Projection based on the existence of good vector fields. In this thesis we study the Regularized Diederich-Fornæss index of these domains, another sufficient condition for global regularity of the Bergman Projection.

This dissertation studies the geometry and combinatorics related to a flow polytope Fcar(ν) constructed from a lattice path ν, whose volume is given by the ν-Catalan numbers. It begins with a study of the ν-associahedron introduced by Ceballos, Padrol, and Sarmiento in 2019, but from the perspective of Schröder combinatorics. Some classical results for Schröder paths are extended to the ν-setting, and insights into the geometry of the ν-associahedron are obtained by describing its face poset with two ν-Schröder objects. The ν-associahedron is then shown to be dual to a framed triangulation of Fcar(ν), which is a geometric realization of the ν-Tamari complex. The dual graph of this triangulation is the Hasse diagram of the ν-Tamari lattice due to Préville-Ratelle and Viennot. The dual graph of a second framed triangulation of Fcar(ν) is shown to be the Hasse diagram of a principal order ideal of Young’s lattice generated by ν, and is used to show that the h∗-vector of Fcar(ν) is given by ν-Narayana numbers. This perspective serves to unify these two important lattices associated with ν-Dyck paths through framed triangulations of a flow polytope. Via an integral equivalence between Fcar(ν) and a subpolytope UI,J of a product of two simplices subdivisions of UI,J are shown to be obtainable with Mészáros’ subdivision algebra, which answers a question of Ceballos, Padrol, and Sarmiento. Building on this result, the subdivision algebra is extended to encode subdivisions of a product of two simplices, giving a new tool for their future study.

A long-standing conjecture in geometric combinatorics entails the interplay between three properties of lattice polytopes: reflexivity, the integer decomposition property (IDP), and the unimodality of Ehrhart h*-vectors. Motivated by this conjecture, this dissertation explores geometric properties of weighted projective space simplices, a class of lattice simplices related to weighted projective spaces. In the first part of this dissertation, we are interested in which IDP reflexive lattice polytopes admit regular unimodular triangulations. Let Delta(1,q)denote the simplex corresponding to the associated weighted projective space whose weights are given by the vector (1,q). Focusing on the case where Delta(1,q) is IDP reflexive such that q has two distinct parts, we establish a characterization of the lattice points contained in Delta(1,q) and verify the existence of a regular unimodular triangulation of its lattice points by constructing a Grobner basis with particular properties. In the second part of this dissertation, we explore how a necessary condition for IDP that relaxes the IDP characterization of Braun, Davis, and Solus yields a natural parameterization of an infinite class of reflexive simplices associated to weighted projective spaces. This parametrization allows us to check the IDP condition for reflexive simplices having high dimension and large volume, and to investigate h* unimodality for the resulting IDP reflexives in the case that Delta(1,q) is 3-supported.

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a linear combination of matrix expressions on the adjacency matrix of a host graph. Algorithms for computing the coefficients of these terms for counting arbitrary subgraphs are presented, with a special focus on efficiency and robustness. These algorithms are used to produce coefficients for counting the number of 8-cycles in a host graph. The matrix expressions used are derived from the space of even functionals of degree . This space is represented by the set of even multigraphs with edges. A difficulty in discovering these spaces hence is discovery of the even graphs themselves. Included in the research are tools developed to facilitate investigation of even functionals. These tools, written in both Python and C++, perform arbitrary-precision evaluation of matrix expressions, solve linear systems of equations, draw and compare graphs, and more. They utilize well-known libraries and packages such as GMP, NumPy, NetworkX, and Graphviz.

A graph is supereulerian if it has a spanning closed trail. Pulleyblank in 1979 showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. Let $\kappa'(G)$ and $\delta(G)$ be the edge-connectivity and the minimum degree of a graph $G$, respectively. For integers $s \ge 0$ and $t \ge 0$, a graph $G$ is $(s,t)$-supereulerian if for any disjoint edge sets $X, Y \subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. This dissertation is devoted to providing some results on $(s,t)$-supereulerian graphs and supereulerian hypergraphs. In Chapter 2, we determine the value of the smallest integer $j(s,t)$ such that every $j(s,t)$-edge-connected graph is $(s,t)$-supereulerian as follows: \[ j(s,t) = \left\{ \begin{array}{ll} \max\{4, t + 2\} & \mbox{ if $0 \le s \le 1$, or $(s,t) \in \{(2,0), (2,1), (3,0),(4,0)\}$,} \\ 5 & \mbox{ if $(s,t) \in \{(2,2), (3,1)\}$,} \\ s + t + \frac{1 - (-1)^s}{2} & \mbox{ if $s \ge 2$ and $s+t \ge 5$. } \end{array} \right. \] As applications, we characterize $(s,t)$-supereulerian graphs when $t \ge 3$ in terms of edge-connectivities, and show that when $t \ge 3$, $(s,t)$-supereulerianicity is polynomially determinable. In Chapter 3, for a subset $Y \subseteq E(G)$ with $|Y|\le \kappa'(G)-1$, a necessary and sufficient condition for $G-Y$ to be a contractible configuration for supereulerianicity is obtained. We also characterize the $(s,t)$-supereulerianicity of $G$ when $s+t\le \kappa'(G)$. These results are applied to show that if $G$ is $(s,t)$-supereulerian with $\kappa'(G)=\delta(G)\ge 3$, then for any permutation $\alpha$ on the vertex set $V(G)$, the permutation graph $\alpha(G)$ is $(s,t)$-supereulerian if and only if $s+t\le \kappa'(G)$. For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $k\le s$ vertices results in a Hamiltonian graph. Let $i_{s,t}(G)$ and $h_s(G)$ denote the smallest integer $i$ such that the iterated line graph $L^{i}(G)$ is $(s,t)$-supereulerian and $s$-Hamiltonian, respectively. In Chapter 4, for a simple graph $G$, we establish upper bounds for $i_{s,t}(G)$ and $h_s(G)$. Specifically, the upper bound for the $s$-Hamiltonian index $h_s(G)$ sharpens the result obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785]. Harary and Nash-Williams in 1968 proved that the line graph of a graph $G$ is Hamiltonian if and only if $G$ has a dominating closed trail, Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, and Catlin in 1988 proved that every graph with two edge-disjoint spanning trees is a contractible configuration for supereulerianicity. In Chapter 5, utilizing the notion of partition-connectedness of hypergraphs introduced by Frank, Kir\'aly and Kriesell in 2003, we generalize the above-mentioned results of Harary and Nash-Williams, of Jaeger and of Catlin to hypergraphs by characterizing hypergraphs whose line graphs are Hamiltonian, and showing that every 2-partition-connected hypergraph is a contractible configuration for supereulerianicity. Applying the adjacency matrix of a hypergraph $H$ defined by Rodr\'iguez in 2002, let $\lambda_2(H)$ be the second largest adjacency eigenvalue of $H$. In Chapter 6, we prove that for an integer $k$ and a $r$-uniform hypergraph $H$ of order $n$ with $r\ge 4$ even, the minimum degree $\delta\ge k\ge 2$ and $k\neq r+2$, if $\lambda_2(H)\le (r-1)\delta-\frac{r^2(k-1)n}{4(r+1)(n-r-1)}$, then $H$ is $k$-edge-connected. %$\kappa'(H)\ge k$. Some discussions are displayed in the last chapter. We extend the well-known Thomassen Conjecture that every 4-connected line graph is Hamiltonian to hypergraphs. The $(s,t)$-supereulerianicity of hypergraphs is another interesting topic to be investigated in the future.

If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, polyHG, is the largest number of colors in an H-polychromatic coloring. We determine polyHG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q. For H, K, subsets of the vertex set V(Qd) of the d-cube Qd, K is an exact copy of H if there is an automorphism of Qd sending H to K. For a positive integer, d, and a configuration in Qd, H, we define λ(H,d) as the limit as n goes to infinity of the maximum fraction, over all subsets S of V(Qn), of sub-d-cubes of Qn whose intersection with S is an exact copy of H. We determine λ(C8,4) and λ(P4,3) where C8 is a “perfect” 8-cycle in Q4 and P4 is a “perfect” path with 4 vertices in Q3, λ(H,d) for several configurations in Q2, Q3, and Q4, and an infinite family of configurations. Strong connections exist with extensions Ramsey numbers for cycles in a graph, counting sequences with certain properties, inducibility of graphs, and we determine the inducibility of two vertex disjoint edges in the family of bipartite graphs.

Consensus functions on finite median semilattices and finite median graphs are studied from an axiomatic point of view. We start with a new axiomatic characterization of majority rule on a large class of median semilattices we call sufficient. A key axiom in this result is the restricted decisive neutrality condition. This condition is a restricted version of the more well-known axiom of decisive neutrality given in [4]. Our theorem is an extension of the main result given in [7]. Another main result is a complete characterization of the class of consensus on a finite median semilattice that satisfies the axioms of decisive neutrality, bi-idempotence, and symmetry. This result extends the work of Monjardet [9]. Moreover, by adding monotonicity as a fourth axiom, we are able to correct a mistake from the Monjardet paper. An attempt at extending the results on median semilattices to median graphs is given, based on a new axiom called split decisive neutrality. We are able to show that majority rule is the only consensus function defined on a path with three vertices that satisfies split decisive neutrality and symmetry.

Bootstrap Percolation is a discrete-time process that models the spread of information or disease across the vertex set of a graph. We consider the following version of this process: Initially, each vertex of the graph is set active with probability p or inactive otherwise. Then, at each time step, every inactive vertex with at least k active neighbors becomes active. Active vertices will always remain active. The process ends when it reaches a stationary state. If all the vertices eventually become active, then we say we achieve percolation. This process has been widely studied on many families of graphs, deterministic and random. We analyze the Bootstrap Percolation process on a Random Geometric Graph. A Random Geometric Graph is obtained by choosing n vertices uniformly at random from the unit d-dimensional cube or torus, and joining any two vertices by an edge if they are within a certain distance, r, of each other. We obtain very precise results that characterize the final state of the Bootstrap Percolation process in terms of the parameters p and r with high probability as the number n of vertices tends to infinity. Adviser: Xavier Pérez Giménez

We present a combinatorial formula using skew Young tableaux for the coefficients of Kazhdan-Lusztig polynomials for sparse paving matroids. These matroids are known to be logarithmically almost all matroids, but are conjectured to be almost all matroids. We also show the positivity of these coefficients using our formula. In special cases, such as for uniform matroids, our formula has a nice combinatorial interpretation. Advisers: Kyungyong Lee and Jamie Radclie

The geometry of a curve can be analyzed in many ways. One way of doing this is to study the set of all divisors on a curve of prescribed rank and degree, known as a Brill-Noether variety. A sequence of results, starting in the 1980s, answered several fundamental questions about these varieties for general curves. However, many of these questions are still unanswered if we restrict to special families of curves. This dissertation has three main goals. First, we examine Brill-Noether varieties for these special families and provide combinatorial descriptions of their irreducible components. Second, we provide a natural generalization of Brill-Noether varieties, known as Splitting-Type varieties, that parameterize this decomposition. Lastly, we provide purely combinatorial descriptions of these Splitting-Type varieties and explore the geometric consequences of these descriptions. These results are based upon and extend tools and techniques from tropical geometry.

The first part of this dissertation deals with the equivariant Ehrhart theory of the permutahedron. As a starting point to determining the equivariant Ehrhart theory of the permutahedron, Ardila, Schindler, and I obtain a volume formula for the rational polytopes that are fixed by acting on the permutahedron by a permutation, which generalizes a result of Stanley’s for the volume for the standard permutahedron. Building from the aforementioned work, Ardila, Supina, and I determine the equivariant Ehrhart theory of the permutahedron, thereby resolving an open problem posed by Stapledon. We provide combinatorial descriptions of the Ehrhart quasipolynomial and Ehrhart series of the fixed polytopes of the permutahedron. Additionally, we answer questions regarding the polynomiality of the equivariant analogue of the h*-polynomial. The second part of this dissertation deals with decompositions of the h*-polynomial for rational polytopes. An open problem in Ehrhart theory is to classify all Ehrhart quasipolynomials. Toward this classification problem, one may ask for necessary in- equalities among the coefficients of an h*-polynomial. Beck, Braun, and I contribute such inequalities when P is a rational polytope. Additionally, we provide two decompositions of the h*-polynomial for rational polytopes, thereby generalizing results of Betke and McMullen and Stapledon. We use our rational Betke–McMullen formula to provide a novel proof of Stanley’s Monotonicity Theorem for rational polytopes.

Let $F(x,y)=I+\hspace{-.3cm}\sum\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}A_{m,n}x^my^n$ be a formal power series, where the coefficients $A_{m,n}$ are either all matrices or all scalars. We expand $F(x,y)$ into the formal products $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I+G_{m,n}x^m y^n)$, $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I-H_{m,n}x^m y^n)^{-1}$, namely the \textit{ power product expansion in two independent variables} and \textit{inverse power product expansion in two independent variables} respectively. By developing new machinery involving the majorizing infinite product, we provide estimates on the domain of absolute convergence of the infinite product via the Taylor series coefficients of $F(x,y)$. This machinery introduces a myriad of "mixed expansions", uncovers various algebraic connections between the $(A_{m,n})$ and the $(G_{m,n})$, and uncovers various algebraic connections between the $(A_{m,n})$ and the $(H_{m,n})$, and leads to the identification of the domain of absolute convergence of the power product and the inverse power product as a Cartesian product of polydiscs. This makes it possible to use the truncated power product expansions $\prod\limits_{\substack{p=1\\m+n=p}}^{P}(1+G_{m,n}x^my^n)$,$\prod\limits_{\substack{p=1\\m+n=p}}^{P}(1-H_{m,n}x^my^n)^{-1}$ as approximations to the analytic function $F(x,y)$. The results are made possible by certain algebraic properties characteristic of the expansions. Moreover, in the case where the coefficients $A_{m,n}$ are scalars, we derive two asymptotic formulas for the $G_{m,n},H_{m,n}$, with $m$ {\it fixed}, associated with the majorizing power series. We also discuss various combinatorial interpretations provided by these power product expansions.

This dissertation proves a collection of results in some heterogeneous generalizations of vertex coloring, i.e. generalizations in which the relationship between the colors of two adjacent vertices may differ throughout the graph. For the most part, the results are from group coloring, group list coloring, and DP coloring. The main results are as follows: a group list coloring analogue of Brooks' Theorem for multigraphs, a result linking group structure (rather than only group size) with group coloring, some results involving coloring edge-disjoint unions, and an examination of the relationship between the group and DP coloring numbers of a multigraph and its simplification.

This dissertation develops a new theory of finite function complexity. This novel approach is based on the structure of preimage sets generated under repeat application of the inverse. We encode this information in our primary data-structure, an square matrix called the sigma matrix. This matrix allows us to easily encode information about the functional digraph and cycle structure of the associated endofunction. Additionally, the sigma matrix is of interest in its own right. The columns of sigma matrices are integer partitions of the domain size n, the size of the domain is always an eigenvalue of the sigma matrix, and calculation of the sigma matrix is highly efficient -- requiring no direct calculation of inverses. The problem of finding the number of unique sigma matrices on X^X as a function of n, the size of X, gives rise to a novel integer sequence \[CapitalSigma](n). We use the sigma matrix and a natural ordering on these matrices as part of a flexible and informative definition of preimage complexity. We give several examples of preimage complexity measures and examine the partition of all endofunctions induced by these measures. Finally we show how the integer sequence \[CapitalSigma](n) corresponds to the number of complexity classes induced by the discrete preimage complexity function.

The control of complex networks is an emerging field yet it has already garnered interest from across the scientific disciplines, from robotics to sociology. It has quickly been noticed that many of the classical techniques from controls engineering, while applicable, are not as illuminating as they were for single systems of relatively small dimension. Instead, properties borrowed from graph theory provide equivalent but more practical conditions to guarantee controllability, reachability, observability, and other typical properties of interest to the controls engineer when dealing with large networked systems. This manuscript covers three topics investigated in detail by the author: (i) the role of the choice of target nodes (system outputs) on the control effort, (ii) creating and analyzing graphs with symmetry, and (iii) the relationship between graph structural properties and control effort.

This dissertation is devoted to the study of the geometric properties of subspace configurations, with an emphasis on configurations of points. One distinguishing feature is the widespread use of techniques from Matroid Theory and Combinatorial Optimization. In part we generalize a theorem of Edmond's about partitions of matroids in independent subsets. We then apply this to establish a conjectured bound on the Castelnuovo-Mumford regularity of a set of fat points. We then study how the dimension of an ideal of point changes when intersected with a generic fat subspace. In particular we introduce the concept of a ``very unexpected hypersurface'' passing through a fixed set of points Z. We show in certain cases these can be characterized via combinatorial data and geometric data from the Hyperplane Arrangement dual to Z. This generalizes earlier results on unexpected curves in the plane due to Faenzi, Valles, Cook, Harbourne, Migliore and Nagel.

In this dissertation filtrations of ideals arising from hierarchical models in statistics related by a group action are are studied. These filtrations lead to ideals in polynomial rings in infinitely many variables, which require innovative tools. Regular languages and finite automata are used to prove and explicitly compute the rationality of some multivariate power series that record important quantitative information about the ideals. Some work regarding Markov bases for non-reducible models is shown, together with advances in the polyhedral geometry of binary hierarchical models.

A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph G and a monotone graph property P, one can associate to the pair (G,P) a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these graph-theoretic simplicial complexes using combinatorial and topological approaches as a way to inform our understanding of the graphs and their properties. In this dissertation, we study two families of simplicial complexes: (1) neighborhood complexes and (2) k-matching complexes. A neighborhood complex is a simplicial complex of a graph with vertex set the vertices of the graph and facets given by neighborhoods of each vertex of the graph. In 1978, Lov\'asz used neighborhood complexes as a tool for studying lower bounds for the chromatic number of graphs. In Chapter 2, we will prove results about the connectivity of neighborhood complexes in relation to Haj\'os-type constructions and analyze randomly generated graphs arising from two Haj\'os-type stochastic algorithms using SageMath. Chapter 3 will focus on k-matching complexes. A k-matching complex of a graph is a simplicial complex with vertex set given by edges of the graph and faces given sets of edges in the graph such that each vertex of the induced graph has degree at most k. We pursue the study of k-matching complexes and investigate 2-matching complexes of wheel graphs and caterpillar graphs.

This dissertation focuses on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo (2k+1) at every vertex. Note that the k=1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of k=2 implies the 5-Flow Conjecture. This work is devoted to providing some partial results on these problems. In Chapter 2, we study the problem of modulo 5-orientation for given multigraphic degree sequences. We prove that a multigraphic degree sequence d=(d1,..., dn) has a realization G with a modulo 5-orientation if and only if di≤1,3 for each i. In addition, we show that every multigraphic sequence d=(d1,..., dn) with min{1≤i≤n}di≥9 has a 9-edge-connected realization that admits a modulo 5-orientation for every possible boundary function. Jaeger conjectured that every 9-edge-connected multigraph admits a modulo 5-orientation, whose truth would imply Tutte's 5-Flow Conjecture. Consequently, this supports the conjecture of Jaeger. In Chapter 3, we show that there are essentially finite many exceptions for graphs with bounded matching numbers not admitting any modulo (2k+1)-orientations for any positive integers t. We additionally characterize all infinite many graphs with bounded matching numbers but without a nowhere-zero 3-flow. This partially supports Jaeger's Circular Flow Conjecture and Tutte's 3-Flow Conjecture. In 2018, Esperet, De Verclos, Le and Thomass introduced the problem of weighted modulo orientations of graphs and indicated that this problem is closely related to modulo orientations of graphs, including Tutte's 3-Flow Conjecture. In Chapter 4 and Chapter 5, utilizing properties of additive bases and contractible configurations, we reduced the Esperet et al's edge-connectivity lower bound for some (signed) graphs families including planar graphs, complete graphs, chordal graphs, series-parallel graphs and bipartite graphs, indicating that much lower edge-connectivity bound still guarantees the existence of such orientations for those graph families. In Chapter 6, we show that the assertion of Jaeger's Circular Flow Conjecture with k=2 holds asymptotically almost surely for random 9-regular graphs.

This dissertation mainly focuses on characterizing cycles and circuits in graphs, line graphs and matroids. We obtain the following advances. 1. Results in graphs and line graphs. For a connected graph G not isomorphic to a path, a cycle or a K1,3, let pc(G) denote the smallest integer n such that the nth iterated line graph Ln(G) is panconnected. A path P is a divalent path of G if the internal vertices of P are of degree 2 in G. If every edge of P is a cut edge of G, then P is a bridge divalent path of G; if the two ends of P are of degree s and t, respectively, then P is called a divalent (s, t)-path. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K3}. We prove the following. (i) If G is a connected triangular graph, then L(G) is panconnected if and only if G is essentially 3-edge-connected. (ii) pc(G) ≤ l(G) + 2. Furthermore, if l(G) ≥ 2, then pc(G) = l(G) + 2 if and only if for some integer t ≥ 3, G has a bridge divalent (3, t)-path of length l(G). For a graph G, the supereulerian width μ′(G) of a graph G is the largest integer s such that G has a spanning (k;u,v)-trail-system, for any integer k with 1 ≤ k ≤ s, and for any u, v ∈ V (G) with u ̸= v. Thus μ′(G) ≥ 2 implies that G is supereulerian, and so graphs with higher supereulerian width are natural generalizations of supereulerian graphs. Settling an open problem of Bauer, Catlin in [J. Graph Theory 12 (1988), 29-45] proved that if a simple graph G on n ≥ 17 vertices satisfy δ(G) ≥ n − 1, then μ′(G) ≥ 2. In this paper, we show that for 4 any real numbers a, b with 0 < a < 1 and any integer s > 0, there exists a finite graph family F = F(a,b,s) such that for a simple graph G with n = |V(G)|, if for any u,v ∈ V(G) with uv ∈/ E(G), max{dG(u), dG(v)} ≥ an + b, then either μ′(G) ≥ s + 1 or G is contractible to a member in F. When a = 1,b = −3, we show that if n is sufficiently large, K3,3 is the only 42 obstacle for a 3-edge-connected graph G to satisfy μ′(G) ≥ 3. An hourglass is a graph obtained from K5 by deleting the edges in a cycle of length 4, and an hourglass-free graph is one that has no induced subgraph isomorphic to an hourglass. Kriesell in [J. Combin. Theory Ser. B, 82 (2001), 306-315] proved that every 4-connected hourglass-free line graph is Hamilton-connected, and Kaiser, Ryj ́aˇcek and Vr ́ana in [Discrete Mathematics, 321 (2014) 1-11] extended it by showing that every 4-connected hourglass-free line graph is 1- Hamilton-connected. We characterize all essentially 4-edge-connected graphs whose line graph is hourglass-free. Consequently we prove that for any integer s and for any hourglass-free line graph L(G), each of the following holds. (i) If s ≥ 2, then L(G) is s-hamiltonian if and only if κ(L(G)) ≥ s + 2; (ii) If s ≥ 1, then L(G) is s-Hamilton-connected if and only if κ(L(G)) ≥ s + 3. For integers s1, s2, s3 > 0, let Ns1,s2,s3 denote the graph obtained by identifying each vertex of a K3 with an end vertex of three disjoint paths Ps1+1, Ps2+1, Ps3+1 of length s1,s2 and s3, respectively. We prove the following results. (i)LetN1 ={Ns1,s2,s3 :s1 >0,s1 ≥s2 ≥s3 ≥0ands1+s2+s3 ≤6}. Thenforany N ∈ N1, every N-free line graph L(G) with |V (L(G))| ≥ s + 3 is s-hamiltonian if and only if κ(L(G)) ≥ s + 2. (ii)LetN2={Ns1,s2,s3 :s1>0,s1≥s2≥s3≥0ands1+s2+s3≤4}.ThenforanyN∈N2, every N -free line graph L(G) with |V (L(G))| ≥ s + 3 is s-Hamilton-connected if and only if κ(L(G)) ≥ s + 3. 2. Results in matroids. A matroid M with a distinguished element e0 ∈ E(M) is a rooted matroid with e0 being the root. We present a characterization of all connected binary rooted matroids whose root lies in at most three circuits, and a characterization of all connected binary rooted matroids whose root lies in all but at most three circuits. While there exist infinitely many such matroids, the number of serial reductions of such matroids is finite. In particular, we find two finite families of binary matroids M1 and M2 and prove the following. (i) For some e0 ∈ E(M), M has at most three circuits containing e0 if and only if the serial reduction of M is isomorphic to a member in M1. (ii) If for some e0 ∈ E(M), M has at most three circuits not containing e0 if and only if the serial reduction of M is isomorphic to a member in M2. These characterizations will be applied to show that every connected binary matroid M with at least four circuits has a 1-hamiltonian circuit graph.

My research focuses on two famous problems in graph theory, namely the cycle double cover conjecture and the integer flows conjectures. This kind of problem is undoubtedly one of the major catalysts in the tremendous development of graph theory. It was observed by Tutte that the Four color problem can be formulated in terms of integer flows, as well as cycle covers. Since then, the topics of integer flows and cycle covers have always been in the main line of graph theory research. This dissertation provides several partial results on these two classes of problems.

A tournament graph G is a vertex set V of size n, together with a directed edge set E ⊂ V × V such that (i, j) ∈ E if and only if (j, i) ∉ E for all distinct i, j ∈ V and (i, i) ∉ E for all i ∈ V. We explore the following generalization: For a fixed k we orient every k-subset of V by assigning it an orientation. That is, every facet of the (k − 1)-skeleton of the (n − 1)-dimensional simplex on V is given an orientation. In this dissertation we bound the number of compatible k-simplices, that is we bound the number of k-simplices such that its (k − 1)-faces with the already-specified orientation form an oriented boundary. We prove lower and upper bounds for all k ≥ 3. For k = 3 these bounds agree when the number of vertices n is q or q + 1 where q is a prime power congruent to 3 modulo 4. We also prove some lower bounds for values k > 3 and analyze the asymptotic behavior.

Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields. In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of the fundamental parallelepiped associated to the simplex. We conclude with a proof-of-concept for using machine learning techniques in algebraic combinatorics. Specifically, we attempt to model the integer decomposition property of a family of lattice simplices using a neural network.

In a graph, the generalized distance between multiple vertices is the minimum number of edges in a connected subgraph that contains these vertices. When we consider such distances between all subsets of $k$ vertices and take the sum, it is called the Steiner $k$-Wiener index and has important applications in Chemical Graph Theory. In this thesis we consider the inverse problems related to the Steiner Wiener index, i.e. for what positive integers is there a graph with Steiner Wiener index of that value?

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound on the c-conflict-free connection number of complete graphs.