Matching Items (28)
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 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
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 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
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 $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
Description
This thesis explores several questions concerning the preservation of geometric structure under the Ricci flow, an evolution equation for Riemannian metrics. Within the class of complete solutions with bounded curvature, short-time existence and uniqueness of solutions guarantee that symmetries and many other geometric features are preserved along the flow. However, much less is known about the analytic and geometric properties of solutions of potentially unbounded curvature. The first part of this thesis contains a proof that the full holonomy group is preserved, up to isomorphism, forward and backward in time. The argument reduces the problem to the preservation of reduced holonomy via an analysis of the equation satisfied by parallel translation around a loop with respect to the evolving metric. The subsequent chapter examines solutions satisfying a certain instantaneous, but nonuniform, curvature bound, and shows that when such solutions split as a product initially, they will continue to split for all time. This problem is encoded as one of uniqueness for an auxiliary system constructed from a family of time-dependent, orthogonal distributions of the tangent bundle. The final section presents some details of an ongoing project concerning the uniqueness of asymptotically product gradient shrinking Ricci solitons, including the construction of a certain system of mixed differential inequalities which measures the extent to which such a soliton fails to split.
ContributorsCook, Mary (Author) / Kotschwar, Brett (Thesis advisor) / Paupert, Julien (Committee member) / Kawski, Matthias (Committee member) / Kaliszewski, Steven (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2021
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 $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.
$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
Description
Van der Waerden’s Theorem asserts that for any two positive integers k and r, one may find an integer w=w(k,r) known as the Van der Waerden Number such that for every r-coloring of the integers from 1 to w there exists a monochromatic arithmetic progression of length k. This groundbreaking theorem in combinatorics has greatly impacted the field of discrete math for decades. However, it is quite difficult to find the exact values of w. As such, it would be worth more of our time to try and bound such a value, both from below and above, in order to restrict the possible values of the Van der Waerden Numbers. In this thesis we will endeavor to bound such a number; in addition to proving Van der Waerden’s Theorem, we will discuss the unique functions that bound the Van der Waerden Numbers.
ContributorsBrannock, Matthew Dean (Author) / Czygrinow, Andrzej (Thesis director) / Fishel, Susanna (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / School of International Letters and Cultures (Contributor) / Barrett, The Honors College (Contributor)
Created2019-12
Description
We consider programmable matter as a collection of simple computational elements (or particles) that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. Within this model a configuration of particles can be represented as a unique closed self-avoiding walk on the triangular lattice. In this paper we will examine the bias parameter of a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. This bias parameter, $\lambda$, determines the behavior of the algorithm. It has been shown that for $\lambda > 2+\sqrt{2}$, with all but exponentially small probability, the algorithm achieves compression. Additionally the same algorithm can be used for expansion for small values of $\lambda$; in particular, for all $0 < \lambda < \sqrt{\tau}$, where $\lim_{n\to\infty} {(p_n)^{1
}}=\tau$. This research will focus on improving approximations on the lower bound of $\tau$. Toward this end we will examine algorithmic enumeration, and series analysis for self-avoiding polygons.
}}=\tau$. This research will focus on improving approximations on the lower bound of $\tau$. Toward this end we will examine algorithmic enumeration, and series analysis for self-avoiding polygons.
ContributorsLough, Kevin James (Author) / Richa, Andrea (Thesis director) / Fishel, Susanna (Committee member) / School of Mathematical and Statistical Sciences (Contributor, Contributor) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2019-05
Description
The Tamari lattice Tn was originally defined on bracketings of a set of n + 1 objects, with a cover relation based on the associativity rule in one direction. Although in several related lattices, the number of maximal chains is known, quoting Knuth, “The enumeration of such paths in Tamari lattices remains mysterious.”
The lengths of maximal chains vary over a great range. In this paper, we focus on the chains with maximum length in these lattices. We establish a bijection between the maximum length chains in the Tamari lattice and the set of standard shifted tableaux of staircase shape. We thus derive an explicit formula for the number of maximum length chains, using the Thrall formula for the number of shifted tableaux. We describe the relationship between chains of maximum length in the Tamari lattice and certain maximal chains in weak Bruhat order on the symmetric group, using standard Young tableaux. Additionally, recently, Bergeron and Pr ́eville-Ratelle introduced a generalized Tamari lattice. Some of the results mentioned above carry over to their generalized Tamari lattice.
ContributorsFishel, Susanna (Author) / Nelson, Luke (Author) / College of Liberal Arts and Sciences (Contributor)
Created2014-10-01