Ändra sökning
Avgränsa sökresultatet
1 - 21 av 21
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
Träffar per sida
• 5
• 10
• 20
• 50
• 100
• 250
Sortering
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
• 1.
KTH, Tidigare Institutioner, Matematik.
KTH, Tidigare Institutioner, Matematik.
A note on blockers in posets2004Ingår i: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 8, nr 2, s. 123-131Artikel i tidskrift (Refereegranskat)

The blocker A* of an antichain A in a finite poset P is the set of elements minimal with the property of having with each member of A a common predecessor. The following is done: (1) The posets P for which A** = A for all antichains are characterized.(2) The blocker A* of a symmetric antichain in the partition lattice is characterized.(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.

• 2.
KTH, Tidigare Institutioner, Matematik.
KTH, Tidigare Institutioner, Matematik.
Estimating the expected reversal distance after a fixed number of reversals2004Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 32, nr 3, s. 439-453Artikel i tidskrift (Refereegranskat)

We address the problem of computing the expected reversal distance of a genome with n genes obtained by applying t random reversals to the identity. A good approximation is the expected transposition distance of a product of t random transpositions in S-n. Computing the latter turns out to be equivalent to computing the coefficients of the length function (i.e., the class function returning the number of parts in an integer partition) when written as a linear combination of the irreducible characters of Sn. Using symmetric functions theory, we compute these coefficients, thus obtaining a formula for the expected transposition distance. We also briefly sketch how to compute the variance.

• 3. Eriksen, Niklas
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Expected reflection distance in G(r, 1, n) after a fixed number of reflections2005Ingår i: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 9, nr 1, s. 21-33Artikel i tidskrift (Refereegranskat)

Extending to r > 1 a formula of the authors, we compute the expected reflection distance of a product of t random reflections in the complex reflection group G (r, 1, n). The result relies on an explicit decomposition of the reflection distance function into irreducible G (r, 1, n) characters and on the eigenvalues of certain adjacency matrices.

• 4.
KTH, Tidigare Institutioner                               , Matematik.
Bruhat intervals of length 4 in Weyl groups2003Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 102, nr 1, s. 163-178Artikel i tidskrift (Refereegranskat)

We determine all isomorphism classes of intervals of length 4 in the Bruhat order on the Weyl groups A(4), B-4, D-4 and F-4. It turns out that there are 24 of them (some of which are dual to each other). Work of Dyer allows us to conclude that these are the only intervals of length 4 that can occur in the Bruhat order on any Weyl group. We also determine the intervals that arise already in the smaller classes of simply laced Weyl groups and symmetric groups. Our method combines theoretical arguments and computer calculations. We also present an independent, completely computerized, approach.

• 5.
KTH, Tidigare Institutioner                               , Matematik.
Combinatorial complexes, Bruhat intervals and reflection distances2003Doktorsavhandling, monografi (Övrigt vetenskapligt)

The various results presented in this thesis are naturallysubdivided into three different topics, namely combinatorialcomplexes, Bruhat intervals and expected reflection distances.Each topic is made up of one or several of the altogether sixpapers that constitute the thesis. The following are some of ourresults, listed by topic:

Combinatorial complexes:

Using a shellability argument, we compute the cohomologygroups of the complements of polygraph arrangements. These arethe subspace arrangements that were exploited by Mark Haiman inhis proof of the n! theorem. We also extend these results toDowling generalizations of polygraph arrangements.

We consider certainB- andD-analogues of the quotient complex Δ(Πn)=Sn, i.e. the order complex of the partition latticemodulo the symmetric group, and some related complexes.Applying discrete Morse theory and an improved version of knownlexicographic shellability techniques, we determine theirhomotopy types.

Given a directed graphG, we study the complex of acyclic subgraphs ofGas well as the complex of not strongly connectedsubgraphs ofG. Known results in the case ofGbeing the complete graph are generalized.

We list the (isomorphism classes of) posets that appear asintervals of length 4 in the Bruhat order on some Weyl group. Inthe special case of symmetric groups, we list all occuringintervals of lengths 4 and 5.

Expected reflection distances:Consider a random walk in the Cayley graph of the complexreflection groupG(r, 1,n) with respect to the generating set of reflections. Wedetermine the expected distance from the starting point aftertsteps. The symmetric group case (r= 1) has bearing on the biologists problem ofcomputing evolutionary distances between different genomes. Moreprecisely, it is a good approximation of the expected reversaldistance between a genome and the genome with t random reversalsapplied to it.

• 6.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
Criteria for rational smoothness of some symmetric orbit closures2010Ingår i: DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, s. 319-330Konferensbidrag (Refereegranskat)

Let G be a connected reductive linear algebraic group over ℂ with an involutionθ. Denote by K the subgroup of fixed points. In certain cases, the K-orbits in the flag variety G/B are indexed by the twisted identities ι(θ) = {θ (w -1)w |w ∈ W} in the Weyl group W. Under this assumption, we establish a criterion for rational smoothness of orbit closures which generalises classical results of Carrell and Peterson for Schubert varieties. That is, whether an orbit closure is rationally smooth at a given point can be determined by examining the degrees in a "Bruhat graph" whose vertices form a subset of ι(θ). Moreover, an orbit closure is rationally smooth everywhere if and only if its corresponding interval in the Bruhat order on ι(θ) is rank symmetric. In the special case K = Sp 2n(ℂ), G = SL 2n(ℂ), we strengthen our criterion by showing that only the degree of a single vertex, the "bottom one", needs to be examined. This generalises a result of Deodhar for type A Schubert varieties.

• 7. Hultman, Axel
Directed subgraph complexes2004Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 11, nr 1Artikel i tidskrift (Refereegranskat)

Let G be a directed graph, and let Delta(G)(ACY) be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of G. Similarly, we define Delta(G)(NSC) to be the simplicial complex with the edge sets of not strongly connected subgraphs of G as simplices. We show that Delta(G)(ACY) is homotopy equivalent to the (n-1-k)-dimensional sphere if G is a disjoint union of k strongly connected graphs. Otherwise, it is contractible. If G belongs to a certain class of graphs, the homotopy type of Delta(G)(NSC) is shown to be a wedge of (2n-4)-dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements.

• 8. Hultman, Axel
Fixed points of involutive automorphisms of the Bruhat order2005Ingår i: Advances in Mathematics, ISSN 0001-8708, E-ISSN 1090-2082, Vol. 195, nr 1, s. 283-296Artikel i tidskrift (Refereegranskat)

Applying a classical theorem of Smith, we show that the poset property of being Gorenstein* over Z(2) is inherited by the subposet of fixed points under an involutive poset automorphism. As an application, we prove that every interval in the Bruhat order on (twisted) involutions in an arbitrary Coxeter group has this property, and we find the rank function. This implies results conjectured by F. Incitti. We also show that the Bruhat order on the fixed points of an involutive automorphism induced by a Coxeter graph automorphism is isomorphic to the Bruhat order on the fixed subgroup viewed as a Coxeter group in its own right.

• 9.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Fixed points of zircon automorphisms2008Ingår i: Order, ISSN 0167-8094, E-ISSN 1572-9273, Vol. 25, nr 2, s. 85-90Artikel i tidskrift (Refereegranskat)

A zircon is a poset in which every principal order ideal is finite and equipped with a so-called special matching. We prove that the subposet induced by the fixed points of any automorphism of a zircon is itself a zircon. This provides a natural context in which to view recent results on Bruhat orders on twisted involutions in Coxeter groups.

• 10.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Link complexes of subspace arrangements2007Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 28, nr 3, s. 781-790Artikel i tidskrift (Refereegranskat)

Given a simplicial hyperplane arrangement H and a subspace arrangement A embedded in H, we define a simplicial complex Delta(A,H) as the subdivision of the link of A induced by R. In particular, this generalizes Steingrimsson's coloring complex of a graph. We do the following: (1) When A is a hyperplane arrangement, Delta(A,H) is shown to be shellable. As a special case, we answer affirmatively a question of Steingrimsson on coloring complexes. (2) For H a Coxeter arrangement of type A or B we obtain a close connection between the Hilbert series of the Stanley-Reisner ring Of Delta(A,H) and the characteristic polynomial of A. This extends results of Steingrimsson and provides an interpretation of chromatic polynomials of hypergraphs and signed graphs in terms of Hilbert polynomials.

• 11.
KTH, Tidigare Institutioner                               , Matematik.
Polygraph arrangements2002Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, nr 8, s. 937-948Artikel i tidskrift (Refereegranskat)

A class of subspace arrangements, Z(n, m), known as polygraph arrangements was exploited by Haiman in order to prove the n! theorem. By showing that their intersection lattices, L(Z(n, m)), are EL-shellable, we determine the cohomology groups of the complements of the arrangements. Moreover, we generalize the shellability results to a class of lattices which deserve to be called Dowling generalizations of L (Z (n, m)). As a consequence, we obtain the cohomology groups of the complements of certain Dowling analogues of polygraph arrangements.

• 12.
KTH, Tidigare Institutioner                               , Matematik.
Quotient complexes and lexicographic shellability2002Ingår i: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 16, nr 1, s. 83-96Artikel i tidskrift (Refereegranskat)

Let Pi(n,k,k) and Pi(n,k,h), h < k, denote the intersection lattices of the k-equal subspace arrangement of type D-n and the k, h-equal subspace arrangement of type B-n respectively. Denote by S-n(B) the group of signed permutations. We show that Delta(Pi(n,k,k))/S-n(B) is collapsible. For Delta(Pi(n,k,h))/S-n(B),h < k, we show the following. If n = 0 (mod k), then it is homotopy equivalent to a sphere of dimension 2n/k = 2. If n = h (mod k), then it is homotopy equivalent to a sphere of dimension 2n-h/k-1. Otherwise, it is contractible. Immediate consequences for the multiplicity of the trivial characters in the representations of S-n(B) on the homology groups of Delta(Pi(n,k,k)) and Delta(Pi(n,k,h)) are stated. The collapsibility of Delta (Pi(n,k,k))/S-n(B) is established using a discrete Morse function. The same method is used to show that Delta(Pi(n,k,h))/S-n(B), h < k, is homotopy equivalent to a certain subcomplex. The homotopy type of this subcomplex is calculated by showing that it is shellable. To do this, we are led to introduce a lexicographic shelling condition for balanced cell complexes of boolean type. This extends to the non-pure case work of P. Hersh (Preprint, 2001) and specializes to the CL-shellability of A. Bjorner and M. Wachs (Trans. Amer. Math. Soc. 4 (1996), 1299-1327) when the cell complex is an order complex of a poset.

• 13.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The combinatorics of twisted involutions in Coxeter groups2005Ingår i: FPSAC Proceedings 2005: 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics, 2005, s. 195-206Konferensbidrag (Refereegranskat)

The open intervals in the Bruhat order on twisted involutions in a Coxeter group are shown to be PL spheres. This implies results conjectured by F. Incitti and sharpens the known fact that these posets are Gorenstein* over ℤ 2. We also introduce a Boolean cell complex which is an analogue for twisted involutions of the Coxeter complex. Several classical Coxeter complex properties are shared by our complex. When the group is finite, it is a shellable sphere, shelling orders being given by the linear extensions of the weak order on twisted involutions. Furthermore, the h-polynomial of the complex coincides with the polynomial counting twisted involutions by descents. In particular, this gives a type independent proof that the latter is symmetric.

• 14.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The combinatorics of twisted involutions in Coxeter groups2007Ingår i: Transactions of the American Mathematical Society, ISSN 0002-9947, E-ISSN 1088-6850, Vol. 359, nr 6, s. 2787-2798Artikel i tidskrift (Refereegranskat)

The open intervals in the Bruhat order on twisted involutions in a Coxeter group are shown to be PL spheres. This implies results conjectured by F. Incitti and sharpens the known fact that these posets are Gorenstein* over Z(2). We also introduce a Boolean cell complex which is an analogue for twisted involutions of the Coxeter complex. Several classical Coxeter complex properties are shared by our complex. When the group is finite, it is a shellable sphere, shelling orders being given by the linear extensions of the weak order on twisted involutions. Furthermore, the h-polynomial of the complex coincides with the polynomial counting twisted involutions by descents. In particular, this gives a type-independent proof that the latter is symmetric.

• 15.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The finite antichain property in Coxeter groups2007Ingår i: Arkiv för matematik, ISSN 0004-2080, E-ISSN 1871-2487, Vol. 45, nr 1, s. 61-69Artikel i tidskrift (Refereegranskat)

We prove that the weak order on an infinite Coxeter group contains infinite antichains if and only if the group is not affine.

• 16.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The topology of spaces of phylogenetic trees with symmetry2007Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 307, nr 14, s. 1825-1832Artikel i tidskrift (Refereegranskat)

Natural Dowling analogues of the complex of phylogenetic trees are studied. Using discrete Morse theory, we find their homotopy types. In the process, the homotopy types of certain subposets of Dowling lattices are determined.

• 17.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Twisted identities in Coxeter groups2008Ingår i: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 28, nr 2, s. 313-332Artikel i tidskrift (Refereegranskat)

Given a Coxeter system ( W, S) equipped with an involutive automorphism theta, the set of twisted identities is iota(theta) = {theta(w(-1))w vertical bar w is an element of W}. We point out how iota(theta) shows up in several contexts and prove that if there is no s is an element of S such that s theta(s) is of odd order greater than 1, then the Bruhat order on iota(theta) is a graded poset with rank function. given by halving the Coxeter length. Under the same condition, it is shown that the order complexes of the open intervals either are PL spheres or Z-acyclic. In the general case, contractibility is shown for certain classes of intervals. Furthermore, we demonstrate that sometimes these posets are not graded. For the Poincare series of iota(theta), i.e. its generating function with respect to rho, a factorisation phenomenon is discussed.

• 18.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The topology of the space of matrices of Barvinok rank two2010Ingår i: Beiträge zur Algebra und Geometrie, ISSN 0138-4821, Vol. 51, nr 2, s. 373-390Artikel i tidskrift (Refereegranskat)

The Barvinok rank of a d x n matrix is the minimum number of  points in Rd such that the tropical convex hull of the points contains all columns of the matrix. The concept originated in work by Barvinok and others on the travelling salesman problem. Our object of study is the space of real d x n matrices of Barvinok rank two. Let Bd,n denote this space modulo rescaling and translation. We show that Bd,n is a manifold, thereby settling a  conjecture due to Develin. In fact, Bd,n is homeomorphic to the quotient of the product of spheres Sd-2 x Sn-2 under the involution which sends each point to its antipode simultaneously in both  components.  In addition, using discrete Morse theory, we compute the integral homology of Bd,n. Assuming d \ge n, for odd d the homology turns out to be   isomorphic to that of Sd-2 x RPn-2. This  is true also for even d up to degree d-3, but the two cases differ from degree d-2 and up. The homology computation straightforwardly extends to more general  complexes of the form (Sd-2 x X)//Z2, where X is a finite cell  complex of dimension at most d-2 admitting a free  Z2-action.

• 19.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
From Bruhat intervals to intersection lattices and a conjecture of Postnikov2008Ingår i: FPSAC - Int. Conf. Form. Power Ser. Algebraic Comb., 2008, s. 203-214Konferensbidrag (Refereegranskat)

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.

• 20.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
From Bruhat intervals to intersection lattices and a conjecture of Postnikov2009Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 116, nr 3, s. 564-580Artikel i tidskrift (Refereegranskat)

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.

• 21.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Pattern avoidance and Boolean elements in the Bruhat order on involutions2009Ingår i: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 30, nr 1, s. 87-102Artikel i tidskrift (Refereegranskat)

We show that the principal order ideal of an element w in the Bruhat order on involutions in a symmetric group is a Boolean lattice if and only if w avoids the patterns 4321, 45312 and 456123. Similar criteria for signed permutations are also stated. Involutions with this property are enumerated with respect to natural statistics. In this context, a bijective correspondence with certain Motzkin paths is demonstrated.

1 - 21 av 21
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
v. 2.35.4
| | | |