Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Graph Homomorphisms: Topology, Probability, and Statistical Physics

Martinez Figueroa, Francisco Jose
http://orcid.org/0000-0003-0471-9453
http://rave.ohiolink.edu/etdc/view?acc_num=osu1650391058872365

Abstract Details

2022, Doctor of Philosophy, Ohio State University, Mathematics.
The chromatic number of a graph is the least integer k required to color its vertices with k colors, such that adjacent vertices are assigned different colors. Computing the chromatic number is known to be an NP-complete problem, and thus different bounds have been studied in the last few decades, including topological bounds and bounds inspired by combinatorial models of statistical physics. Graph homomorphisms are a natural generalization of graph colorings and provide a common language to describe and study these topological and statistical physics invariants. In this dissertation, we study the efficiency of these bounds for different families of graphs, including some models of random graphs. We introduce Random Borsuk graphs and Generalized Borsuk graphs, as models where topological bounds to the chromatic number are indeed efficient. We study ε-distance graphs on spheres, where we show that, in general, topological bounds are far from tight. We compute the warmth, a statistical physics bound, of Erdős-Rényi random graphs, Kneser graphs, and Borsuk graphs. We conjecture some relations between both kinds of invariants, and provide evidence for them. Finally, we also explore a related problem of complete colorings on square grids, where colors must be assigned so that all pairs of colors are adjacent at least once.
Matthew Kahle (Advisor)
Hoi Nguyen (Committee Member)
Facundo Mémoli (Committee Member)
227 p.
Mathematics
random graphs, Borsuk-Ulam, topology, chromatic number, graph homomorphism, Kneser graphs, warmth, long range action, hom-complex,

Recommended Citations

Citations

  • Martinez Figueroa, F. J. (2022). Graph Homomorphisms: Topology, Probability, and Statistical Physics [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1650391058872365

    APA Style (7th edition)

  • Martinez Figueroa, Francisco. Graph Homomorphisms: Topology, Probability, and Statistical Physics. 2022. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1650391058872365.

    MLA Style (8th edition)

  • Martinez Figueroa, Francisco. "Graph Homomorphisms: Topology, Probability, and Statistical Physics." Doctoral dissertation, Ohio State University, 2022. http://rave.ohiolink.edu/etdc/view?acc_num=osu1650391058872365

    Chicago Manual of Style (17th edition)

osu1650391058872365
276
© 2022, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.