On percolation and the bunkbed conjecture (2008)
We study a problem on 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. In edge percolation every edge in G x K_2 is...
On the independence complex of square grids (2008)
Bousquet-Mélou, Mireille, Linusson, Svante, Nevo, Eran
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 Fendleyet al....
From Bruhat intervals to intersection lattices and a conjecture of Postnikov (2007)
Hultman, Axel, Linusson, Svante, Shareshian, John, Sjöstrand, Jonas
We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation $w\in \Sn$ is at most the number of elements below $w$ in...
On the independence complex of square grids (2007)
Bousquet-Mélou, Mireille, Linusson, Svante, Nevo, Eran
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 Fendleyet al....
On the independence complex of square grids (2007)
Bousquet-Mélou, Mireille, Linusson, Svante, Nevo, Eran
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 Fendleyet al....
On the independence complex of square grids (2007)
Bousquet-Mélou, Mireille, Linusson, Svante, Nevo, Eran
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 Fendleyet al....
Complexes of graphs with bounded matching size (2004)
Linusson, Svante, Shareshian, John, Welker, Volkmar
For positive integers k,n, we investigate the simplicial complex NM_k(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other...
Completing a k-1 assignment (2004)
Linusson, Svante, Waestlund, Johan
We consider the distribution of the value of the optimal k-assignment in an m x n-matrix, where the entries are independent exponential random variables with arbitrary rates. We give closed formulas...
A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem (2003)
Linusson, Svante, W"astlund, Johan
We prove the main conjecture of the paper ``On the expected value of the minimum assignment'' by Marshall W. Buck, Clara S. Chan, and David P. Robbins (Random Structures & Algorithms 21 (2002), no....
A Proof of Parisi's Conjecture on the Random Assignment Problem (2003)
Linusson, Svante, Waestlund, Johan
An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an...
Determining the Number of Solutions to Binary CSP instances (2003)
Ola Angelsmark, Peter Jonsson, Svante Linusson
Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of...
A Generalization of the Random Assignment Problem (2000)
Linusson, Svante, Waestlund, Johan
We give a conjecture for the expected value of the optimal k-assignment in an m x n-matrix, where the entries are all exp(1)-distributed random variables or zeros. We prove this conjecture in the...
A Smaller Sleeping Bag For A Baby Snake (2000)
Johan H Astad, Svante Linusson, W Astlund
. By a sleeping bag for a baby snake in d dimensions we mean a subset of R d which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller...
A Smaller Sleeping Bag For A Baby Snake (1998)
. By a sleeping bag for a baby snake in d dimensions we mean a subset of R d which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller...
The Number of K-Faces of a Simple D-Polytope (1998)
Anders Bj Orner, Svante Linusson
Consider the question: Given integers k ! d ! n, does there exist a simple d-polytope with n faces of dimension k? We show that there exist numbers G(d; k) and N(d; k) such that for n ? N(d; k) the...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes (1998)
Christos A. Athanasiadis, Svante Linusson
. The Shi arrangement Sn is the arrangement of affine hyperplanes in R n of the form x i Gamma x j = 0 or 1, for 1 i ! j n. It dissects R n into (n+1) nGamma1 regions, as was first proved by Shi. We...
Doubly alternating Baxter permutations are Catalan (1998)
Olivier Guibert, Svante Linusson
The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given. R'esum'e Nous...
Complexes Of Not i-Connected Graphs (1998)
Eric Babson, Anders Bj Orner, Svante Linusson
. Complexes of (not) connected graphs, hypergraphs and their homology appear in the construction of knot invariants given by V. Vassiliev [V1, V2, V4]. In this paper we study the complexes of not...
Doubly alternating Baxter permutations are Catalan (1998)
Olivier Guibert, Svante Linusson
The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given. R'esum'e Nous...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes (1998)
Christos A. Athanasiadis, Svante Linusson
. The Shi arrangement Sn is the arrangement of affine hyperplanes in R n of the form x i Gamma x j = 0 or 1, for 1 i ! j n. It dissects R n into (n+1) nGamma1 regions, as was first proved by Shi. We...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes (1998)
Christos A. Athanasiadis, Svante Linusson
. The Shi arrangement Sn is the arrangement of affine hyperplanes in R n of the form x i Gamma x j = 0 or 1, for 1 i ! j n. It dissects R n into (n+1) nGamma1 regions, as was first proved by Shi. We...
Doubly alternating Baxter permutations are Catalan (1998)
Olivier Guibert, Svante Linusson
The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given. R'esum'e Nous...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes (1998)
Christos A. Athanasiadis, Svante Linusson
. The Shi arrangement Sn is the arrangement of affine hyperplanes in R n of the form x i Gamma x j = 0 or 1, for 1 i ! j n. It dissects R n into (n+1) nGamma1 regions, as was first proved by Shi. We...
A Class of Lattices Whose Intervals are Spherical or Contractible (1997)
We study a class of lattices called weak* complemented lattices which are shown to have the property that the order complex of any interval of the lattice is either contractible or homotopy...
The Number of K-Faces of a Simple D-Polytope (1997)
Anders Bj Orner, Svante Linusson
Consider the question: Given integers k ! d ! n, does there exist a simple d-polytope with n faces of dimension k? We show that there exist numbers G(d; k) and N(d; k) such that for n ? N(d; k) the...
Doubly alternating Baxter permutations are Catalan (1997)
Olivier Guibert, Svante Linusson
The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers.
Möbius Functions and Characteristic Polynomials for Subspace Arrangements Embedded in ... (1997)
In [BS], Bjorner and Sagan define certain subspace arrangements embedded in the Coxeter hyperplane arrangements of type Bn and Dn . They give formulas for the exponential generating functions for the...
Partitions With Restricted Block Sizes, Möbius Functions And The k-Of-Each Problem. (1997)
Given a list of n real numbers, one wants to decide whether every number in the list occurs at least k times. It will be shown thatOmegaGamma n log n) is a sharp lower bound for the depth of an...
Complexes of not $i$-connected graphs (1997)
Babson, Eric, Björner, Anders, Linusson, Svante, Shareshian, John, Welker, Volkmar
Complexes of (not) connected graphs, hypergraphs and their homology appear in the construction of knot invariants given by V. Vassiliev. In this paper we study the complexes of not $i$-connected...
A Simple Bijection for the Regions of the Shi Arrangement of Hyperplanes (1997)
Athanasiadis, Christos A., Linusson, Svante
The Shi arrangement ${\mathcal S}_n$ is the arrangement of affine hyperplanes in ${\mathbb R}^n$ of the form $x_i - x_j = 0$ or $1$, for $1 \leq i < j \leq n$. It dissects ${\mathbb R}^n$ into...
The number of faces of a simple polytope (1996)
Björner, Anders, Linusson, Svante
Consider the question: Given integers $k
The size of Fulton's essential set (1995)
Kimmo Eriksson, Svante Linusson
The essential set of a permutation was defined by Fulton as the set of southeast corners of the diagram of the permutation. In this paper we determine explicit formulas for the average size of the...
The size of Fulton's essential set (1995)
Kimmo Eriksson, Svante Linusson
The essential set of a permutation was defined by Fulton as the set of southeast corners of the diagram of the permutation. In this paper we determine explicit formulas for the average size of the...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes (1970)
Christos A. Athanasiadis, Svante Linusson
. The Shi arrangement Sn is the arrangement of affine hyperplanes in R n of the form x i Gamma x j = 0 or 1, for 1 i ! j n. It dissects R n into (n+1) nGamma1 regions, as was first proved by Shi. We...
Anders Bj Orner, Svante Linusson
Consider the question: Given integers k ! d ! n, does there exist a simple d-polytope with n faces of dimension k? We show that there exist numbers G(d; k) and N(d;k) such that for n ? N(d;k) the...
Partitions With Restricted Block Sizes, Möbius Functions, And The k-Of-Each Problem (1970)
. Given a list of n real numbers, one wants to decide whether every number in the list occurs at least k times. It will be shown that## n log n) is a sharp lower bound for the depth of an algebraic...