Combinatorics at KTH

The combinatorics group at KTH was started in 1987. The current members (May 1995) are Anders Björner, Henrik Eriksson, Kimmo Eriksson, Olle Heden, Johan Karlander, Bernt Lindström, Lars Svensson. The current graduate students are Svante Linusson, Dmitrij Kozlov, Johan Wästlund.

1 Research interests.

1. Combinatorial Coxeter group theory: The language of reduced expressions; Partial orders: Bruhat order and weak order; Kazhdan-Lusztig theory; Affine groups, permutational representations.

2. Subspace arrangements: Arrangements (hyperplanes and the general case); Intersection lattice (in particular partitions with forbidden block sizes); “k-equal” arrangements of type A_{n}, B_{n}, D_{n}; Reflection arrangements: Arrangements from hypergraphs, simplicial complexes, etc.

3. Topological methods in combinatorics and complexity theory: Topological method; Homology/Betti numbers, homotopy type, shellability, Cohen-Macaulayness; fvectors; Decision tree complexity; Explicit lower bounds.

4. Enumerative combinatorics: Permutations; Signed permutations; q-analogs; Möbius function; (Forbidden) subwords and factor words (free monoid); Finite Radon transform.

5. Matroids and geometry: Matroids; Algebraic matroids; Oriented matroids; Greedoids; Finite geometries and codes; Partial spreads and Bruen chains; Convex polytopes.

6. Strongly convergent games: Chip firing game; Number firing game; Pebbling game, etc.

2 Results.

See the list of references. It contains the publications of the group since 1991.

References

[1] A. Björner and M. Wachs, Permutation statistics and linear extensions of posets, J. Combinatorial Theory, Ser. A, 58 (1991), 85–114.

[2] A. Björner, L. Lovász and P. W. Shor, Chip-firing games on graphs, European J. Combinatorics 12 (1991), 283–291.

[3] A. Björner and G. Kalai, Extended Euler-Poincaré relations for cell complexes , in “Applied Geometry and Discrete Mathematics (The Victor Klee Festschrift)” (eds. P. Gritzmann and B. Sturmfels), Amer. Math. Soc., Providence, R. I., 1991, pp. 81–89.

[4] A. Björner and G. M. Ziegler, Broken circuit complexes: Factorizations and generalizations, J. Combinatorial Theory, Ser. B, 51 (1991), 96–126.

[5] A. Björner, The homology and shellability of matroids and geometric lattices, in “Matroid Applications”(ed. N. White), Cambridge Univ. Press, 1992, pp. 226–283.

[6] A. Björner and G. M. Ziegler, Introduction to greedoids, in “Matroid Applications” (ed. N. White), Cambridge Univ. Press, 1992, pp. 284–357.

[7] A. Björner and G. M. Ziegler, Combinatorial stratification of complex arrangements, Journal Amer. Math. Soc. 5 (1992), 105-149.

[8] A. Björner and C. Reutenauer, Rationality of the Möbius function of subword order, Theoretical Computer Sci. 98 (1992), 53-63.

[9] A. Björner, L. Lovász and A. Yao, Linear decision trees: volume estimates and topological bounds, in: Proc. 24th ACM Symp. on Theory of Computing (May 1992), ACM Press, N.Y., 1992, pp. 170-177.

[10] A. Björner and J. Karlander, Invertibility of the base Radon transform of a matroid, Discrete Math. 108 (1992), 139-147.

[11] A. Björner, J. Karlander and B. Lindström, , Communication complexity of two decision problems Discrete Appl. Math. 39 (1992), 161-163.

[12] A. Björner, Essential chains and homotopy type of posets, Proc. Amer. Math. Soc. 116 (1992), 1179-1181.

[13] A. Björner and L. Lovász, Chip-firing games on directed graphs, Journal Alg. Combinatorics 1 (1992), 305-328.

