Problems in extremal graphs and poset theory

dc.contributor.advisor Ryan R. Martin
dc.contributor.author Walker, Shanise
dc.contributor.department Mathematics
dc.date 2018-08-11T20:16:43.000
dc.date.accessioned 2020-06-30T03:11:24Z
dc.date.available 2020-06-30T03:11:24Z
dc.date.copyright Thu Mar 01 00:00:00 UTC 2018
dc.date.embargo 2001-01-01
dc.date.issued 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/lib.dr.iastate.edu/etd/16482/
dc.identifier.articleid 7489
dc.identifier.contextkey 12331577
dc.identifier.doi https://doi.org/10.31274/etd-180810-6112
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/16482
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/30665
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/16482/Walker_iastate_0097E_17235.pdf|||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
thesis.degree.discipline Mathematics
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
Name:
Walker_iastate_0097E_17235.pdf
Size:
521.29 KB
Format:
Adobe Portable Document Format
Description: