Dept. of Mathematics
http://hdl.handle.net/2142/16339
Thu, 23 Mar 2017 06:19:12 GMT2017-03-23T06:19:12ZSome properties of Markoff chains
http://hdl.handle.net/2142/94732
Some properties of Markoff chains
Blackwell, David Harold
Markov processes; Markoff chains; Mathematics
Wed, 01 Jan 1941 00:00:00 GMThttp://hdl.handle.net/2142/947321941-01-01T00:00:00ZBlackwell, David HaroldTopology of configuration space on trees
http://hdl.handle.net/2142/89221
Topology of configuration space on trees
Zhou, Sishen
Configuration Space on trees comes naturally from problems in engineering and has its own importance in mathematics. This paper reviewed the existing research results on the topological properties of classic configuration spaces and generalized some of them for the no-k-equal configuration space on trees.
Configuration space; Discrete Morse theory
Wed, 02 Dec 2015 00:00:00 GMThttp://hdl.handle.net/2142/892212015-12-02T00:00:00ZZhou, SishenExtremal graph theory: supersaturation and enumeration
http://hdl.handle.net/2142/89148
Extremal graph theory: supersaturation and enumeration
Liu, Hong
In this thesis, we study supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph.
In Chapter 3, we extend a classical result of Kolaitis, Promel and Rothschild on the typical structure of graphs forbidding a clique of fixed order as a subgraph, showing that the order of the forbidden clique can be as large as some polylogarithmic function of the order of the host graph. This is based on joint work with Balogh, Bushaw, Collares Neto, Morris and Sharifzadeh.
In Chapter 4 and Chapter 5, we study the number of maximal sum-free subsets of the set [n] := {1, 2, . . . , n}. Together with Balogh, Sharifzadeh and Treglown, we show that, for each 1 ≤ i ≤ 4, there are constants Ci such that the number of maximal sum-free subsets in [n] is (C_i + o(1))2^{n/4}, where i ≡ n mod 4. This resolves a conjecture of Cameron and Erdos.
In Chapter 6, with Balogh and Sharifzadeh, we study the number of subsets of [n] which does not contain an arithmetic progression of a fixed length. This addresses another question of Cameron and Erdos and provides an optimal bound for infinitely many n. As corollaries, we improve the known transference results on arithmetic progressions.
Supersaturation; Enumeration; Typical Structure; Extremal Combinatorics
Fri, 04 Dec 2015 00:00:00 GMThttp://hdl.handle.net/2142/891482015-12-04T00:00:00ZLiu, HongThe bound states of Dirac equation with a scalar potential
http://hdl.handle.net/2142/89002
The bound states of Dirac equation with a scalar potential
Dwivedi, Vatsal
We study the bound states of the 1+1 dimensional Dirac equation with a scalar potential, which can also be interpreted as a position dependent "mass'', analytically as well as numerically. We derive a Prüfer-like representation for the Dirac equation, which can be used to derive a condition for the existence of bound states in terms of the fixed point of the nonlinear Prüfer equation for the angle variable. Another condition was derived by interpreting the Dirac equation as a Hamiltonian flow on the 2-dimensional Euclidean space and a shooting argument for the induced flow on the space of its Lagrangian planes following a similar calculation by Jones (Ergodic Theor Dyn Syst, 8 (1988) 119-138). The two conditions are shown to be equivalent, and used to compute the bound states analytically and numerically, as well as to derive a Calogero-like upper bound on the number of bound states. The analytic computations are also compared to the bound states computed using techniques from supersymmetric quantum mechanics.
Dirac equation; Bound states; Dynamical systems
Thu, 10 Dec 2015 00:00:00 GMThttp://hdl.handle.net/2142/890022015-12-10T00:00:00ZDwivedi, VatsalDynamics of a fully stochastic discretized neuronal model with excitatory and inhibitory neurons
http://hdl.handle.net/2142/88189
Dynamics of a fully stochastic discretized neuronal model with excitatory and inhibitory neurons
Berning, Stephen R
We consider here an extension and generalization of the stochastic
neuronal network model developed by DeVille et al.; their model
corresponded to an all-to-all network of discretized
integrate-and-fire excitatory neurons where synapses are
failure-prone. It was shown that this model exhibits different
metastable phases of asynchronous and synchronous behavior, since the
model limits on a mean-field deterministic system with multiple
attractors. Our work investigates adding inhibition into the
model. The new model exhibits the same metastable phases, but also
exhibits new non-monotonic behavior that was not seen in the DeVille
et al. model. The techniques used by DeVille et al. for finding the
mean-field limit are not suitable for this new model. We explore
early attempts at obtaining a new mean-field deterministic system that
would give us an understanding of the behavior seen in the new
model. After redefining the process we do find a mean-field
deterministic system that the model limits on, and we investigate the
behavior of the new model studying the mean-field system.
neural network; neuronal network; inhibitory neurons; inhibition; non-monotonic; synchrony; mean-field analysis; integrate-and-fire; limit theorem
Thu, 16 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/881892015-07-16T00:00:00ZBerning, Stephen RRamanujan's identities, Voronoi summation formula, and zeros of partial sums of zeta and L-functions
http://hdl.handle.net/2142/88129
Ramanujan's identities, Voronoi summation formula, and zeros of partial sums of zeta and L-functions
Roy, Arindam
The focus of the first part of the thesis commences with an examination of two pages in Ramanujan's lost notebook, pages 336 and 335. A casual, or even more prolonged, examination of the strange formulas on these pages does not lead one to conclude that they are related to one another. Moreover, it does not appear that they have any relationships with other parts of mathematics. On page 336 in his lost notebook, Ramanujan proposes two identities. Here, it does not take a reader long to make a deduction -- the formulas are obviously wrong -- each is vitiated by divergent series. Most readers encountering such obviously false claims would dismiss them and deposit the paper on which they were written in the nearest receptacle for recycling (if they were environmentally conscientious). However, these formulas were recorded by Ramanujan. Ramanujan made mistakes, but generally his mistakes were interesting! Frequently, there were hidden truths behind his not so precise or accurate claims -- truths that were deep and influential for decades. Thus, it was difficult for us to dismiss them.
We initially concentrate on only one of the two incorrect ``identities.'" This ``identity'' may have been devised to attack the extended divisor problem. We prove here a corrected version of Ramanujan's claim, which contains the convergent series appearing in it. Our identity is admittedly quite complicated, and we do not claim that what we have found is what Ramanujan originally had in mind. But there are simple and interesting special cases as well as analogues of this identity, one of which very nearly resembles Ramanujan's version. The aforementioned convergent series in Ramanujan's faulty claim is similar to one used by Vorono\"{\dotlessi}, Hardy, and others in their study of the classical Dirichlet divisor problem, and so we are motivated to study further series of this sort. This now brings us to page 335, which comprises two formulas featuring doubly infinite series of Bessel functions. Although again not obvious at a first inspection, one is conjoined with the classical circle problem initiated by Gauss, while the other is associated with the Dirichlet divisor problem. Berndt, Kim, and Zaharescu have written several papers providing proofs of these two difficult formulas in different interpretations. In this thesis, We return to these two formulas and examine them in more general settings.
The Vorono\"{\dotlessi} summation formula appears prominently in our study. In particular, we generalize work of Wilton and derive an analogue involving the sum of divisors function $\sigma_s(n)$.
Another part of the thesis is focused on the partial sums of Dedekind zeta functions and $L$-functions attached to cusp forms. The motivation of the study of the partial sums of Dedekind zeta functions and $L$-functions attached to cusp forms arise from their approximate functional equations. The partial sums of the Dedekind zeta function of a cyclotomic field $K$ is defined by the truncated Dirichlet series
\[
\zeta_{K, X} (s)
= \sum_{ \|\mathfrak{a}\| \leq X } \frac{1}{\|\mathfrak{a}\|^{s}},
\]
where the sum is to be taken over nonzero integral ideals $\mathfrak{a}$ of $K$ and $\|\mathfrak{a}\|$ denotes the absolute norm of $\mathfrak{a}$. We establish the zero-free regions for $\zeta_{K, X} (s)$ and estimate the number of zeros of $\zeta_{K, X} (s)$ up to height $T$.
We consider a family of approximations of a Hecke $L$-function $L_f(s)$ attached to a holomorphic cusp form $f$ of positive integral weight with respect to the full modular group. These families are of the form
\begin{align}
L_f(X;s):=\sum_{n\leq X}\frac{a(n)}{n^s}+\chi_f(s)\sum_{n\leq X}\frac{a(n)}{n^{1-s}},
\end{align}
where $s=\sigma+it$ is a complex variable. From the approximate functional equation one sees that $L_f(X;s)$ is a good approximation to $L_f(s)$ when $X=t/2\pi$. To investigate such approximation in more general sense, we compute the $L^2$-norms of the difference of two such approximations of $L_f(s)$. We work with a weight which is a compactly supported smooth function. Mean square estimates for the difference of approximations of $L_f(s)$ can be obtained from such weighted $L^2$-norms. We also obtain a vertical strips where most of the zeros of $ L_f(X;s) $ lie. We study the distribution of zeros of $L_f(X;s)$ when $X$ is independent of $t$. For $X=1,2$ we prove that all the complex zeros of $L_f(X;s)$ lie on the critical line $\sigma=1/2$. We also show that as $T\to\infty$ and $ X=T^{o(1)} $, $100\%$ of the complex zeros of $ L_f(X;s) $ up to height $T$ lie on the critical line and simple. Here by $100\%$ we mean that the ratio between the number of simple zeros on the critical line and the total number of zeros up to height $T$ approaches 1 as $T\to\infty$.
Ramanujan; Voronoi summation formula; Divisor problem; Dedekind zeta function; Dirichlet polynomial; Distribution of zeros; Hecke L-functions; Approximate functional equation; Proportion of zeros on the critical line
Mon, 03 Aug 2015 00:00:00 GMThttp://hdl.handle.net/2142/881292015-08-03T00:00:00ZRoy, ArindamCompetitive versions of vertex ranking and game acquisition, and a problem on proper colorings
http://hdl.handle.net/2142/88024
Competitive versions of vertex ranking and game acquisition, and a problem on proper colorings
McDonald, Daniel Cooper
In this thesis we study certain functions on graphs. Chapters 2 and 3 deal with variations on vertex ranking, a type of node-labeling scheme that models a parallel processing problem. A k-ranking of a graph G is a labeling of its vertices from {1,...,k} such that any nontrivial path whose endpoints have the same label contains a vertex with a larger label. In Chapter 2, we investigate the problem of list ranking, wherein every vertex of G is assigned a set of possible labels, and a ranking must be constructed by labeling each vertex from its list; the list ranking number of G is the minimum k such that if every vertex is assigned a set of k possible labels, then G is guaranteed to have a ranking from these lists. We compute the list ranking numbers of paths, cycles, and trees with many leaves. In Chapter 3, we investigate the problem of on-line ranking, which asks for an algorithm to rank the vertices of G as they are revealed one at a time in the subgraph of G induced by the vertices revealed so far. The on-line ranking number of G is the minimum over all such labeling algorithms of the largest label that the algorithm can be forced to use. We give algorithmic bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of internal vertices.
Chapter 4 is concerned with the connectedness and Hamiltonicity of the graph G^j_k(H), whose vertices are the proper k-colorings of a given graph H, with edges joining colorings that differ only on a set of vertices contained within a connected subgraph of H on at most j vertices. We introduce and study the parameters g_k(H) and h_k(H), which denote the minimum j such that G^j_k(H) is connected or Hamiltonian, respectively. Finally, in Chapter 5 we compute the game acquisition number of complete bipartite graphs. An acquisition move in a weighted graph G consists a vertex v taking all the weight from a neighbor whose weight is at most the weight of v. In the acquisition game on G, each vertex initially has weight 1, and players Min and Max alternate acquisition moves until the set of vertices remaining with positive weight is an independent set. Min seeks to minimize the size of the final independent set, while Max seeks to maximize it; the game acquisition number is the size of the final set under optimal play.
graph theory; vertex ranking; list ranking; on-line ranking; mixing number; game acquisition
Wed, 15 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880242015-07-15T00:00:00ZMcDonald, Daniel CooperA classification of toric, folded-symplectic manifolds
http://hdl.handle.net/2142/88015
A classification of toric, folded-symplectic manifolds
Hockensmith, Daniel Lawrence
Given a $G$-toric, folded-symplectic manifold with co-orientable folding hypersurface, we show that its orbit space is naturally a manifold with corners $W$ equipped with a smooth map $\psi: W \to \frak{g}^*$, where $\frak{g}^*$ is the dual of the Lie algebra of the torus, $G$. The map $\psi$ has fold singularities at points in the image of the folding hypersurface under the quotient map and it is a unimodular local embedding away from these points. Thus, to every $G$-toric, folded-symplectic manifold we can associate its orbit space data $\psi:W \to \fg^*$, a unimodular map with folds. We fix a unimodular map with folds $\psi:W \to \fg^*$ and show that isomorphism classes of $G$-toric, folded-symplectic manifolds whose orbit space data is $\psi:W \to \fg^*$ are in bijection with $H^2(W; \mathbb{Z}_G\times \R)$, where $\mathbb{Z}_G= \ker(\exp:\frak{g} \to G)$ is the integral lattice of $G$. Thus, there is a pair of characteristic classes associated to every $G$-toric, folded-symplectic manifold. This result generalizes a classical theorem of Delzant as well as the classification of toric, origami manifolds, due to Cannas da Silva, Guillemin, and Pires, in the case where the folding hypersurface is co-orientable.
We spend a significant amount of time discussing the fundamentals of equivariant and non-equivariant folded-symplectic geometry. In particular, we characterize folded-symplectic forms in terms of their induced map from the sheaf of vector fields into a distinguished sheaf of one-forms, we relate the existence of an orientation on the folding hypersurface of a fold-form to the intrinsic derivative of the contraction mapping from the tangent bundle to the cotangent bundle, and we show that $G$-toric, folded-symplectic manifolds are stratified by $K$-toric, folded-symplectic submanifolds, where $K$ varies over the subtori of $G$ and the action is principal on each stratum. We show how these structures give rise to the rigid orbit space structure of a toric, folded-symplectic manifold used in the classification. We also give a robust description of folded-symplectic reduction, which we use to construct local models of toric, folded-symplectic manifolds.
folded-symplectic; toric; Delzant; origami manifolds; classification; completely integrable system
Wed, 15 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880152015-07-15T00:00:00ZHockensmith, Daniel LawrenceOnline choosability of graphs
http://hdl.handle.net/2142/88001
Online choosability of graphs
Mahoney, Thomas R
We study several problems in graph coloring. In list coloring, each vertex $v$ has a set $L(v)$ of available colors and must be assigned a color from this set so that adjacent vertices receive distinct colors; such a coloring is an $L$-coloring, and we then say that $G$ is $L$-colorable. Given a graph $G$ and a function $f:V(G)\to\N$, we say that $G$ is $f$-choosable if $G$ is $L$-colorable for any list assignment $L$ such that $|L(v)|\ge f(v)$ for all $v\in V(G)$. When $f(v)=k$ for all $v$ and $G$ is $f$-choosable, we say that $G$ is $k$-choosable. The least $k$ such that $G$ is $k$-choosable is the choice number, denoted $\ch(G)$. We focus on an online version of this problem, which is modeled by the Lister/Painter game.
The game is played on a graph in which every vertex has a positive number of tokens. In each round, Lister marks a nonempty subset $M$ of uncolored vertices, removing one token at each marked vertex. Painter responds by selecting a subset $D$ of $M$ that forms an independent set in $G$. A color distinct from those used on previous rounds is given to all vertices in $D$. Lister wins by marking a vertex that has no tokens, and Painter wins by coloring all vertices in $G$. When Painter has a winning strategy, we say that $G$ is $f$-paintable. If $f(v)=k$ for all $v$ and $G$ is $f$-paintable, then we say that $G$ is $k$-paintable. The least $k$ such that $G$ is $k$-paintable is the paint number, denoted $\pa(G)$.
In Chapter 2, we develop useful tools for studying the Lister/Painter game. We study the paintability of graph joins and of complete bipartite graphs. In particular, $\pa(K_{k,r})\le k$ if and only if $r<k^k$.
In Chapter 3, we study the Lister/Painter game with the added restriction that the proper coloring produced by Painter must also satisfy some property $\mathcal{P}$. The main result of Chapter 3 provides a general method to give a winning strategy for Painter when a strategy for the list coloring problem is already known. One example of a property $\mathcal{P}$ is that of having an $r$-dynamic coloring, where a proper coloring is $r$-dynamic if each vertex $v$ has at least $\min\set{r,d(v)}$ distinct colors in its neighborhood. For any graph $G$ and any $r$, we give upper bounds on how many tokens are necessary for Painter to produce an $r$-dynamic coloring of $G$. The upper bounds are in terms of $r$ and the genus of a surface on which $G$ embeds.
In Chapter 4, we study a version of the Lister/Painter game in which Painter must assign $m$ colors to each vertex so that adjacent vertices receive disjoint color sets. We characterize the graphs in which $2m$ tokens is sufficient to produce such a coloring. We strengthen Brooks' Theorem as well as Thomassen's result that planar graphs are 5-choosable.
In Chapter 5, we study sum-paintability. The sum-paint number of a graph $G$, denoted $\spa(G)$, is the least $\sum f(v)$ over all $f$ such that $G$ is $f$-paintable. We prove the easy upper bound: $\spa(G)\le|V(G)|+|E(G)|$. When $\spa(G)=|V(G)|+|E(G)|$, we say that $G$ is sp-greedy. We determine the sum-paintability of generalized theta-graphs. The generalized theta-graph $\Theta_{\ell_1,\dots,\ell_k}$ consists of two vertices joined by $k$ paths of lengths $\VEC \ell1k$. We conjecture that outerplanar graphs are sp-greedy and prove several partial results toward this conjecture.
In Chapter 6, we study what happens when Painter is allowed to allocate tokens as Lister marks vertices. The slow-coloring game is played by Lister and Painter on a graph $G$. Lister marks a nonempty set of uncolored vertices and scores 1 point for each marked vertex. Painter colors all vertices in an independent subset of the marked vertices with a color distinct from those used previously in the game. The game ends when all vertices have been colored. The sum-color cost of a graph $G$, denoted $\scc(G)$, is the maximum score Lister can guarantee in the slow-coloring game on $G$. We prove several general lower and upper bounds for $\scc(G)$. In more detail, we study trees and prove sharp upper and lower bounds over all trees with $n$ vertices. We give a formula to determine $\scc(G)$ exactly when $\alpha(G)\le2$. Separately, we prove that $\scc(G)=\spa(G)$ if and only if $G$ is a disjoint union of cliques. Lastly, we give lower and upper bounds on $\scc(K_{r,s})$.
graph coloring; list coloring; choosability; paintability; online list coloring; online choosability
Thu, 09 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/880012015-07-09T00:00:00ZMahoney, Thomas RRoot-theoretic Young diagrams and Schubert Calculus
http://hdl.handle.net/2142/87992
Root-theoretic Young diagrams and Schubert Calculus
Searles, Dominic Nigel
A longstanding problem in algebraic combinatorics is to find nonnegative combinatorial rules for the Schubert calculus of generalized flag varieties; that is, for the structure constants of their cohomology rings with respect to the Schubert basis.
There are several natural choices of combinatorial indexing sets for the Schubert basis classes. This thesis examines a number of Schubert calculus problems from the common lens of root-theoretic Young diagrams (RYDs).
In terms of RYDs, we present nonnegative Schubert calculus rules for the (co)adjoint varieties of classical Lie type. Using these we give polytopal descriptions of the set of nonzero Schubert structure constants for the (co)adjoint varieties where the RYDs are all planar, and suggest a connection between planarity of the RYDs and polytopality of the nonzero Schubert structure constants. This is joint work with A. Yong.
For the family of (nonmaximal) isotropic Grassmannians, we characterize the RYDs and give a bijection between RYDs and the k-strict partitions of A. Buch, A. Kresch and H. Tamvakis. We apply this bijection to show that the (co)adjoint Schubert calculus rules agree with the Pieri rules of A. Buch, A. Kresch and H. Tamvakis, which is needed for the proofs of the (co)adjoint rules.
We also use RYDs to study the Belkale-Kumar deformation of the ordinary cup product on cohomology of generalized flag varieties. This product structure was introduced by P. Belkale and S. Kumar and used to study a generalization of the Horn problem. A structure constant of the Belkale-Kumar product is either zero or equal to the corresponding Schubert structure constant, hence the Belkale-Kumar product captures a certain subset of the Schubert structure constants. We give a new formula (after that of A. Knutson and K. Purbhoo) in terms of RYDs for the Belkale-Kumar product on flag varieties of type A. We also extend this formula outside of type A to the (co)adjoint varieties of classical type.
With O. Pechenik, we introduce a new deformed product structure on the cohomology of generalized flag varieties, whose nonzero structure constants can be understood in terms of projections to smaller flag varieties. We draw comparisons with the ordinary cup product and the Belkale-Kumar product.
Root-theoretic Young diagrams; Schubert calculus; generalized flag variety; adjoint variety; Belkale-Kumar product
Mon, 06 Jul 2015 00:00:00 GMThttp://hdl.handle.net/2142/879922015-07-06T00:00:00ZSearles, Dominic Nigel