[14] A. Björner and J. Karlander, The mod p rank of incidence matrices for connected uniform hypergraphs, European J. Combinatorics 14 (1993), 151-155.

[15] A. Björner, The Möbius function of factor order, Theoretical Computer Sci. 117 (1993), 91-98.

[16] A. Björner, The mathematical work of Bernt Lindström, European J. Combinatorics 14 (1993), 143-149.

[17] A. Björner, Matematiken som skön konst och intellektuellt äventyr, in “Vetenskapens vackra verktyg - Matematiken som arbetsredskap”, NFRs Årsbok 1993, pp. 9-23.

[18] A. Björner, L. Lovász, S. Vrećica and R. Živaljević, Chessboard complexes and matching complexes , J. London Math. Soc. (2) 49 (1994), 25-39.

[19] A. Björner, Linear decision trees, subspace arrangements and Möbius functions (with L. Lovász), Journal Amer. Math. Soc. 7 (1994), 677-706.

[20] A. Björner and K. Eriksson, Extendable shellability for rank 3 matroid complexes, Discrete Math. 132 (1994), 373-376.

[21] A. Björner, Subspace arrangements, in “First European Congress of Mathematics, Paris 1992” (eds. A. Joseph et al.), Progress in Math. Series, Vol. 119, Birkhäuser, Boston, 1994, pp. 321-370.

[22] A. Björner, Partial unimodality for f-vectors of simplicial polytopes and spheres, in “Proceedings of Jerusalem Combinatorics Conference, 1993” (eds. H. Barcelo and G. Kalai), Contemporary Math. Series, Vol. 178, Amer. Math. Soc., 1994, pp. 45–54.

[23] A. Björner and V. Welker, The homology of “k-equal” manifolds and related partition lattices , Advances in Math. 110 (1995), 277–313.

[24] A. Björner and M. Wachs, Shellable nonpure complexes and posets, Trans. Amer. Math. Soc., to appear. (Preprint 1994)

[25] A. Björner and B. Sagan, Subspace arrangements of type B_{n} and D_{n}, J. Algebraic Combinatorics, to appear. (Preprint 1994)

[26] A. Björner, A general homotopy complementation formula. (Preprint 1994) (Announced in Abstracts of Amer. Math. Soc. 12 (1991), 205.)

[27] A. Björner, M. LasVergnas, B. Sturmfels, N. White and G. M. Ziegler,“Oriented matroids” , Cambridge Univ. Press, 1993.

[28] H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH, 1994.

[29] H. Eriksson, Rat races and the hook length formula, Proceedings of the 5th conference on Formal Power Series and Algebraic Combinatorics, Firenze, 1993, 179-185.

[30] H.Eriksson, Pebblings, Electr. J. Combin. 2, 1995, 15p.

[31] H. Eriksson and K. Eriksson, Chip-firing, Coxeter words and acyclic edge orientations, 1993, in the proceedings of the Conference on formal power series and algebraic combinatorics, New Jersey, May 1994.

