Matching Items (26)
157777-Thumbnail Image.png
Description
The construction of many families of combinatorial objects remains a challenging problem. A t-restriction is an array where a predicate is satisfied for every t columns; an example is a perfect hash family (PHF). The composition of a PHF and any t-restriction satisfying predicate P yields another t-restriction also satisfying

The construction of many families of combinatorial objects remains a challenging problem. A t-restriction is an array where a predicate is satisfied for every t columns; an example is a perfect hash family (PHF). The composition of a PHF and any t-restriction satisfying predicate P yields another t-restriction also satisfying P with more columns than the original t-restriction had. This thesis concerns three approaches in determining the smallest size of PHFs.



Firstly, hash families in which the associated property is satisfied at least some number lambda times are considered, called higher-index, which guarantees redundancy when constructing t-restrictions. Some direct and optimal constructions of hash families of higher index are given. A new recursive construction is established that generalizes previous results and generates higher-index PHFs with more columns. Probabilistic methods are employed to obtain an upper bound on the optimal size of higher-index PHFs when the number of columns is large. A new deterministic algorithm is developed that generates such PHFs meeting this bound, and computational results are reported.



Secondly, a restriction on the structure of PHFs is introduced, called fractal, a method from Blackburn. His method is extended in several ways; from homogeneous hash families (every row has the same number of symbols) to heterogeneous ones; and to distributing hash families, a relaxation of the predicate for PHFs. Recursive constructions with fractal hash families as ingredients are given, and improve upon on the best-known sizes of many PHFs.



