Change search
Refine search result
1 - 21 of 21
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Hultman, Axel
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The topology of the space of matrices of Barvinok rank two2010In: Beiträge zur Algebra und Geometrie, ISSN 0138-4821, Vol. 51, no 2, 373-390 p.Article in journal (Refereed)
    Abstract [en]

    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.

  • 2.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    3-torsion in the Homology of Complexes of Graphs of Bounded Degree2013In: Canadian Journal of Mathematics - Journal Canadien de Mathematiques, ISSN 0008-414X, E-ISSN 1496-2479, Vol. 65, no 4, 843-862 p.Article in journal (Refereed)
    Abstract [en]

    For delta >= 1 and n >= 1, consider the simplicial complex of graphs on n vertices in which each vertex has degree at most delta; we identify a given graph with its edge set and admit one loop at each vertex. This complex is of some importance in the theory of semigroup algebras. When delta = 1, we obtain the matching complex, for which it is known that there is 3-torsion in degree d of the homology whenever (n - 4)/3 <= d <= (n - 6)/2. This paper establishes similar bounds for delta >= 2. Specifically, there is 3-torsion in degree d whenever (3 delta - 1)n - 8/6 <= d <= delta(n - 1) - 4/2. The procedure for detecting torsion is to construct an explicit cycle z that is easily seen to have the property that 3z is a boundary. Defining a homomorphism that sends z to a non-boundary element in the chain complex of a certain matching complex, we obtain that z itself is a non-boundary. In particular, the homology class of z has order 3.

  • 3.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Certain Homology Cycles of the Independence Complex of Grids2010In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 43, no 4, 927-950 p.Article in journal (Refereed)
    Abstract [en]

    Let G be an infinite graph such that the automorphism group of G contains a subgroup K congruent to Z(d) with the property that G/K is finite. We examine the homology of the independence complex Sigma(G/I) of G/I for subgroups I of K of full rank, focusing on the case that G is the square, triangular, or hexagonal grid. Specifically, we look for a certain kind of homology cycles that we refer to as "cross-cycles," the rationale for the terminology being that they are fundamental cycles of the boundary complex of some cross-polytope. For the special cases just mentioned, we determine the set Q(G, K) of rational numbers r such that there is a group I with the property that Sigma(G/I) contains cross-cycles of degree exactly r . |G/I| - 1; |G/I| denotes the size of the vertex set of G/I. In each of the three cases, Q( G, K) turns out to be an interval of the form [a, b] boolean AND Q = {r is an element of Q : a <= r <= b}. For example, for the square grid, we obtain the interval [1/5, 1/4] boolean AND Q.

  • 4.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Exact sequences for the homology of the matching complex2008In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 115, no 8, 1504-1526 p.Article in journal (Refereed)
    Abstract [en]

    Building on work by Bouc and by Shareshian and Wachs, we provide a toolbox of long exact sequences for the reduced simplicial homology of the matching complex M., which is the simplicial complex of matchings in the complete graph K-n. Combining these sequences in different ways, we prove several results about the 3-torsion part of the homology of M, First, we demonstrate that there is nonvanishing 3-torsion in (H) over bar (d)(M-n : Z) whenever v(n) <= d <= [n-6/2], where v(n) =[n-4/3]. By results due to Bouc and to Shareshian and Wachs, (H) over bar (d)(M-n : Z) is a nontrivial elementary 3-group for almost all n and the bottom nonvanishing homology group of M. for all n 0 2. Second, we prove that (H) over bar (d)(M-n : Z) is a nontrivial 3-group whenever v(n) <= d <= [2n-9/5]. Third, for each k >= 0, we show that there is a polynomial f(k)(r) of degree 3k such that the dimension of (H) over bar (k-1+r) (M2k+1+3r:Z(3)), viewed as a vector space over Z(3), is at most f(k)(r) for all r >= k + 2.

  • 5.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Five-torsion in the homology of the matching complex on 14 vertices2009In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 29, no 1, 81-90 p.Article in journal (Refereed)
    Abstract [en]

    J.L. Andersen proved that there is 5-torsion in the bottom nonvanishing homology group of the simplicial complex of graphs of degree at most two on seven vertices. We use this result to demonstrate that there is 5-torsion also in the bottom nonvanishing homology group of the matching complex M-14 on 14 vertices. Combining our observation with results due to Bouc and to Shareshian and Wachs, we conclude that the case n = 14 is exceptional; for all other n, the torsion subgroup of the bottom nonvanishing homology group has exponent three or is zero. The possibility remains that there is other torsion than 3-torsion in higher-degree homology groups of M-n when n = 13 and n not equal 14.

  • 6.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Generalized triangulations and diagonal-free subsets of stack polyrominoes2005In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 112, no 1, 117-142 p.Article in journal (Refereed)
    Abstract [en]

    For n >= 3, let Omega(n) be the set of line segments between vertices in a convex n-gon. For j >= 1, a j-crossing is a set of j distinct and mutually intersecting line segments from Q,, such that all 2j endpoints are distinct. For k >= 1, let Delta(n,k) be the simplicial complex of subsets of Omega(n) not containing any (k + 1)-crossing. For example, Delta(n.1) has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Delta(n,k) have the same number k(2n - 2k - 1) of line segments. We demonstrate that the number of such maximal sets is counted by a k x k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung, on determinantal ideals.

  • 7. Jonsson, Jakob
    Hard squares with negative activity and rhombus tilings of the plane2006In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 13, no 1Article in journal (Refereed)
    Abstract [en]

    Let S-m,S-n be the graph on the vertex set Z(m) x Z(n) in which there is an edge between (a, b) and (c, d) if and only if either (a, b) = (c, d +/- 1) or (a, b) (c +/- 1, d) modulo (m, n). We present a formula for the Euler characteristic of the simplicial complex Sigma(m,n) of independent sets in S-m,S-n. In particular, we show that the unreduced Euler characteristic of Sigma(m,n) vanishes whenever m and n are coprime, thereby settling a conjecture in statistical mechanics due to Fendley, Schoutens and van Eerten. For general m and n, we relate the Euler characteristic of Sigma(m,n) to certain periodic rhombus tilings of the plane. Using this correspondence, we settle another conjecture due to Fendley et al., which states that all roots of det(x(I) - T-m) are roots of unity, where T-m is a certain transfer matrix associated to {Sigma(m,n) : n >= 1}. In the language of statistical mechanics, the reduced Euler characteristic of Sigma(m,n) coincides with minus the partition function of the corresponding hard square model with activity -1.

  • 8.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Hard Squares with Negative Activity on Cylinders with Odd Circumference2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed)
    Abstract [en]

    Let C-m,C-n be the graph on the vertex set {1, ..., m} x {0, ..., n-1} in which there is an edge between (a, b) and (c, d) if and only if either (a, b) = (c, d +/- 1) or (a, b) = (c +/- 1, d), where the second index is computed modulo n. One may view C-m,C-n as a unit square grid on a cylinder with circumference n units. For odd n, we prove that the Euler characteristic of the simplicial complex Sigma(m,n) of independent sets in C-m,C-n is either 2 or -1, depending on whether or not gcd(m-1, n) is divisble by 3. The proof relies heavily on previous work due to Thapper, who reduced the problem of computing the Euler characteristic of Sigma(m,n) to that of analyzing a certain subfamily of sets with attractive properties. The situation for even n remains unclear. In the language of statistical mechanics, the reduced Euler characteristic of Sigma(m,n) coincides with minus the partition function of the corresponding hard square model with activity -1.

  • 9.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Hom complexes of set systems2013In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 20, no 1, P4- p.Article in journal (Refereed)
    Abstract [en]

    A set system is a pair S = (V (S), Delta(S)), where Delta(S) is a family of subsets of the set V(S). We refer to the members of Delta(S) as the stable sets of S. A homomorphism between two set systems S and T is a map f : V (S) -> V(T) such that the preimage under f of every stable set of T is a stable set of S. Inspired by a recent generalization due to Engstrom of Lovasz's Hom complex construction, the author associates a cell complex Hom(S, T) to any two finite set systems S and T. The main goal of the paper is to examine basic topological and homological properties of this cell complex for various pairs of set systems.

  • 10.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    More Torsion in the Homology of the Matching Complex2010In: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 19, no 3, 363-383 p.Article in journal (Refereed)
    Abstract [en]

    A matching on a set X is a collection of pairwise disjoint subsets of X of size two Using computers, we analyze the integral homology of the matching complex M, which is the simplicial complex of matchings on the set {1, ,n} The main result is the detection of elements of order p in the homology for p is an element of {5, 7, 11, 13} Specifically, we show that there are elements of order 5 in the homology of M-n for n >= 18 and for n is an element of {14, 16} The only previously known value was n = 14, and in this particular case we have a new computer-free proof Moreover, we show that there are elements of order 7 in the homology of M-n for all odd a between 23 and 41 and for n = 30 In addition, there are elements of order 11 in the homology of M-47 and elements of order 13 in the homology of M-62 Finally, we compute the ranks of the Sylow 3- and 5-subgroups of the torsion part of (H) over tilde (d)(M-n, Z) for 13 <= n <= 16, a complete description of the homology already exists for n <= 12 To prove the results, we use a representation-theoretic approach, examining subcomplexes of the chain complex of M-n obtained by letting certain groups act on the chain complex.

  • 11.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    On the 3-Torsion Part of the Homology of the Chessboard Complex2010In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 14, no 4, 487-505 p.Article in journal (Refereed)
    Abstract [en]

    Let 1 (d) (M-m,M-n; Z) not equal 0. Second, for each k >= 0, we show that there is a polynomial f(k)(a, b) of degree 3k such that the dimension of (H) over tilde (k+a+2b-2) (M-k+a+3b-1,M- k+2a+3b-1; Z(3)), viewed as a vector space over Z(3), is at most f(k)(a, b) for all a >= 0 and b >= k+ 2. Third, we give a computer- free proof that (H) over tilde (2) (M-5,M-5; Z) congruent to Z(3). Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M-m,M-n to the homology of M-m-2,M-n-1 and M-m-2,M-n-3.

  • 12. Jonsson, Jakob
    On the number of Euler trails in directed graphs2002In: Mathematica Scandinavica, ISSN 0025-5521, E-ISSN 1903-1807, Vol. 90, no 2, 191-214 p.Article in journal (Refereed)
    Abstract [en]

    Let G be an Eulerian digraph with all in- and out-degrees equal to 2, and let pi be an Euler trail in G. We consider an intersection matrix L(pi) with the property that the determinant of L(pi) + I is equal to the number of Euler trails in G; I denotes the identity matrix. We show that if the inverse of L(pi) exists, then L-1 (pi) = L(sigma) for a certain Euler trail sigma in G. Furthermore, we use properties of the intersection matrix to prove some results about how to divide the set of Euler trails in a digraph into smaller sets of the same size.

  • 13. Jonsson, Jakob
    On the topology of simplicial complexes related to 3-connected and Hamiltonian graphs2003In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 104, no 1, 169-199 p.Article in journal (Refereed)
    Abstract [en]

    Using techniques from Robin Forman's discrete Morse theory, we obtain information about the homology and homotopy type of some graph complexes. Specifically, we prove that the simplicial complex Delta(n)(3) of not 3-connected graphs on it vertices is homotopy equivalent to a wedge of (n - 3) (.) (n - 2)!/2 spheres of dimension 2n - 4, thereby verifying a conjecture by Babson, Bjorner, Linusson, Shareshian, and Welker. We also determine a basis for the corresponding nonzero homology group in the CW complex of 3-connected graphs. In addition, we show that the complex Gamma(n) of non-Hamiltonian graphs on it vertices is homotopy equivalent to a wedge of two complexes, one of the complexes being the complex Delta(n)(2) of not 2-connected graphs on it vertices. The homotopy type of Delta(n)(2) has been determined, independently, by the five authors listed above and by Turchin. While Gamma(n) and Delta(n)(2) are homotopy equivalent for small values on it, they are nonequivalent for n = 10.

  • 14.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Optimal decision trees on simplicial complexes2005In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 12, no 1Article in journal (Refereed)
    Abstract [en]

    We consider topological aspects of decision trees on simplicial complexes, concentrating on how to use decision trees as a tool in topological combinatorics. By Robin Forman's discrete Morse theory, the number of evasive faces of a given dimension i with respect to a decision tree on a simplicial complex is greater than or equal to the ith reduced Betti number (over any field) of the complex. Under certain favorable circumstances, a simplicial complex admits an optimal decision tree such that equality holds for each i; we may hence read off the homology directly from the tree. We provide a recursive definition of the class of semi-nonevasive simplicial complexes with this property. A certain generalization turns out to yield the class of semi-collapsible simplicial complexes that admit an optimal discrete Morse function in the analogous sense. In addition, we develop some elementary theory about semi-nonevasive and semi-collapsible complexes. Finally, we provide explicit optimal decision trees for several well-known simplicial complexes.

  • 15.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Simplicial complexes of graphs2008In: Lecture Notes in Mathematics: Volume 1928, Springer Berlin/Heidelberg, 2008, 1-394 p.Chapter in book (Refereed)
    Abstract [en]

    Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this book is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic. We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this book are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices. Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity. The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs. Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this book provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees, which we successfully apply to a large number of graph and digraph complexes.

  • 16.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Simplicial Complexes of Graphs2005Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this thesis is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic.

    We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this thesis are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices.

    Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity.

    The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs.

    Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this thesis provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees, which we successfully apply to a large number of graph and digraph complexes.

  • 17.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Simplicial complexes of graphs and hypergraphs with a bounded covering number2005In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 19, no 3, 633-650 p.Article in journal (Refereed)
    Abstract [en]

    For 1 <= p <= n- 1, define Cov(n,p) as the family of graphs on the vertex set {1,..., n} with a covering number of at most p ( equivalently, with an independence number of at least n = p). Since the underlying vertex set is fixed, we may identify each graph in Cov(n,p) with its edge set. In particular, we may view Cov(n,p) as a simplicial complex. For i >= - 1, we show that the rank of the ith homology group of Cov(n,p) is a linear combination, with coefficients being polynomials in n, of the ranks of the ith homology groups of Cov(p+2, p),..., Cov(2p+1,p). Our proof takes place in a more general setting where we consider complexes of hypergraphs. In addition, we show that the (2p - 1)- skeleton of Cov(n,p) is shellable, which implies that Cov(n,p) is (2p - 2)-connected. For p <= 3, we give a complete description of the homology groups of Cov(n,p).

  • 18.
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The topology of the coloring complex2005In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 21, no 3, 311-329 p.Article in journal (Refereed)
    Abstract [en]

    In a recent paper, E. Steingrimsson associated to each simple graph G a simplicial complex G., referred to as the coloring complex of G. Certain nonfaces of &UDelta;(G) correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial χ(G) of G, and the reduced Euler characteristic is, up to sign, equal to &VERBAR;χ(G)(-1)&VERBAR; -1. We show that &UDelta;(G) is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of χ(G), and their Euler characteristics coincide with χ'(G)(0) and -χ'(G)(1), respectively. We show for a large class of graphs - including all connected graphs - that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.

  • 19.
    Jonsson, Jakob
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Robshaw, M.J.B.
    Securing RSA-KEM via the AES2005In: PUBLIC KEY CRYPTOGRAPHY - PKC 2005 / [ed] Vaudenay, S, 2005, Vol. 3386, 29-46 p.Conference paper (Refereed)
    Abstract [en]

    RSA-KEM is a popular key encapsulation mechanism that combines the RSA trapdoor permutation with a key derivation function (KDF). Often the details of the KDF are viewed as orthogonal to the RSA-KEM construction and the RSA-KEM proof of security models the KDF as a random oracle. In this paper we present an AES-based KDF that has been explicitly designed so that we can appeal to currently held views on the ideal behaviour of the AES when proving the security of RSA-KEM. Thus, assuming that encryption with the AES provides a permutation of 128-bit input blocks that is chosen uniformily at random for each key k, the security of RSA-KEM against chosen-ciphertext attacks can be related to, the hardness of inverting RSA.

  • 20.
    Jonsson, Jakob
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Welker, Volkmar
    A spherical initial ideal for Pfaffians2007In: Illinois Journal of Mathematics, ISSN 0019-2082, E-ISSN 1945-6581, Vol. 51, no 4, 1397-1407 p.Article in journal (Refereed)
    Abstract [en]

    We determine a term order on the monomials in the variables X-ij, 1 <= i <= j <= n, such that corresponding initial ideal of the ideal of Pfaffians of degree r of a generic n by n skew-symmetric matrix is the Stanley-Reisner ideal of a join of a simplicial sphere and a simplex. Moreover, we demonstrate that the Pfaffians of the 2r by 2r skew-symmetric submatrices form a, Grobner basis for the given term order. The same methods and similar term orders as for the Pfaffians also yield squarefree initial ideals for certain determinantal ideals. Yet, in contrast to the case of Pfaffians, the corresponding simplicial complexes are balls that do not decompose into a join as above.

  • 21.
    Jonsson, Jakob
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Welker, Volkmar
    COMPLEXES OF INJECTIVE WORDS AND THEIR COMMUTATION CLASSES2009In: Pacific Journal of Mathematics, ISSN 0030-8730, E-ISSN 1945-5844, Vol. 243, no 2, 313-329 p.Article in journal (Refereed)
    Abstract [en]

    Let S be a finite alphabet. An injective word over S is a word over S such that each letter in S appears at most once in the word. For an abstract simplicial complex Delta, let Gamma(Delta) be the Boolean cell complex whose cells are indexed by all injective words over the sets forming the faces of Delta. The boundary of a cell indexed by a given word w consists of those cells that are indexed by subwords of w. For a partial order P on S, we study the subcomplex Gamma(Delta, P) of Gamma(Delta) consisting of those cells that are indexed by words whose letters are arranged in increasing order with respect to some linear extension of the order P. For a graph G = (S, E) on vertex set S and a word w over S, let [w] be the class of all words that we can obtain from w via a sequence of commutations ss' -> s's s such that {s, s'} g is not an edge in E. We study the Boolean cell complex Gamma/G(Delta) whose cells are indexed by commutation classes [w] of words indexing cells in Gamma(Delta). We prove: If Delta is shellable then so are Gamma(Delta, P) and Gamma/G(Delta). If Delta is Cohen-Macaulay (respectively sequentially Cohen-Macaulay) then so are Gamma(Delta, P) and Gamma/G(Delta). The complex Gamma(Delta) is partitionable. Our work generalizes work by Farmer and by Bjorner and Wachs on the complex of all injective words.

1 - 21 of 21
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf