| 1. |
- Aas, Erik, 1990-
(författare)
-
A Markov Process on Cyclic Words
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The TASEP (totally asymmetric simple exclusion process) studied here is a Markov chain on cyclic words over the alphabet{1,2,...,n} given by at each time step sorting an adjacent pair of letters chosen uniformly at random. For example, from the word 3124 one may go to 1324, 3124, 3124, 4123 by sorting the pair 31, 12, 24, or 43.Two words have the sametype if they are permutations of each other. If we restrict TASEP to words of some particular type m we get an ergodic Markov chain whose stationary distribution we denote by ζm. Soζm (u) is the asymptotic proportion of time spent in the state u if the chain started in some word of type m. The distribution ζ is the main object of study in this thesis. This distribution turns out to have several remarkable properties, and alternative characterizations. It has previously been studied both from physical, combinatorial, and probabilitistic viewpoints.In the first chapter we give an extended summary of known results and results in this thesis concerning ζ. The new results are described (and proved) in detail in Papers I - IV.The new results in Papers I and II include an explicit formula for the value ofζat sorted words and a product formula for decomposable words. We also compute some correlation functions for ζ. In Paper III we study of a generalization of TASEP to Weyl groups. In Paper IV we study a certain scaling limit of ζ, finding several interesting patterns of which we prove some. We also study an inhomogenous version of TASEP, in which different particles get sorted at different rates, which generalizes the homogenous version in several aspects. In the first chapter we compute some correlation functions for ζ
|
|
| 2. |
|
|
| 3. |
- Engström, Alexander, 1977-
(författare)
-
Topological Combinatorics
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis on Topological Combinatorics contains 7 papers. All of them but paper Bare published before.In paper A we prove that!i dim ˜Hi(Ind(G);Q) ! |Ind(G[D])| for any graph G andits independence complex Ind(G), under the condition that G\D is a forest. We then use acorrespondence between the ground states with i+1 fermions of a supersymmetric latticemodel on G and ˜Hi(Ind(G);Q) to deal with some questions from theoretical physics.In paper B we generalize the topological Tverberg theorem. Call a graph on the samevertex set as a (d + 1)(q − 1)-simplex a (d, q)-Tverberg graph if for any map from thesimplex to Rd there are disjoint faces F1, F2, . . . , Fq whose images intersect and no twoadjacent vertices of the graph are in the same face. We prove that if d # 1, q # 2 is aprime power, and G is a graph on (d+1)(q −1)+1 vertices such that its maximal degreeD satisfy D(D + 1) < q, then G is a (d, q)–Tverberg graph. It was earlier known that thedisjoint unions of small complete graphs, paths, and cycles are Tverberg graphs.In paper C we study the connectivity of independence complexes. If G is a graphon n vertices with maximal degree d, then it is known that its independence complex is(cn/d + !)–connected with c = 1/2. We prove that if G is claw-free then c # 2/3.In paper D we study when complexes of directed trees are shellable and how one canglue together independence complexes for finding their homotopy type.In paper E we prove a conjecture by Björner arising in the study of simplicial polytopes.The face vector and the g–vector are related by a linear transformation. We prove thatthis matrix is totaly nonnegative. This is joint work with Michael Björklund.In paper F we introduce a generalization of Hom–complexes, called set partition complexes,and prove a connectivity theorem for them. This generalizes previous results ofBabson, Cukic, and Kozlov, and questions from Ramsey theory can be described with it.In paper G we use combinatorial topology to prove algebraic properties of edge ideals.The edge ideal of G is the Stanley-Reisner ideal of the independence complex of G. Thisis joint work with Anton Dochtermann.
|
|
| 4. |
- Parviainen, Robert, 1975-
(författare)
-
Connectivity Properties of Archimedean and Laves Lattices
- 2004
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- An Archimedean lattice is a graph of a regular tiling of the plane, such that all corners are equivalent. A tiling is regular if all tiles are regular polygons: equilateral triangles, squares, et cetera. There exist exactly 11 Archimedean lattices. Being planar graphs, the Archimedean lattices have duals, 3 of which are Archimedean, the other 8 are called Laves lattices.In the thesis, three measures of connectivity of these 19 graphs are studied: the connective constant for self-avoiding walks, and bond and site percolation critical probabilities. The connective constant measures connectivity by the number of walks in which all visited vertices are unique. The critical probabilities quantify the proportion of edges or vertices that can be removed, so that the produced subgraph has a large connected component.A common issue for these measures is that they, although intensely studied by both mathematicians and scientists from other fields, have been calculated only for very few graphs. With the goal of comparing the induced orders of the Archimedean and Laves lattices under the three measures, the thesis gives improved bounds and estimates for many graphs. A large part of the thesis focuses on the problem of deciding whether a given graph is a subgraph of another graph. This, surprisingly difficult problem, is considered for the set of Archimedean and Laves lattices, and for the set of matching Archimedean and Laves lattices.
|
|
| 5. |
- Potka, Samu
(författare)
-
Dynamics and limits in algebraic combinatorics
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis consists of the following six articles.Properties of the Edelman-Greene bijection. Edelman and Greene constructed a correspondence between reduced words of the reverse permutation and standard Young tableaux. We prove that for any reduced word the shape of the region of the insertion tableau containing the smallest possible entries evolves exactly as the upper-left component of the permutation's (Rothe) diagram. Properties of the Edelman-Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman-Greene bijection applied to non-reduced words.On random shifted standard Young tableaux and 132-avoiding sorting networks. We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman-Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.The cyclic sieving phenomenon on circular Dyck paths. We give a q-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this q-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Möbius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving, and introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.The exact phase diagram for a semipermeable TASEP with nonlocal boundary jumps. We consider a finite one-dimensional totally asymmetric simple exclusion process (TASEP) with four types of particles, 1, 0, -1, and *, in contact with reservoirs. Particles of species 0 can neither enter nor exit the lattice, and those of species * are constrained to lie at the first and last site. Particles of species 1 enter from the left reservoir into either the first or second site, move rightwards, and leave from either the last or penultimate site. Conversely, particles of species -1 enter from the right reservoir into either the last or penultimate site, move leftwards, and leave from either the first or second site. This dynamics is motivated by a natural random walk on the Weyl group of type D. We compute the exact nonequilibrium steady state distribution using a matrix ansatz building on earlier work of Arita. We then give explicit formulas for the nonequilibrium partition function as well as densities and currents of all species in the steady state, and derive the phase diagram.Limiting directions for random walks in classical affine Weyl groups. Let W be a finite Weyl group and W_a the corresponding affine Weyl group. A random element of W_a can be obtained as a reduced random walk on the alcoves of W_a. By a theorem of Lam (Ann. Prob. 2015), such a walk almost surely approaches one of |W| many directions. We compute these directions when W is B_n, C_n and D_n and the random walk is weighted by Kac and dual Kac labels. This settles Lam's questions for types B and C in the affirmative and for type D in the negative. The main tool is a combinatorial two row model for a totally asymmetric simple exclusion process called the D*-TASEP, with four parameters. By specializing the parameters in different ways, we obtain TASEPs for each of the Weyl groups mentioned above. Computing certain correlations in these TASEPs gives the desired limiting directions.Refined Catalan and Narayana cyclic sieving. We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type A and type B. Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of "ears", non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.
|
|
| 6. |
- Restadh, Petter
(författare)
-
Causal Combinatorics : Edges of the Characteristic Imset Polytopes
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Explaining data in a concise and efficient manner has become increasingly important in today's society. This thesis pertains to the problem of finding causal links within data, and how that can be done from a mathematical perspective. Using the framework of graphical models has several advantages, from interpretability to efficiency. One of the most commonly used graphical model are directed acyclic graphs (DAGs), that has been used to model complex problems within a plethora of areas. Usually, the model in question is either assumed or based on experiments, both of which are methods that have different drawbacks. Inferring a DAG from data alone is however a hard problem and a central question within causal discovery. Due to the combinatorial explosion of the number of DAGs, we cannot do this by hand and therefore we need to design algorithms specifically for this task; several algorithms already exists within this area: PC, GES, MMHC, and Greedy SP, to name but a few. Studený proposed an alternative viewpoint using integer valued multi-set functions (imsets). This in turn allows us to see DAG discovery as a linear optimization problem. Specifically we consider the characteristic imset polytope, $\CIM_n$, whose vertices correspond to Markov equivalence classes of DAGs. A central theme of this thesis is understanding the edge structure and how this can be used in algorithms. Many of the best performing algorithms use a fixed set of moves to greedily transform one DAG to another optimizing a score function. In this thesis we show that the most commonly used moves has a polyhedral interpretation as an edge-walk along $\CIM_n$, thus provide a geometric perspective on these algorithms. This in turn allow us to design algorithms that expand upon earlier algorithms and discuss how certain faces of $\CIM_n$ can be efficiently used to improve on state of the art. Of specific importance are the faces of $\CIM_n$ with clear graphical interpretation, for example $\CIM_G$, the convex hull of all imsets encoding for DAGs with a fixed skeleton $G$. Via introducing a algorithm skeletal greedy CIM, that use conditional independence test to find $G$, and then proceeds in a greedy fashion, we show that these are not only interesting from a theoretical standpoint, but are directly applicable to real data. In general very little is known about the edge structure of $\CIM_n$, especially in terms of the DAGs. However, if we assume that $G$ is a tree, we can in fact give a complete description of all edges of $\CIM_G$. This allow us to give several connections to other well-studied polytopes. Moreover this gives a natural generalization of skeletal greedy CIM, for learning directed trees, sometimes referred to as polytrees.The additional edges, or moves, turns out to be especially useful when we do not have a lot of data. An important measure on the complexity of an edge-walk is the diameter of a polytope. We prove low-degree polynomial bounds, in the number of nodes of the DAGs, of the diameter of $\CIM_n$, $\CIM_G$, and other characteristic imset polytopes. This is surprising as the dimension grows exponentially.As a final method of understanding the edge structure of the characteristic imset polytopes we define the rhombus criterion.It is a simple sufficient condition to determine when two vertices can not form an edge. For several characteristic imset polytopes, the rhombus criterion is both necessary and sufficient, and hence characterize all edges. Therefore we raise the question when this is true for characteristic imset polytopes. We show that almost all pair of vertices of the chordal graph polytope fulfill the rhombus criterion and conjecture it holds for every pair. Using this criterion we also provide a way to compute the edge structure of some $0/1$-polytopes that scales better with dimension.Thus we can computationally show that the rhombus criterion describes the edge structure of $\CIM_n$ for $n\leq 5$ and the edge structure for the chordal graph polytope when $n\leq 6$.
|
|