Thirdly, a method of Colbourn and Lanus is extended in which they horizontally copied a given hash family and greedily applied transformations to each copy. Transformations of existential t-restrictions are introduced, which allow for the method to be applicable to any t-restriction having structure like those of hash families. A genetic algorithm is employed for finding the "best" such transformations. Computational results of the GA are reported using PHFs, as the number of transformations permitted is large compared to the number of symbols. Finally, an analysis is given of what trade-offs exist between computation time and the number of t-sets left not satisfying the predicate.
ContributorsDougherty, Ryan Edward (Author) / Colbourn, Charles J (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Forrest, Stephanie (Committee member) / Richa, Andrea (Committee member) / Arizona State University (Publisher)
Created2019
158314-Thumbnail Image.png
Description
The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has

The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.

It is well known that the coloring number is an upper bound for the

chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is

a generalization of the coloring number, and it was first introduced

by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$

is the minimum integer $k$ such that for some linear ordering $L$

of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller

vertices $u$ (with respect to $L$) with a path of length at most

$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.

The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$

is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$

if and only if the distance between $x$ and $y$ in $G$ is $3$.

This dissertation improves the best known upper bound of the

chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$

of planar graphs $G$, which is $105$, to $95$. It also improves

the best known lower bound, which is $7$, to $9$.

A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number.
ContributorsAlmulhim, Ahlam (Author) / Kierstead, Henry (Thesis advisor) / Sen, Arunabha (Committee member) / Richa, Andrea (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2020
161386-Thumbnail Image.png
Description
This dissertation consists of three papers about opinion dynamics. The first paper is in collaboration with Prof. Lanchier while the other two papers are individual works. Two models are introduced and studied analytically: the Deffuant model and the Hegselmann-Krause~(HK) model. The main difference between the two models is that the

This dissertation consists of three papers about opinion dynamics. The first paper is in collaboration with Prof. Lanchier while the other two papers are individual works. Two models are introduced and studied analytically: the Deffuant model and the Hegselmann-Krause~(HK) model. The main difference between the two models is that the Deffuant dynamics consists of pairwise interactions whereas the HK dynamics consists of group interactions. Translated into graph, each vertex stands for an agent in both models. In the Deffuant model, two graphs are combined: the social graph and the opinion graph. The social graph is assumed to be a general finite connected graph where each edge is interpreted as a social link, such as a friendship relationship, between two agents. At each time step, two social neighbors are randomly selected and interact if and only if their opinion distance does not exceed some confidence threshold, which results in the neighbors' opinions getting closer to each other. The main result about the Deffuant model is the derivation of a positive lower bound for the probability of consensus that is independent of the size and topology of the social graph but depends on the confidence threshold, the choice of the opinion space and the initial distribution. For the HK model, agent~$i$ updates its opinion~$x_i$ by taking the average opinion of its neighbors, defined as the set of agents with opinion at most~$\epsilon$ apart from~$x_i$. Here,~$\epsilon > 0$ is a confidence threshold. There are two types of HK models: the synchronous and the asynchronous HK models. In the former, all the agents update their opinion simultaneously at each time step, whereas in the latter, only one agent is selected uniformly at random to update its opinion at each time step. The mixed model is a variant of the HK model in which each agent can choose its degree of stubbornness and mix its opinion with the average opinion of its neighbors. The main results of this dissertation about HK models show conditions under which the asymptotic stability holds or a consensus can be achieved, and give a positive lower bound for the probability of consensus and, in the one-dimensional case, an upper bound for the probability of consensus. I demonstrate the bounds for the probability of consensus on a unit cube and a unit interval.
ContributorsLi, Hsin-Lun (Author) / Lanchier, Nicolas (Thesis advisor) / Camacho, Erika (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Motsch, Sebastien (Committee member) / Arizona State University (Publisher)
Created2021
161884-Thumbnail Image.png
Description
Any permutation in the finite symmetric group can be written as a product of simple transpositions $s_i = (i~i+1)$. For a fixed permutation $\sigma \in \mathfrak{S}_n$ the products of minimal length are called reduced decompositions or reduced words, and the collection of all such reduced words is denoted $R(\sigma)$. Any

Any permutation in the finite symmetric group can be written as a product of simple transpositions $s_i = (i~i+1)$. For a fixed permutation $\sigma \in \mathfrak{S}_n$ the products of minimal length are called reduced decompositions or reduced words, and the collection of all such reduced words is denoted $R(\sigma)$. Any reduced word of $\sigma$ can be transformed into any other by a sequence of commutation moves or long braid moves. One area of interest in these sets are the congruence classes defined by using only braid moves or only commutation moves. This document will present work towards a conjectured relationship between the number of reduced words and the number of braid classes. The set $R(\sigma)$ can be drawn as a graph, $G(\sigma)$, where the vertices are the reduced words, and the edges denote the presence of a commutation or braid move between the words. This paper will present brand new work on subgraph structures in $G(\sigma)$, as well as new formulas to count the number of braid edges and commutation edges in $G(\sigma)$. The permutation $\sigma$ covers $\tau$ in the weak order poset if the length of $\tau$ is one less than the length of $\sigma$, and there exists a simple transposition $s_i$ such that $\sigma = \tau s_i$. This paper will cover new work on the relationships between the size of $R(\sigma)$ and $R(\tau)$, and how this creates a new method of writing reduced decompositions of $\sigma$ as products of permutations $\alpha$ and $\beta$, where both $\alpha$ and $\beta$ have a length greater than one. Finally, this thesis will also discuss how these results help relate the number of reduced words and the number of braid classes in certain cases.
ContributorsElder, Jennifer E (Author) / Fishel, Susanna (Thesis advisor) / Childress, Nancy (Committee member) / Czygrinow, Andrzej (Committee member) / Paupert, Julien (Committee member) / Vega, Oscar (Committee member) / Arizona State University (Publisher)
Created2021
161893-Thumbnail Image.png
Description
A $k$-list assignment for a graph $G=(V, E)$ is a function $L$ that assigns a $k$-set $L(v)$ of "available colors" to each vertex $v \in V$. A $d$-defective, $m$-fold, $L$-coloring is a function $\phi$ that assigns an $m$-subset $\phi(v) \subseteq L(v)$ to each vertex $v$ so that each color class

A $k$-list assignment for a graph $G=(V, E)$ is a function $L$ that assigns a $k$-set $L(v)$ of "available colors" to each vertex $v \in V$. A $d$-defective, $m$-fold, $L$-coloring is a function $\phi$ that assigns an $m$-subset $\phi(v) \subseteq L(v)$ to each vertex $v$ so that each color class $V_{i}=\{v \in V:$ $i \in \phi(v)\}$ induces a subgraph of $G$ with maximum degree at most $d$. An edge $xy$ is an $i$-flaw of $\phi$ if $i\in \phi(x) \cap \phi(y)$. An online list-coloring algorithm $\mathcal{A}$ works on a known graph $G$ and an unknown $k$-list assignment $L$ to produce a coloring $\phi$ as follows. At step $r$ the set of vertices $v$ with $r \in L(v)$ is revealed to $\mathcal{A}$. For each vertex $v$, $\mathcal{A}$ must decide irrevocably whether to add $r$ to $\phi(v)$. The online choice number $\pt_{m}^{d}(G)$ of $G$ is the least $k$ for which some such algorithm produces a $d$-defective, $m$-fold, $L$-coloring $\phi$ of $G$ for all $k$-list assignments $L$. Online list coloring was introduced independently by Uwe Schauz and Xuding Zhu. It was known that if $G$ is planar then $\pt_{1}^{0}(G) \leq 5$ and $\pt_{1}^{1}(G) \leq 4$ are sharp bounds; here it is proved that $\pt_{1}^{3}(G) \leq 3$ is sharp, but there is a planar graph $H$ with $\pt_{1}^{2}(H)\ge 4$. Zhu conjectured that for some integer $m$, every planar graph $G$ satisfies $\pt_{m}^{0}(G) \leq 5 m-1$, and even that this is true for $m=2$. This dissertation proves that $\pt_{2}^{1}(G) \leq 9$, so the conjecture is "nearly" true, and the proof extends to $\pt_{m}^{1}(G) \leq\left\lceil\frac{9}{2} m\right\rceil$. Using Alon's Combinatorial Nullstellensatz, this is strengthened by showing that $G$ contains a linear forest $(V, F)$ such that there is an online algorithm that witnesses $\mathrm{pt}_{2}^{1}(G) \leq 9$ while producing a coloring whose flaws are in $F$, and such that no edge is an $i$-flaw and a $j$-flaw for distinct colors $i$ and $j$.
Contributorshan, ming (Author) / Kierstead, Henry A. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Sen, Arunabha (Committee member) / Spielberg, John (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2021
153556-Thumbnail Image.png
Description
Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from

$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$

with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$

whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then

Let $G=(V,E)$ be a graph. A \emph{list assignment} $L$ for $G$ is a function from

$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$

with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$

whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list

assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$

there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called

the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite

graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.

suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that

$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved

the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that

$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.

An online version of the list coloring problem was introduced independently by Schauz

and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice

designs lists of colors for all vertices, but does not tell Bob, and is allowed to

change her mind about unrevealed colors as the game progresses. On her $i$-th turn

Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,

irrevocably, which (independent set) of these vertices to color with $i$. For a

function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if

eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its

list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online

choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If

$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.

The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$

is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,

$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$

can be arbitrarily large. However there are only a few known examples with this gap

equal to one, and none with larger gap. This conjecture is explored in this thesis.

One of the obstacles is that there are not many graphs whose exact list coloring

number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'

problem. Here new examples of graphs with gap one are found, and related technical

results are developed as tools for attacking Zhu's conjecture.

The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices

at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.

This was recently disproved for specially constructed graphs. Here it is shown that

a graph arising naturally in the theory of cellular networks is also a counterexample.
ContributorsWang, Ran (Author) / Kierstead, H.A. (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2015