Problems in extremal graphs and poset theory

dc.contributor.advisor Ryan R. Martin Walker, Shanise
dc.contributor.department Mathematics 2018-08-11T20:16:43.000 2020-06-30T03:11:24Z 2020-06-30T03:11:24Z Thu Mar 01 00:00:00 UTC 2018 2001-01-01 2018-01-01
dc.description.abstract <p>In this dissertation, we present three different research topics and results regarding such topics. We introduce partially ordered sets (posets) and study two types of problems concerning them-- forbidden subposet problems and induced-poset-saturation problems. We conclude by presenting results obtained from studying vertex-identifying codes in graphs.</p> <p>In studying forbidden subposet problems, we are interested in estimating the maximum size of a family of subsets of the $n$-set avoiding a given subposet. We provide a lower bound for the size of the largest family avoiding the $\mathcal{N}$ poset, which makes use of error-correcting codes. We also provide and upper and lower bound results for a $k$-uniform hypergraph that avoids a \emph{triangle}. Ferrara et al. introduced the concept of studying the minimum size of a family of subsets of the $n$-set avoiding an induced poset, called induced-poset-saturation. In particular, the authors provided a lower bound for the size of an induced-antichain poset and we improve on their lower bound result.</p> <p>Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. For any nonnegative integer $r$, let $B_r(v)$ denote the ball of radius $r$ around vertex $v\in V$. For a finite graph $G$, an $r$-vertex-identifying code in $G$ is a subset $C\subset V(G)$, with the property that $B_r(u)\cap C\neq B_r(v)\cap C$, for all distinct $u,v\in V(G)$ and $B_r(v)\cap C\neq\emptyset$, for all $v\in V(G)$. We study graphs with large symmetric differences and $(p,\beta)$-jumbled graphs and estimate the minimum size of a vertex-identifying code in each graph.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 7489
dc.identifier.contextkey 12331577
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/16482
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 21:00:57 UTC 2022
dc.subject.disciplines Mathematics
dc.subject.keywords forbidden subposets
dc.subject.keywords identifying codes
dc.subject.keywords poset saturation
dc.title Problems in extremal graphs and poset theory
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48 Mathematics dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
521.29 KB
Adobe Portable Document Format