You are here
LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS
| Title: | LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS. |
 57 views 24 downloads |
|---|---|---|
| Name(s): |
Khera, Jessica, author Lundberg, Erik, Thesis advisor Florida Atlantic University, Degree grantor Department of Mathematical Sciences Charles E. Schmidt College of Science |
|
| Type of Resource: | text | |
| Genre: | Electronic Thesis Or Dissertation | |
| Date Created: | 2021 | |
| Date Issued: | 2021 | |
| Publisher: | Florida Atlantic University | |
| Place of Publication: | Boca Raton, Fla. | |
| Physical Form: | application/pdf | |
| Extent: | 72 p. | |
| Language(s): | English | |
| Summary: | An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes. | |
| Identifier: | FA00013716 (IID) | |
| Degree granted: | Dissertation (PhD)--Florida Atlantic University, 2021. | |
| Collection: | FAU Electronic Theses and Dissertations Collection | |
| Note(s): | Includes bibliography. | |
| Subject(s): |
Matrices Combinatorial analysis Graph theory |
|
| Held by: | Florida Atlantic University Libraries | |
| Sublocation: | Digital Library | |
| Persistent Link to This Record: | http://purl.flvc.org/fau/fd/FA00013716 | |
| Use and Reproduction: | Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder. | |
| Use and Reproduction: | http://rightsstatements.org/vocab/InC/1.0/ | |
| Host Institution: | FAU | |
| Is Part of Series: | Florida Atlantic University Digital Library Collections. |
