Determining the chromatic number of the partition graph P(33) poses a considerable
challenge. We can bound it to 4 ≤ χ(P(33)) ≤ 6, with exhaustive search confirming
χ(P(33)) = 6. A potential mathematical proof strategy for this equality involves
identifying a Z2-invariant S4 with non-trivial homology in the box complex of the
partition graph P(33), namely Bedge(︁P(33))︁, and applying the Borsuk-Ulam theorem to compute its Z2-index. This provides a robust topological lower bound for the chromatic number of P(33), termed the Lovász bound. We have verified the absence of such an S4 within certain sections of Bedge(︁P(33))︁. We also validated this approach through a case study on the Petersen graph.
This thesis offers a thorough examination of various topological lower bounds for
a graph’s chromatic number, complete with proofs and examples. We demonstrate
instances where these lower bounds converge to a single value and others where they
diverge significantly from a graph’s actual chromatic number.
We also classify all vertex pairs, triples, and quadruples of P(33) into unique equivalence classes, facilitating the derivation of all maximal complete bipartite subgraphs.
This classification informs the construction of all simplices of Bedge(︁P(33)).
Following a detailed and technical exploration, we uncover both the maximal size of
the pairwise intersections of its maximal simplices and their underlying structure.
Our study proposes an algorithm for building the box complex of the partition
graph P(33) using our method of identifying maximal complete bipartite subgraphs.
This reduces time complexity to O(n3), marking a substantial enhancement over
brute-force techniques.
Lastly, we apply discrete Morse theory to construct a simplicial complex homotopy
equivalent to the box complex of P(33), using two methods: elementary collapses
and the determination of a discrete Morse function on the box complex. This process
reduces the dimension of the box complex from 35 to 12, streamlining future
calculations of the Z2-index and the Lovász bound.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/45478 |
| Date | 26 September 2023 |
| Creators | Refahi, Behnaz |
| Contributors | Newman, Michael, Fraser, Maia |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0022 seconds