123 research outputs found
The k-assignment polytope
No full textIn this paper we Study the structure of the k-assignment polytope, whose vertices are the m x n (0, 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. A representation of the faces by certain bipartite graphs is given. This tool is used to describe the properties of the polytope, especially a complete description of the cover relation in the face poset of the polytope and an exact expression for the diameter. An ear decomposition of these bipartite graphs is constructed.Original Publication:Jonna Gill and Svante Linusson, The k-assignment polytope, 2009, DISCRETE OPTIMIZATION, (6), 2, 148-161.http://dx.doi.org/10.1016/j.disopt.2008.10.003Copyright: Elsevier Science B.V. Amsterdamhttp://www.elsevier.com
Extended pattern avoidance
No full textAbstractA 0–1 matrix is said to be extendably τ-avoiding if it can be the upper left corner of a τ-avoiding permutation matrix. This concept arose in Eriksson and Linusson (Electron. J. Combin. 2 (1995) R6) where the surprising result that the number of extendably 321-avoiding rectangles are enumerated by the ballot numbers was proved. Here we study the other five patterns of length three. The main result is that the six patterns of length three divide into only two cases, no easy symmetry can explain this. Another result is that the Simion–Schmidt–West bijection for permutations avoiding patterns 12τ and 21τ works also for extended pattern avoidance. As an application, we use the results on extended pattern avoidance to prove a sequence of refinements on the enumeration of permutations avoiding patterns of length 3.The results and proofs use many properties and refinements of the Catalan numbers
On Percolation and the Bunkbed Conjecture
No full textWe study a problem on edge percolation on product graphs G x K-2. Here G is any finite graph and K-2 consists of two vertices {0, 1} connected by an edge. Every edge in G x K-2 is present with probability p independent of other edges. The bunkbed conjecture states that for all G and p, the probability that (u, 0) is in the same component as (v, 0) is greater than or equal to the probability that (u, 0) is in the same component as (v, 1) for every pair of vertices u, v is an element of G. We generalize this conjecture and formulate and prove similar statements for randomly directed graphs. The methods lead to a proof of the original conjecture for special classes of graphs G, in particular outerplanar graphs.</p
Epistasis, reguläre Unterteilungen und Spannbäume
No full textIn this thesis, we use techniques from polyhedral geometry and statistics in order to detect and quantify biological interactions within a system of genes or species described by a given data set.
Our concept relies on the theory of regular subdivisions. A regular subdivision decomposes a space into convex cells and can be used to showcase some distinct aspects of the given data set in its cell structure. After all, one can implement and compute with regular subdivisions and this is an important feature of polyhedral and discrete geometry.
The way these cells spatially relate to each other is exploited to determine a list of moderate length with potentially significant biological interactions. A statistical test allows us to diminish this list further and to point to few but statistically significant interactions. A major benefit of our method, and in a way this is reciprocal compared to other existing methods, is the concise extent of our findings which allows for communicating them in a comprehensive form, for instance in data tables or specifically developed bar diagrams.
We applied our methods to several experimentally obtained genetic and microbiome data sets. A central use case was the analysis of two instances of Drosophila melanogaster fly gut microbiome studies. The gut of these fruit flies has a microbiome with a small number of constituting species and can be manipulated in the laboratory by regulation of the food. The two Drosophila data sets we applied our methods on describe a microbiome system with five species and hence each of the two data sets can be related to some regular subdivision of the 5-dimensional 0/1-cube from where our method departs. We are able to point to significant higher dimensional interactions which are not perceived by other existing methods and, in particular, are not captured by looking at pairs of interacting species only.
Further, we reinterpret and analyze our method mathematically. It produces and is in some way equivalent to naming a network of shortest genetic distances, i.e. a minimum spanning tree of a certain fixed weighted graph with biological meaning. Tropical hypersurfaces, central objects of tropical geometry, which is an active field of research at the border of polyhedral, discrete and algebraic geometry, encapsulate these structures inside their 1-dimensional skeleton. We determine the parameter space of the minimum spanning trees arising this way. It turns out to be encoded by a collection of cones given by linear hyperplanes. For a few elected examples we computed an explicit representation of all occuring parameter cones. Yet, this rapidly reaches limits of complexity.
The rest of this thesis is about an achievement beyond these limits. Given a cell decomposition in some implicit form, one may not be able to recuperate the defining geometric data for every cell. But it still may be possible to enumerate them. We present a method for computing the number of chambers of a hyperplane arrangement in real euclidean space which uses purely combinatorial techniques and which makes use of the combinatorial symmetries of the given hyperplane arrangement. With this method, it was possible to compute the previously unknown number of chambers of the ninth resonance arrangement given by 511 hyperplanes in R^9.In dieser Arbeit werden Techniken aus der polyedrischen Geometrie und der Statistik vorgestellt, die benutzt werden können, um biologische Wechselwirkungen in einem durch Datensätze beschriebenen Gen- oder Speziensystem aufzufinden und zu quantifizieren.
Unser Konzept beruht auf der Theorie der regulären Unterteilungen. Eine reguläre Unterteilung zerlegt einen Raum in konvexe Zellen, die im vorliegenden Fall dazu dienen, ausgewiesene Eigenschaften der zugrundeliegenden Daten aufzuzeigen. Desweiteren lassen sich reguläre Unterteilungen in Computerprogrammen implementieren und berechnen, was allgemein einen wichtigen Aspekt der polyedrischen und diskreten Geometrie darstellt.
Der räumliche Bezug der Zellen zueinander wird hierbei benutzt, um eine Liste angemessener Länge mit potenziell signifikanten biologischen Wechselwirkungen zu erstellen. Desweiteren dient ein statistischer Signifikanztest zur weiteren Ausdünnung dieser Liste, die schließlich nur noch statistisch nachweißbar signifikante Wechselwirkungen enthält. Durch die Bündelung und Konzentration auf relevante Wechselwirkungen zeichnet sich unsere Methode wesentlich aus, da dies sich durchaus konträr zu den bereits existierenden Methoden verhält und eine stringente Kommunikation der Ergebnisse gestattet, beispielsweise in Form von Datentabellen oder eigens konzipierter Bardiagramme.
Wir haben unsere Methode auf mehrere Experimentaldatensätze mit Genetik- und Mikrobiombezug angewandt. Ein zentraler Anwendungsfall stellte dabei die Analyse zweier Datensätze dar, die das Mikrobiom des Magens der Drosophila melanogaster Fliege experimentell erfassen. Das Mikrobiom des Magens dieser Fruchtfliege hat die besondere Eigenschaft, durch eine geringe Anzahl von teilhabenden Spezien bestimmt und im Labor leicht manipulierbar zu sein, etwa durch Regulierung des Futters. Die zwei Drosophila Datensätze, die wir betrachteten, beschreiben jeweils ein Mikrobiomsystem mit fünf konstituierenden Spezien und können folglich mit regulären Unterteilungen des fünfdimensionalen 0/1-Würfels assoziiert werden, welche die von uns entwickelte Methode verarbeitet. Es war uns möglich, höherdimensionale Wechselwirkungen zu finden, die von den bereits existierenden Methoden nicht gesehen werden und insbesondere vom Paarvergleich wechselwirkender Spezien übergangen werden.
Desweiteren interpretieren und analysieren wir unsere biologisch motivierte Methode innermathematisch. Im Einzelfall ist der Verlauf dieser äquivalent zur Konstruktion eines Spannbaums minimalen Gewichts in einem festgeschriebenen gewichteten Graph. Dieser Spannbaum lässt sich biologisch wiederum als Netzwerk kürzester genetischer Distanz interpretieren. Tropische Hyperflächen sind zentrale Objekte der tropischen Geometrie, eines eigens für sich aktiven Forschungsgebiets mit Anknüpfungspunkten zur polyedrischen, diskreten und algebraischen Geometrie. Diese Hyperflächen enthalten die betreffenden minimalen Spannbäume in ihrem eindimensionalen Skelett. Wir zeigen, dass der Parameterbereich dieser minimalen Spannbäume durch eine Sammlung polyedrischer Kegel gegeben ist. Für ausgewählte, kleine Bespiele gelingt es, eine explizite Darstellung für jeden einzelnen Parameterkegel zu berechnen. Dennoch stößt man dabei schnell auf unüberwindbare Komplexitätsschranken.
Der Rest dieser Arbeit beschäftigt sich mit einer Thematik, die jenseits dieser Komplexitätsschranken liegt. Zwar mag es für eine implizit gegebene Zellzerlegung mit den aktuellen Methoden unmöglich sein, für jede einzelne Zelle eine explizite geometrische Beschreibung zu errechnen, jedoch kann durchaus eine Abzählung der Zellen erfolgen. Wir präsentieren eine rein kombinatorische Methode zur Abzählung der Kammern eines reellen Hyperebenenarrangements, die wesentlich auf der Ausnutzung kombinatorischer Symmetrie fußt. Mit dieser Methode war es uns möglich, die zuvor unbekannte Kammeranzahl des neunten Resonanzarrangements zu bestimmen, das durch 511 Hyperebenen im R^9 gegeben ist.DFG, 286237555, TRR 195: Symbolische Werkzeuge in der Mathematik und ihre Anwendun
n! matchings, n! posets
No full textWe show that there are matchings on points without, so called, left (neighbor) nestings. We also define a set of naturally labeled -free posets, and show that there are such posets on elements. Our work was inspired by Bousquet-M\'elou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884--909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabeled -free posets, permutations avoiding a specific pattern, and so called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-M\'elou et al.\ and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled -free posets. We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections maps via certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) \#R53
The Probability Of The Alabama Paradox
No full textHamilton's method is a natural and common method to distribute seats proportionally between states (or parties) in a parliament. In the USA it has been abandoned due to some drawbacks, in particular the possibility of the Alabama paradox, but it is still in use in many other countries. In this paper we give, under certain assumptions, a closed formula for the asymptotic probability, as the number of seats tends to infinity, that the Alabama paradox occurs given the vector p(l), ..., p(m) of relative sizes of the states. From the formula we deduce a number of consequences. For example, the expected number of states that will suffer from the Alabama paradox is asymptotically bounded above by 1/e and on average approximately 0.123.</p
CORRELATIONS IN THE MULTISPECIES TASEP AND A CONJECTURE BY LAM
No full textWe study correlations in the multispecies TASEP on a ring. Results on the correlation of two adjacent points prove two conjectures by Thomas Lam on (a) the limiting direction of a reduced random walk in (A) over tilde (n-1) and (b) the asymptotic shape of a random integer partition with no hooks of length n, a so called n-core. We further investigate two-point correlations far apart and three-point nearest neighbour correlations and prove explicit formulas in almost all cases. These results can be seen as a finite strengthening of correlations in the TASEP speed process by Amir, Angel and Valko. We also give conjectures for certain higher order nearest neighbour correlations. We find an unexplained independence property (provably for two points, conjecturally for more points) between points that are closer in position than in value that deserves more study
An inhomogeneous multispecies TASEP on a ring
No full textWe reinterpret and generalize conjectures of Lam and Williams as statements about the stationary distribution of a multispecies exclusion process on the ring. The central objects in our study are the multiline queues of Ferrari and Martin. We make some progress on some of the conjectures in different directions. First, we prove Lam and Williams' conjectures in two special cases by generalizing the rates of the Ferrari-Martin transitions. Secondly, we define a new process on multiline queues, which have a certain minimality property. This gives another proof for one of the special cases; namely arbitrary jump rates for three species. (C) 2014 Elsevier Inc. All rights reserved
Proportionella val inom kommunfullmäktige [Elektronisk resurs]
No full textVi diskuterar två olika problem som kan uppstå vid proportionella val i kommunfullmäktige och regionfullmäktige når ett parti försöker en kupp genom att utan samtycke gå i kartell med ett annat parti vid val till nämnd eller styrelse, vilket aktualiserades i åtminstone ett par fall hösten 2018. Det första problemet är vad sådana oönskade valkarteller kan få för effekter, och vilka möjligheter det finns för ett parti att skydda sig från att bli del i en oönskad valkartell. Det andra problemet är att i en sådan valkartell kan ett parti genom att splittra upp sina kandidater strategiskt på flera olika valsedlar få fler platser i en nämnd är vad som är proportionellt. Detta andra problem bottnar i att lagen om proportionella val stipulerar att Thieles metod skall användas för fördelning inom kartellen. På detta problem finns en enkel matematisk lösning och vi argumenterar för att man skall byta till Phragméns metod som används för motsvarande val till utskott i riksdagen.</p
First critical probability for a problem on random orientations in G(n, p)
No full textWe study the random graph G(n, p) with a random orientation. For three fixed vertices s, a, b in G(n, p) we study the correlation of the events {a → s} (there exists a directed path from a to s) and {s → b}. We prove that asymptotically the correlation is negative for small p, p < C1 C1, where C1 ≈ 0.3617, positive for n n p = p2(n). Computer aided computations suggest that p2(n) = C2 < p < 2 n and up t
- …
