Problems in extremal graphs and poset theory

Walker, Shanise
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue

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.

forbidden subposets, identifying codes, poset saturation