Year of Publication

2019

Degree Name

Doctor of Philosophy (PhD)

Document Type

Doctoral Dissertation

College

Arts and Sciences

Department

Mathematics

First Advisor

Dr. Richard Ehrenborg

Abstract

A tournament graph G is a vertex set V of size n, together with a directed edge set EV × V such that (i, j) ∈ E if and only if (j, i) ∉ E for all distinct i, jV and (i, i) ∉ E for all iV. 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.

Digital Object Identifier (DOI)

https://doi.org/10.13023/etd.2019.203

Share

COinS