| 1. |
- Backelin, Jörgen, et al.
(författare)
-
Parity splits by triple point distances in X-trees
- 2006
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 10:1, s. 1-18
-
Tidskriftsartikel (refereegranskat)abstract
- At the conference Dress defined parity split maps by triple point distance and asked for a characterisation of such maps coming from binary phylogenetic X-trees. This article gives an answer to that question. The characterisation for X-trees can be easily described as follows: If all restrictions of a split map to sets of five or fewer elements is a parity split map for an X-tree, then so is the entire map. To ensure that the parity split map comes from an X-tree which is binary and phylogenetic, we add two more technical conditions also based on studying at most five points at a time.
|
|
| 2. |
- Bousquet-Melou, Mireille, et al.
(författare)
-
On the independence complex of square grids
- 2008
-
Ingår i: Journal of Algebraic Combinatorics. - : Springer Science and Business Media LLC. - 0925-9899 .- 1572-9192. ; 27:4, s. 423-450
-
Tidskriftsartikel (refereegranskat)abstract
- The enumeration of independent sets of regular graphs is of interest in statistical mechanics, as it corresponds to the solution of hard-particle models. In 2004, it was conjectured by Fendley et al., that for some rectangular grids, with toric boundary conditions, the alternating number of independent sets is extremely simple. More precisely, under a coprimality condition on the sides of the rectangle, the number of independent sets of even and odd cardinality always differ by 1. In physics terms, this means looking at the hard-particle model on these grids at activity -1. This conjecture was recently proved by Jonsson. Here we produce other families of grid graphs, with open or cylindric boundary conditions, for which similar properties hold without any size restriction: the number of independent sets of even and odd cardinality always differ by 0, +/- 1, or, in the cylindric case, by some power of 2. We show that these results reflect a stronger property of the independence complexes of our graphs. We determine the homotopy type of these complexes using Forman's discrete Morse theory. We find that these complexes are either contractible, or homotopic to a sphere, or, in the cylindric case, to a wedge of spheres. Finally, we use our enumerative results to determine the spectra of certain transfer matrices describing the hard-particle model on our graphs at activity -1. These results parallel certain conjectures of Fendley et al., proved by Jonsson in the toric case.
|
|
| 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. |
- Eriksson, Henrik, et al.
(författare)
-
Dense packing of patterns in a permutation
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:3-4, s. 459-470
-
Tidskriftsartikel (refereegranskat)abstract
- We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.
|
|
| 5. |
- Gill, Jonna, et al.
(författare)
-
A regular decomposition of the edge-product space of phylogenetic trees
- 2008
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 41:2, s. 158-176
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the topology and combinatorics of a topological space called the edge-product space that is generated by the set of edge-weighted finite labelled trees. This space arises by multiplying the weights of edges on paths in trees, and is closely connected to tree-indexed Markov processes in molecular evolutionary biology. In particular, by considering combinatorial properties of the Tuffley poset of labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset.
|
|
| 6. |
- Gill, Jonna, et al.
(författare)
-
The k-assignment polytope
- 2009
-
Ingår i: DISCRETE OPTIMIZATION. - : Elsevier BV. - 1572-5286. ; 6:2, s. 148-161
-
Tidskriftsartikel (refereegranskat)abstract
- In 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.
|
|
| 7. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2008
-
Ingår i: FPSAC - Int. Conf. Form. Power Ser. Algebraic Comb.. ; , s. 203-214
-
Konferensbidrag (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w ∈ S n is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups.
|
|
| 8. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2009
-
Ingår i: Journal of combinatorial theory. Series A (Print). - : Elsevier BV. - 0097-3165 .- 1096-0899. ; 116:3, s. 564-580
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w is an element of (sic)(n). is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups. A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.
|
|
| 9. |
- Johansson, Robert, et al.
(författare)
-
Pattern avoidance in alternating sign matrices
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:04-mar, s. 471-480
-
Tidskriftsartikel (refereegranskat)abstract
- We generalize the definition of a pattern from permutations to alternating sign matrices. The number of alternating sign matrices avoiding 132 is proved to be counted by the large Schroder numbers, 1, 2, 6, 22, 90, 394,.... We give a bijection between 132-avoiding alternating sign matrices and Schroder paths, which gives a refined enumeration. We also show that the 132-, 123-avoiding alternating sign matrices are counted by every second Fibonacci number.
|
|
| 10. |
- Linusson, Svante, et al.
(författare)
-
Completing a (k-1)-assignment
- 2007
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 16:4, s. 621-629
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the distribution of the value of the optimal k-assignment in an in x n matrix, where the entries are independent exponential random variables with arbitrary rates. We give closed formulas for both the Laplace transform of this random variable and for its expected value under the condition that there is a zero-cost (k - 1)-assignment.
|
|
