%May 95, latex \documentstyle[11pt]{article} \oddsidemargin 0in \topmargin 0in \headheight 0in \headsep 0in \textheight 23.5cm \textwidth 16cm \hsize=7.5in \vsize=11.0in \begin{document} \title {\bf Combinatorics at KTH} \author{} \date{} \maketitle The combinatorics group at KTH was started in 1987. The current members (May 1995) are {\em Anders Bj{\"o}rner, Henrik Eriksson, Kimmo Eriksson, Olle Heden, Johan Karlander, Bernt Lindstr{\"o}m, Lars Svensson}. The current graduate students are {\em Svante Linusson, Dmitrij Kozlov, Johan W{\"a}stlund}. \bigskip \section{Research interests.} \begin{enumerate} \item{} {\bf Combinatorial Coxeter group theory: } The language of reduced expressions; Partial orders: Bruhat order and weak order; Kazhdan-Lusztig theory; Affine groups, permutational representations. \item{} {\bf 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. \item{} {\bf Topological methods in combinatorics and complexity theory: } Topological method; Homology/Betti numbers, homotopy type, shellability, Cohen-Macau\-layness; $f$-vec\-tors; Decision tree complexity; Explicit lower bounds. \item{} {\bf Enumerative combinatorics: } Permutations; Signed permutations; $q$-analogs; M{\"o}bius function; (Forbidden) subwords and factor words (free monoid); Finite Radon transform. \item{} {\bf Matroids and geometry: } Matroids; Algebraic matroids; Oriented matroids; Greedoids; Finite geometries and codes; Partial spreads and Bruen chains; Convex polytopes. \item{} {\bf Strongly convergent games: } Chip firing game; Number firing game; Pebbling game, etc. \end{enumerate} \bigskip \section{Results.} See the list of references. It contains the publications of the group since 1991. \newpage \begin{thebibliography}{ABC} \bibitem{AB36} A. Bj{\"o}rner and M. Wachs, Permutation statistics and linear extensions of posets, J. Combinatorial Theory, Ser. A, {\bf 58} (1991), 85--114. \bibitem{AB37} A. Bj{\"o}rner, L. Lov\'asz and P. W. Shor, Chip-firing games on graphs, European J. Combinatorics {\bf 12} (1991), 283--291. \bibitem{AB38} A. Bj{\"o}rner and G. Kalai, Extended Euler-Poincar\'e 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. \bibitem{AB39} A. Bj{\"o}rner and G. M. Ziegler, Broken circuit complexes: Factorizations and generalizations, J. Combinatorial Theory, Ser. B, {\bf 51} (1991), 96--126. \bibitem{AB40} A. Bj{\"o}rner, The homology and shellability of matroids and geometric lattices, in \lq\lq Matroid Applications''(ed. N. White), Cambridge Univ. Press, 1992, pp. 226--283. \bibitem{AB41} A. Bj{\"o}rner and G.~M.~Ziegler, Introduction to greedoids, in \lq\lq Matroid Applications" (ed. N.~White), Cambridge Univ. Press, 1992, pp. 284--357. \bibitem{AB42} A. Bj{\"o}rner and G.~M.~Ziegler, Combinatorial stratification of complex arrangements, Journal Amer. Math. Soc. {\bf 5} (1992), 105-149. \bibitem{AB43} A. Bj{\"o}rner and C.~Reutenauer, Rationality of the M\"obius function of subword order, Theoretical Computer Sci. {\bf 98} (1992), 53-63. \bibitem{AB44} A. Bj{\"o}rner, L.~Lov\'asz 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. \bibitem{AB45} A. Bj{\"o}rner and J. Karlander, Invertibility of the base Radon transform of a matroid, Discrete Math. {\bf 108} (1992), 139-147. \bibitem{AB46} A. Bj{\"o}rner, J. Karlander and B. Lindstr\"om, , Communication complexity of two decision problems Discrete Appl. Math. {\bf 39} (1992), 161-163. \bibitem{AB47} A. Bj{\"o}rner, Essential chains and homotopy type of posets, Proc. Amer. Math. Soc. {\bf 116} (1992), 1179-1181. \bibitem{AB48} A. Bj{\"o}rner and L.~Lov\'asz, Chip-firing games on directed graphs, Journal Alg. Combinatorics {\bf 1} (1992), 305-328. \bibitem{AB49} A. Bj{\"o}rner and J. Karlander, The mod $p$ rank of incidence matrices for connected uniform hypergraphs, European J.~Combinatorics {\bf 14} (1993), 151-155. \bibitem{AB50} A. Bj{\"o}rner, The M\"obius function of factor order, Theoretical Computer Sci. {\bf 117} (1993), 91-98. \bibitem{AB3} A. Bj{\"o}rner, The mathematical work of Bernt Lindstr\"om, European J.~Combinatorics {\bf 14} (1993), 143-149. \bibitem{AB4} A. Bj{\"o}rner, Matematiken som sk\"on konst och intellektuellt \"aventyr, in ``Vetenskapens vackra verktyg - Matematiken som arbetsredskap'', NFRs {\AA}rsbok 1993, pp. 9-23. \bibitem{AB51} A. Bj{\"o}rner, L.~Lov\'asz, S.~Vre\'cica and R.~{\v Z}ival\-jevi\'c, Chessboard complexes and matching complexes , J.~London Math. Soc. ~(2)~ {\bf 49} (1994), 25-39. \bibitem{AB52} A. Bj{\"o}rner, Linear decision trees, subspace arrangements and M\"obius functions (with L.~Lov\'asz), Journal Amer. Math. Soc. {\bf 7} (1994), 677-706. \bibitem{AB53} A. Bj{\"o}rner and K. Eriksson, Extendable shellability for rank 3 matroid complexes, Discrete Math. {\bf 132} (1994), 373-376. \bibitem{AB54} A. Bj{\"o}rner, Subspace arrangements, in ``First European Congress of Mathematics, Paris 1992'' (eds. A. Joseph et al.), Progress in Math. Series, Vol. 119, Birkh\"auser, Boston, 1994, pp. 321-370. \bibitem{AB55} A. Bj{\"o}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. \bibitem{AB56} A. Bj{\"o}rner and V. Welker, The homology of ``k-equal'' manifolds and related partition lattices , Advances in Math. {\bf 110} (1995), 277--313. \bibitem{AB58} A. Bj{\"o}rner and M. Wachs, Shellable nonpure complexes and posets, Trans. Amer. Math. Soc., to appear. (Preprint 1994) \bibitem{AB59} A. Bj{\"o}rner and B. Sagan, Subspace arrangements of type $B_n$ and $D_n$, J. Algebraic Combinatorics, to appear. (Preprint 1994) \bibitem{AB60} A. Bj{\"o}rner, A general homotopy complementation formula. (Preprint 1994) (Announced in Abstracts of Amer. Math. Soc. {\bf 12} (1991), 205.) \bibitem{AB61} A. Bj{\"o}rner, M.~LasVergnas, B.~Sturmfels, N.~White and G.~M.~Ziegler,\lq\lq Oriented matroids" , Cambridge Univ. Press, 1993. \bibitem{HE4} H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH, 1994. \bibitem{HE5} 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. \bibitem{HE6} H.Eriksson, Pebblings, Electr. J. Combin. 2, 1995, 15p. \bibitem{HE1} 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. \bibitem{HE2} 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. \bibitem{HE3} H. Eriksson and B. Lindstr\"om, Twin checker jumping in $Z^d$, {\it Europ.J. Combinatorics}, 16 (1995), 153--157. \bibitem{KE2} K. Eriksson, Convergence of Mozes's game of numbers, {\it Linear Alg. Appl.}, vol. 166, 1992, 151--165. \bibitem{KE3} K. Eriksson, Strong convergence and a game of numbers, 1991, submitted for publication in {\it Eur. J. Combinatorics}. \bibitem{KE5} 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 {\it Discrete Math.} \bibitem{KE6} K. Eriksson, Reachability is decidable in the numbers game, {\it Theoretical Comp. Science} vol. 131, 1994, 431--439. \bibitem{KE7} K. Eriksson, Chip firing games on mutating graphs, 1992, to appear in {\it SIAM J. Discrete Math}. \bibitem{KE8} K. Eriksson, The number of I-rooted spanning forests, 1992, technical report, KTH. \bibitem{KE9} 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 {\it Discrete Math}. \bibitem{KE10} K. Eriksson, Polygon posets and the weak order of Coxeter groups, 1992, to appear in {\it J. Algebraic Comb.} \bibitem{KE11} K. Eriksson, Forbidden factors and the PS-index of words, 1993, technical report, KTH. \bibitem{KE12} K. Eriksson, A combinatorial proof of the existence of the generic Hecke algebra and $R$-polynomials, 1993, to appear in {\it Math. Scand.} \bibitem{KE13} K. Eriksson, Node firing games on graphs, {\it Contemporary Math.} vol. {\bf 178}, 1994, 117--127. \bibitem{KE15} 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 {\it Discrete Math.} \bibitem{SL4} K. Eriksson and S. Linusson, Combinatorics of Fulton's Essential Set, preprint, KTH 1995. \bibitem{SL5} K. Eriksson and S. Linusson, The Size of Fulton's Essential Set, Electronic Journal of Combinatorics, \#R6, Vol. 2,(1995). \bibitem{OH2} O. Heden, No partial 1-spread of class $[0,\ge 2]_d$ in PG(2d-1,q) exists, {\it Discrete Mathematics}, 87(1991), 215--216. \bibitem{OH3} O. Heden, A greedy search for maximal partial spreads in PG(3,7), {\it Ars Combinatorica}, 32(1991), 253--255. \bibitem{OH4} O. Heden, On the modular n-queen problem, {\it Discrete Mathematics}, 102 (1992) 155--161. \bibitem{OH5} O. Heden, Maximal partial spreads and the modular n-queen problem, {\it Discrete Mathematics}, 120 (1993), 75--91. \bibitem{OH6} O. Heden, A binary Perfect Code of Length 15 and Codimension 0, {\it Designs, Codes and Cryptography}, 4(1994), 213--220. \bibitem{OH7} O. Heden, Maximal partial spreads in PG(3,q) and the the n-queen problem II, to appear in {\it Discrete Mathematics}, 140(1995). \bibitem{OH8} O. Heden, On Bruen chains, to appear in {\it Discrete Mathematics}, 143(1995). \bibitem{JK3} J. Karlander, ``Note: A rank formula for zero-one matrices'', preprint, 1991. \bibitem{JK4} J. Karlander, ``Matrices generated by semilattices'', to appear in {\it Discrete Appl. Math}. \bibitem{JK6} J. Karlander, ``A characterization of affine sign vector systems'', to appear in {\it Eur. J. Combinatorics}. \bibitem{BL1} B. Lindstr\"om, Borromean circles are impossible, {\it Amer. Math. Monthly}, 98 (1991),340--341. \bibitem{BL2} B. Lindstr\"om, On algebraic matroids, {\it Discrete Mathematics}, 111 (1993), 357--359. \bibitem{BL3} B. Lindstr\"om, Another theorem on families of sets, {\it Ars Combinatorica}, 35 (1993),123--124. \bibitem{BL4} B. Lindstr\"om, Enestr\"oms sats 100 \aa r, {\it NORMAT}, 41 (1993).89--90. \bibitem{SL1} S. Linusson, Examples of Non-uniqueness for the Combinatorial Radon Transform Modulo the Symmetric Group, preprint, KTH 1993. (with Jan Boman) \bibitem{SL2} S. Linusson, Partitions with Restricted Block Sizes, M\"obius Functions and the k-of-each Problem, preprint, KTH, 1994. \bibitem{SL3} S. Linusson, M\"obius function and characteristic polynomial for subspace arrangements embedded in $B_{n}$, preprint, KTH, 1994. \bibitem{SL6} S. Linusson, A class of lattices whose intervals are contractible or homotopy spheres, preprint, KTH, 1995. \bibitem{LS1} L. Svensson, A constructive proof of the Hilbert Nullstellensatz, preprint 1993. \bibitem{LS2} L. Svensson, A Gr{\"o}bner basis approach to decidability questions for a generalized version of the chip firing game, preprint 1993. \end{thebibliography} \end{document}