Correlations for paths in random orientations of G(n,p) (2009)
Alm, Sven Erick, Linusson, Svante
We study the random graph G(n,p) with a random orientation. For three fixed vertices s,a,b in G(n,p) we study the correlation of the events {a\to s} and {s\to b}. We prove that for a fixed p1/2 the...
A counter-intuitive correlation in a random tournament (2009)
Alm, Sven Erick, Linusson, Svante
Consider a randomly oriented graph $G=(V,E)$ and let $a$, $s$ and $b$ be three distinct vertices in $V$. We study the correlation between the events $\{a\to s\}$ and $\{s\to b\}$. We show that, when...
A note on correlations in randomly oriented graphs (2009)
Given a graph $G$, we consider the model where $G$ is given a random orientation by giving each edge a random direction. It is proven that for $a,b,s\in V(G)$, the events $\{s\to a\}$ and $\{s\to...
The k-assignment polytope (2009)
Gill, Jonna, Linusson , Svante
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...
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...
A stratification of Fl(n)^d indexed by permutation arrays (2008)
Kimmo Eriksson, Svante Linusson
this paper. Combinatorially, we define a class of hyper-cubic (shape n
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....
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....
A regular decomposition of the edge-product space of phylogenetic trees (2008)
Gill, Jonna, Linusson, Svante, Moulton, Vincent, Steel, Mike
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...
Johan H Astad, Svante Linusson, W Astlund
Abstract. By a sleeping bag for a baby snake in d dimensions we mean a
Extended Pattern Avoidance (2007)
A 0-1 matrix is said to be extendably ø-avoiding if it can be the upper left corner of a ø-avoiding permutation matrix. This concept arose in [EL], where the surprising result that the number of...
Doubly alternating Baxter permutations are Catalan (2007)
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....
A Decomposition Of ... Indexed By Permutation Arrays (2007)
Kimmo Eriksson, Svante Linusson
. We study a decomposition of F`(n) d\Gamma1 , where F`(n) denotes the flag manifold over C n . The strata are defined by the dimensions of intersections of one space from each flag, so for d equals...
Faces Of Simple, 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 (2007)
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....
A Smaller Sleeping Bag For A Baby Snake (2007)
Svante Linusson, Johan Wästlund, 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...
Extended Pattern Avoidance (2007)
A 0-1 matrix is said to be extendably ø-avoiding if it can be the upper left corner of a ø-avoiding permutation matrix. This concept arose in [EL], where the surprising result that the number of...
The number of k-faces of a simple d-polytope Anders Bj orner (2007)
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...
Kimmo Eriksson, Svante Linusson
of several flags and a generalization of permutation matrices to higher dimensions
Doubly alternating Baxter permutations are Catalan (2007)
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....
PARTITIONS WITH RESTRICTED BLOCK SIZES, M OBIUS FUNCTIONS AND THE k-OF-EACH PROBLEM. (2007)
Abstract. 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\Omega\Gamma n log n) is a sharp lower bound for the depth...
M OBIUS FUNCTIONS AND CHARACTERISTIC POLYNOMIALS FOR SUBSPACE ARRANGEMENTS EMBEDDED IN B n (2007)
Abstract. 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...
Determining the Number of Solutions to Binary CSP instances (2007)
Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper
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...
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....
Pattern Avoidance in Alternating Sign Matrices (2006)
Robert Johansson, Svante Linusson
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 Schröder...
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...
Completing a (k − 1)-Assignment (2004)
Svante Linusson, Johan W Ästlund
We consider the distribution of the value of the optimal k-assignment in an m × 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...
A PROOF OF A CONJECTURE OF BUCK, CHAN AND ROBBINS ON THE RANDOM ASSIGNMENT PROBLEM (2003)
Svante Linusson, W Ästlund, Clara S. Chan, Svante Linusson, ...
Abstract. We prove the main conjecture of the paper “On the expected value of the minimum assignment ” by Marshall W. Buck,
Probab. Theory Relat. Fields (2003) Digital Object Identifier (DOI) 10.1007/s00440-003-0308-9 (2003)
Svante Linusson, Johan Wästlund
A proof of Parisi’s conjecture on the random assignment problem
Dense packing of patterns in a permutation (2002)
Henrik Eriksson, Kimmo Eriksson, Svante Linusson, W Ästlund
Abstract. We study the length Lk of the shortest permutation containing all patterns of length k. We establish the bounds e −2 k 2 < Lk ≤ (2/3 + o(1))k 2. We also prove that as k → ∞,...
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 class of lattices whose intervals are spherical or contractible, preprint (1999)
Abstract. 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...
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...
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 that## n log n) is a sharp lower bound for the depth of an algebraic...
The Number of K-Faces of a Simple D-Polytope (1997)
Anders Björner, 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 (1997)
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) n\Gamma1 regions, as was first proved by Shi....
The number of faces of a simple polytope (1996)
Björner, Anders, Linusson, Svante
Consider the question: Given integers $k
Combinatorics of Fulton's essential set (1996)
Kimmo Eriksson, Svante Linusson
Abstract. Fulton introduced the essential set of a permutation, together with a rank function. In this paper we study some combinatorial aspects of the essential set: We present an algorithm that...
Combinatorics of Fulton's essential set (1996)
Kimmo Eriksson, Svante Linusson
Abstract. Fulton introduced the essential set of a permutation, together with a rank function. In this paper we study some combinatorial aspects of the essential set: We present an algorithm that...
Complexes Of Not i-Connected Graphs (1996)
Eric Babson, Anders Björner, Svante Linusson, John Shareshian, Volkmar Welker
. 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...
The size of Fulton's essential set (1995)
Kimmo Eriksson And, 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...
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 number of M-sequences and f-vectors (1987)
Abstract. We give a recursive formula for the number of M-sequences (a.k.a. f-vectors for multicomplexes or O-sequences) given the number of variables and a maximum degree. In particular, it is shown...
The Number Of M-Sequences And f-Vectors (1987)
. We give a recursive formula for the number of M-sequences (a.k.a. f-vectors for multicomplexes or O-sequences) given the number of variables and a maximum degree. In particular, it is shown that...
The number of M-sequences and f-vectors (1987)
Abstract. We give arecursive formula for the number of M-sequences (a.k.a. f-vectors for multicomplexes or O-sequences) given the number of variables and a maximum degree. In particular, it is shown...
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes
Christos 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) n\Gamma1 regions, as was first proved by Shi....
A Simple Bijection For The Regions Of The Shi Arrangement Of Hyperplanes
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) n\Gamma1 regions, as was first proved by Shi....