[32] H. Eriksson and K. Eriksson, Affine Coxeter groups as infinite permutations (extended abstract, 1994. To appear in the proceedings of the Conference on formal power series and algebraic combinatorics, Paris, May 1995.

[33] H. Eriksson and B. Lindström, Twin checker jumping in Z^{d}, Europ.J. Combinatorics, 16 (1995), 153–157.

[34] K. Eriksson, Convergence of Mozes’s game of numbers, Linear Alg. Appl., vol. 166, 1992, 151–165.

[35] K. Eriksson, Strong convergence and a game of numbers, 1991, submitted for publication in Eur. J. Combinatorics.

[36] K. Eriksson, The numbers game and Coxeter groups, 1992, in the proceedings of the Conference on formal power series and algebraic combinatorics, Montreal, June 1992. To appear in Discrete Math.

[37] K. Eriksson, Reachability is decidable in the numbers game, Theoretical Comp. Science vol. 131, 1994, 431–439.

[38] K. Eriksson, Chip firing games on mutating graphs, 1992, to appear in SIAM J. Discrete Math.

[39] K. Eriksson, The number of I-rooted spanning forests, 1992, technical report, KTH.

[40] K. Eriksson, Strong convergence and the polygon property of 1-player games, 1992, in the proceedings of the Conference on formal power series and algebraic combinatorics, Firenze, June 1993. To appear in Discrete Math.

[41] K. Eriksson, Polygon posets and the weak order of Coxeter groups, 1992, to appear in J. Algebraic Comb.

[42] K. Eriksson, Forbidden factors and the PS-index of words, 1993, technical report, KTH.

[43] K. Eriksson, A combinatorial proof of the existence of the generic Hecke algebra and R-polynomials, 1993, to appear in Math. Scand.

[44] K. Eriksson, Node firing games on graphs, Contemporary Math. vol. 178, 1994, 117–127.

[45] K. Eriksson, Reduced words in affine Coxeter groups, 1993, in the proceedings of the Conference on formal power series and algebraic combinatorics, New Jersey, May 1994. To appear in Discrete Math.

[46] K. Eriksson and S. Linusson, Combinatorics of Fulton’s Essential Set, preprint, KTH 1995.

[47] K. Eriksson and S. Linusson, The Size of Fulton’s Essential Set, Electronic Journal of Combinatorics, #R6, Vol. 2,(1995).

[48] O. Heden, No partial 1-spread of class [0, ≥ 2]_{d} in PG(2d-1,q) exists, Discrete Mathematics, 87(1991), 215–216.

[49] O. Heden, A greedy search for maximal partial spreads in PG(3,7), Ars Combinatorica, 32(1991), 253–255.

[50] O. Heden, On the modular n-queen problem, Discrete Mathematics, 102 (1992) 155–161.

[51] O. Heden, Maximal partial spreads and the modular n-queen problem, Discrete Mathematics, 120 (1993), 75–91.

[52] O. Heden, A binary Perfect Code of Length 15 and Codimension 0, Designs, Codes and Cryptography, 4(1994), 213–220.

[53] O. Heden, Maximal partial spreads in PG(3,q) and the the n-queen problem II, to appear in Discrete Mathematics, 140(1995).

[54] O. Heden, On Bruen chains, to appear in Discrete Mathematics, 143(1995).

[55] J. Karlander, “Note: A rank formula for zero-one matrices”, preprint, 1991.

[56] J. Karlander, “Matrices generated by semilattices”, to appear in Discrete Appl. Math.

[57] J. Karlander, “A characterization of affine sign vector systems”, to appear in Eur. J. Combinatorics.

[58] B. Lindström, Borromean circles are impossible, Amer. Math. Monthly, 98 (1991),340– 341.

[59] B. Lindström, On algebraic matroids, Discrete Mathematics, 111 (1993), 357–359.

[60] B. Lindström, Another theorem on families of sets, Ars Combinatorica, 35 (1993),123– 124.

[61] B. Lindström, Eneströms sats 100 år, NORMAT, 41 (1993).89–90.

[62] S. Linusson, Examples of Non-uniqueness for the Combinatorial Radon Transform Modulo the Symmetric Group, preprint, KTH 1993. (with Jan Boman)

[63] S. Linusson, Partitions with Restricted Block Sizes, Möbius Functions and the k-of-each Problem, preprint, KTH, 1994.

[64] S. Linusson, Möbius function and characteristic polynomial for subspace arrangements embedded in B_{n}, preprint, KTH, 1994.

[65] S. Linusson, A class of lattices whose intervals are contractible or homotopy spheres, preprint, KTH, 1995.

[66] L. Svensson, A constructive proof of the Hilbert Nullstellensatz, preprint 1993.

[67] L. Svensson, A Gröbner basis approach to decidability questions for a generalized version of the chip firing game, preprint 1993.