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

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.

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.

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.

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
Original bundle
Now showing 1 - 1 of 1
Name:
Walker_iastate_0097E_17235.pdf
Size:
521.29 KB
Format: