國立高雄大學圖資館 |

Language: English

Back

Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science /Edgar Jaramillo Rodriguez.
Author:	Jaramillo Rodriguez, Edgar,
Description:	1 electronic resource (102 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-03, Section: B.
Notes:	Advisors: De Loera, Jesus A. Committee members: Strohmer, Thomas; Rademacher, Luis.
Contained By:	Dissertations Abstracts International85-03B.
Subject:	Mathematics.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30490728
ISBN:	9798380360173

Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science /
Jaramillo Rodriguez, Edgar,

Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science /Edgar Jaramillo Rodriguez. - 1 electronic resource (102 pages)

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

In this thesis we develop combinatorial methods for studying barcodes. A barcode is a collection of closed intervals on the real line. Barcodes arise as key objects in topological data analysis, as summaries of the persistent homology groups of a filtration, and in graph theory as interval graphs.We first introduce a map from the space of barcodes to certain equivalence classes of double occurrence words, i.e., permutations of a multiset in which every element occurs exactly twice. We call the set of all such words the space of combinatorial barcodes. We then define an order relation on this space, based on the weak-Bruhat order, and show that the resulting poset is a graded lattice. We show that this lattice can also be defined using new notions of inversion multisets/ inversion vectors of double occurrence words. We also use these objects to prove several properties of the lattice. For example, we compute its rank generating function and introduce a natural bijections between combinatorial barcodes, trapezoidal words, and Stirling permutations. In addition to being of interest from a combinatorial perspective, we also show that the cover relations in this lattice can be used to determine the set of barcode bases of persistence modules.We then generalize this construction, producing an entire family of multipermutations associated to barcodes. We equip these new multipermutations with a similar order relation and show that the resulting posets also form lattices, which we call the power-k barcode lattices. Unfortunately, these lattices do not retain many of the other "nice" combinatorial properties found in our original construction. However, we show that these multipermutations record increasingly detailed information about the arrangement of the bars in a barcode. We prove that for a large class of barcodes these multipermutations can be used to bound two classic, continuous metrics on barcodes: the Wasserstein and bottleneck distances. We also show that these lattices form the face lattices of certain Bruhat-interval polytopes.Finally, we study an original model for generating random interval graphs (or equivalently random barcodes). This model is motivated by scientific sampling problems, where one receives a sequence of time-stamped observations and wants to make conclusions about the start and end of certain events. Although our general model is difficult to analyze, we prove many results about the expected behaviour of this model in a special case which we call the stationary case. For example, we compute the expected number of edges, maximum degree, and maximum clique size. We also study the limit behavior of this model as the number of samples/ observations goes to infinity. In particular, we prove that the special case of this model converges to a complete graph and compute a lower bound on the expected waiting time for this to occur.

English

ISBN: 9798380360173Subjects--Topical Terms:

184409
Mathematics.
Subjects--Index Terms:

Interval graphs

Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science /
LDR:04422nmm a22004333i 4500 001 676267
005 20250420214330.5
006 m o d
007 cr|nu||||||||
008 250901s2023 miu||||||m |||||||eng d
020 $a 9798380360173
035 $a (MiAaPQD)AAI30490728
035 $a AAI30490728
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Jaramillo Rodriguez, Edgar, $e author. $3 990004
245 1 0 $a Combinatorial Analysis of Barcodes and Interval Graphs for Applications in Data Science / $c Edgar Jaramillo Rodriguez.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2023
300 $a 1 electronic resource (102 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-03, Section: B.
500 $a Advisors: De Loera, Jesus A. Committee members: Strohmer, Thomas; Rademacher, Luis.
502 $b Ph.D. $c University of California, Davis $d 2023.
520 $a In this thesis we develop combinatorial methods for studying barcodes. A barcode is a collection of closed intervals on the real line. Barcodes arise as key objects in topological data analysis, as summaries of the persistent homology groups of a filtration, and in graph theory as interval graphs.We first introduce a map from the space of barcodes to certain equivalence classes of double occurrence words, i.e., permutations of a multiset in which every element occurs exactly twice. We call the set of all such words the space of combinatorial barcodes. We then define an order relation on this space, based on the weak-Bruhat order, and show that the resulting poset is a graded lattice. We show that this lattice can also be defined using new notions of inversion multisets/ inversion vectors of double occurrence words. We also use these objects to prove several properties of the lattice. For example, we compute its rank generating function and introduce a natural bijections between combinatorial barcodes, trapezoidal words, and Stirling permutations. In addition to being of interest from a combinatorial perspective, we also show that the cover relations in this lattice can be used to determine the set of barcode bases of persistence modules.We then generalize this construction, producing an entire family of multipermutations associated to barcodes. We equip these new multipermutations with a similar order relation and show that the resulting posets also form lattices, which we call the power-k barcode lattices. Unfortunately, these lattices do not retain many of the other "nice" combinatorial properties found in our original construction. However, we show that these multipermutations record increasingly detailed information about the arrangement of the bars in a barcode. We prove that for a large class of barcodes these multipermutations can be used to bound two classic, continuous metrics on barcodes: the Wasserstein and bottleneck distances. We also show that these lattices form the face lattices of certain Bruhat-interval polytopes.Finally, we study an original model for generating random interval graphs (or equivalently random barcodes). This model is motivated by scientific sampling problems, where one receives a sequence of time-stamped observations and wants to make conclusions about the start and end of certain events. Although our general model is difficult to analyze, we prove many results about the expected behaviour of this model in a special case which we call the stationary case. For example, we compute the expected number of edges, maximum degree, and maximum clique size. We also study the limit behavior of this model as the number of samples/ observations goes to infinity. In particular, we prove that the special case of this model converges to a complete graph and compute a lower bound on the expected waiting time for this to occur.
546 $a English
590 $a School code: 0029
650 4 $a Mathematics. $3 184409
650 4 $a Theoretical mathematics. $3 708655
650 4 $a Applied mathematics. $3 377601
653 $a Interval graphs
653 $a Topological data analysis
653 $a Combinatorial barcodes
653 $a Bottleneck distances
653 $a Persistence modules
690 $a 0405
690 $a 0642
690 $a 0364
710 2 $a University of California, Davis. $b Mathematics. $3 603202
720 1 $a De Loera, Jesus A. $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 85-03B.
790 $a 0029
791 $a Ph.D.
792 $a 2023
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30490728