Change search
Refine search result
12 1 - 50 of 67
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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)
  • Disputation date (earliest first)
  • Disputation date (latest 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)
  • Disputation date (earliest first)
  • Disputation date (latest 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.
    Alexandersson, Per
    Stockholm University, Faculty of Science, Department of Mathematics.
    Schur polynomials, banded Toeplitz matrices and Widom's formula2012In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 4, p. P22-Article in journal (Refereed)
    Abstract [en]

    We prove that for arbitrary partitions lambda subset of kappa, and integers 0 <= c < r <= n, the sequence of Schur polynomials S(kappa+k.1c)/(lambda+k.1r)(x(1), ... , x(n)) for k sufficiently large, satisfy a linear recurrence. The roots of the characteristic equation are given explicitly. These recurrences are also valid for certain sequences of minors of banded Toeplitz matrices. In addition, we show that Widom's determinant formula from 1958 is a special case of a well-known identity for Schur polynomials.

  • 2.
    Alexandersson, Per
    et al.
    Stockholm Univ, Dept Math, Stockholm, Sweden..
    Linusson, Svante
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Potka, Samu
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The cyclic sieving phenomenon on circular Dyck paths2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.16Article in journal (Refereed)
    Abstract [en]

    We give a q-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this q-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Mobius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving, and introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.

  • 3.
    Alexandersson, Per
    et al.
    Stockholm University, Faculty of Science, Department of Mathematics.
    Linusson, Svante
    Potka, Samu
    The cyclic sieving phenomenon on circular Dyck paths2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.16Article in journal (Refereed)
    Abstract [en]

    We give a q-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this q-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Mobius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving, and introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.

  • 4.
    Alexandersson, Per
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Sawhney, Mehtaab
    A Major-Index Preserving Map on Fillings2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 4, article id P4.3Article in journal (Refereed)
    Abstract [en]

    We generalize a map by S. Mason regarding two combinatorial models for key polynomials, in a way that accounts for the major index. Furthermore we define a similar variant of this map, that regards alternative models for the modified Macdonald polynomials at t = 0, and thus partially answers a question by J. Haglund. These maps together imply a certain uniqueness property regarding inversion- and coinversion-free fillings. These uniqueness properties allow us to generalize the notion of charge to a non-symmetric setting, thus answering a question by A. Lascoux and the analogous question in the symmetric setting proves a conjecture by K. Nelson.

  • 5.
    Amini, Nima
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Equidistributions of mahonian statistics over pattern avoiding permutations2018In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 1, article id P1.7Article in journal (Refereed)
    Abstract [en]

    A Mahonian d-function is a Mahonian statistic that can be expressed as a linear combination of vincular pattern functions of length at most d. Babson and Ste- ingrímsson classified all Mahonian 3-functions up to trivial bijections and identified many of them with well-known Mahonian statistics in the literature. We prove a host of Mahonian 3-function equidistributions over permutations in Sn avoiding a single classical pattern in S3. Tools used include block decomposition, Dyck paths and generating functions.

  • 6.
    Andrén, Lina J
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Avoiding (m, m, m)-arrays of order n=2(k)2012In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 1, p. P63-Article in journal (Refereed)
    Abstract [en]

    An (m, m, m)-array of order n is an n x n array such that each cell is assigned a set of at most m symbols from f 1,...,n g such that no symbol occurs more than m times in any row or column. An (m, m, m)-array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant gamma such that if m <= gamma 2(k) and k >= 14, then any (m, m, m)-array of order n = 2(k) is avoidable. Such a constant gamma has been conjectured to exist for all n by Haggkvist.

  • 7. Beer, Elizabeth
    et al.
    Fill, James Allen
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Scheinerman, Edward R.
    On Vertex, Edge, and Vertex-Edge Random Graphs2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, p. P110-Article in journal (Refereed)
    Abstract [en]

    We consider three classes of random graphs: edge random graphs, vertex random graphs, and vertex-edge random graphs. Edge random graphs are Erdos-Renyi random graphs, vertex random graphs are generalizations of geometric random graphs, and vertex-edge random graphs generalize both. The names of these three types of random graphs describe where the randomness in the models lies: in the edges, in the vertices, or in both. We show that vertex-edge random graphs, ostensibly the most general of the three models, can be approximated arbitrarily closely by vertex random graphs, but that the two categories are distinct.

  • 8.
    Berglund, Alexander
    Stockholm University, Faculty of Science, Department of Mathematics.
    Shellability and the strong gcd-condition2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed)
    Abstract [en]

    Shellability is a well-known combinatorial criterion on a simplicial complex for verifying that the associated Stanley-Reisner ring k[] is Cohen-Macaulay. Anotion familiar to commutative algebraists, but which has not received as muchattention from combinatorialists as the Cohen-Macaulay property, is the notion ofa Golod ring. Recently, J¨ollenbeck introduced a criterion on simplicial complexesreminiscent of shellability, called the strong gcd-condition, and he together with theauthor proved that it implies Golodness of the associated Stanley-Reisner ring. Thetwo algebraic notions were earlier tied together by Herzog, Reiner and Welker, whoshowed that if k[∨] is sequentially Cohen-Macaulay, where ∨ is the Alexanderdual of , then k[] is Golod. In this paper, we present a combinatorial companionof this result, namely that if ∨ is (non-pure) shellable then satisfies the stronggcd-condition. Moreover, we show that all implications just mentioned are strict ingeneral but that they are equivalences if is a flag complex.

  • 9.
    Berglund, Alexander
    Stockholm University, Faculty of Science, Department of Mathematics.
    Shellability and the strong gcd-condition2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed)
    Abstract [en]

    Shellability is a well-known combinatorial criterion on a simplicial complex for verifying that the associated Stanley-Reisner ring k[] is Cohen-Macaulay. Anotion familiar to commutative algebraists, but which has not received as muchattention from combinatorialists as the Cohen-Macaulay property, is the notion ofa Golod ring. Recently, J¨ollenbeck introduced a criterion on simplicial complexesreminiscent of shellability, called the strong gcd-condition, and he together with theauthor proved that it implies Golodness of the associated Stanley-Reisner ring. Thetwo algebraic notions were earlier tied together by Herzog, Reiner and Welker, whoshowed that if k[∨] is sequentially Cohen-Macaulay, where ∨ is the Alexanderdual of , then k[] is Golod. In this paper, we present a combinatorial companionof this result, namely that if ∨ is (non-pure) shellable then satisfies the stronggcd-condition. Moreover, we show that all implications just mentioned are strict ingeneral but that they are equivalences if is a flag complex.

  • 10.
    Berglund, Alexander
    Stockholm University, Faculty of Science, Department of Mathematics.
    Shellability and the strong gcd-condition2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2, p. R1-Article in journal (Refereed)
    Abstract [en]

    Shellability is a well-known combinatorial criterion on a simplicial complex Delta for verifying that the associated Stanley-Reisner ring k[Delta] is Cohen-Macaulay. A notion familiar to commutative algebraists, but which has not received as much attention from combinatorialists as the Cohen-Macaulay property, is the notion of a Golod ring. Recently, Jollenbeck introduced a criterion on simplicial complexes reminiscent of shellability, called the strong gcd-condition, and he together with the author proved that it implies Golodness of the associated Stanley-Reisner ring. The two algebraic notions were earlier tied together by Herzog, Reiner and Welker, who showed that if k[Delta(V)] is sequentially Cohen-Macaulay, where Delta(V) is the Alexander dual of Delta, then k[Delta] is Golod. In this paper, we present a combinatorial companion of this result, namely that if Delta(V) is ( non-pure) shellable then Delta satisfies the strong gcd-condition. Moreover, we show that all implications just mentioned are strict in general but that they are equivalences if Delta is a flag complex.

  • 11.
    Björner, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Farley, J. D.
    Chain polynomials of distributive lattices are 75% unimodal2005In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 12, no 1Article in journal (Refereed)
    Abstract [en]

    It is shown that the numbers c(i) of chains of length i in the proper part L\{0, 1} of a distributive lattice L of length l + 2 satisfy the inequalities c(0) <...< c([l/2]) and c([3l.4]) >... > c(l). This proves 75% of the inequalities implied by the Neggers unimodality conjecture.

  • 12.
    Björner, Anders.
    et al.
    KTH, Superseded Departments, Mathematics.
    Wachs, M. L.
    Geometrically constructed bases for homology of partition lattices of types A, B and D2004In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 11, no 2Article in journal (Refereed)
    Abstract [en]

    We use the theory of hyperplane arrangements to construct natural bases for the homology of partition lattices of types A, B and D. This extends and explains the splitting basis for the homology of the partition lattice given in [20], thus answering a question asked by R. Stanley. More explicitly, the following general technique is presented and utilized. Let A be a central and essential hyperplane arrangement in R-d. Let R-1,..., R-k be the bounded regions of a generic hyperplane section of A. We show that there are induced polytopal cycles rho(Ri) in the homology of the proper part LA of the intersection lattice such that {rho(Ri)}(i=1,...,k) is a basis for (H) over tilde (d-2)((L) over bar (A)). This geometric method for constructing combinatorial homology bases is applied to the Coxeter arrangements of types A, B and D, and to some interpolating arrangements.

  • 13. Brignall, Robert
    et al.
    Sliacan, Jakub
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Combinatorial specifications for juxtapositions of permutation classes2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 4, article id P4.4Article in journal (Refereed)
    Abstract [en]

    We show that, given a suitable combinatorial specification for a permutation class C, one can obtain a specification for the juxtaposition (on either side) of C with Av(21) or Av(12), and that if the enumeration for C is given by a rational or algebraic generating function, so is the enumeration for the juxtaposition. Furthermore this process can be iterated, thereby providing an effective method to enumerate any 'skinny' k x 1 grid class in which at most one cell is non-monotone, with a guarantee on the nature of the enumeration given the nature of the enumeration of the non-monotone cell.

  • 14. Bränden, Petter
    Sign-graded posets, unimodality of W-polynomials and the Charney-Davis conjecture2004In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 11, no 2Article in journal (Refereed)
    Abstract [en]

    We generalize the notion of graded posets to what we call sign-graded (labeled) posets. We prove that the W-polynomial of a sign-graded poset is symmetric and unimodal. This extends a recent result of Reiner and Welker who proved it for graded posets by associating a simplicial polytopal sphere to each graded poset. By proving that the W-polynomials of sign-graded posets has the right sign at -1, we are able to prove the Charney-Davis Conjecture for these spheres (whenever they are flag).

  • 15.
    Brändén, Petter
    et al.
    Department of Mathematics, Stockholm University.
    Claesson, A.
    Mesh patterns and the expansion of permutation statistics as sums of permutation patterns2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, ISSN 1077-8926, Vol. 18, no 2, p. Paper 5-14Article in journal (Refereed)
    Abstract [en]

    Any permutation statistic f : G -> C may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: f = Sigma(tau)lambda(f)(tau)tau . To provide explicit expansions for certain statistics, we introduce a new type of permutation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern p = (pi, R) is an occurrence of the permutation pattern pi with additional restrictions specified by R on the relative position of the entries of the occurrence. We show that, for any mesh pattern p = (pi, R), wehave lambda(p)(tau) = (-1)(vertical bar tau vertical bar-vertical bar pi vertical bar)p*(tau) where p* = (pi, R(c)) is the mesh pattern with the same underlying permutation as p but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, Andre permutations of the first kind and simsun permutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.

  • 16.
    Brändén, Petter
    et al.
    Stockholm University, Faculty of Science, Department of Mathematics.
    Claesson, Anders
    Mesh patterns and the expansion of permutation statistics as sums of permutation patterns2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 2, p. P5-Article in journal (Refereed)
    Abstract [en]

    Any permutation statistic f : G -> C may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: f = Sigma(tau)lambda(f)(tau)tau . To provide explicit expansions for certain statistics, we introduce a new type of permutation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern p = (pi, R) is an occurrence of the permutation pattern pi with additional restrictions specified by R on the relative position of the entries of the occurrence. We show that, for any mesh pattern p = (pi, R), wehave lambda(p)(tau) = (-1)(vertical bar tau vertical bar-vertical bar pi vertical bar)p*(tau) where p* = (pi, R(c)) is the mesh pattern with the same underlying permutation as p but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, Andre permutations of the first kind and simsun permutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.

  • 17.
    Cai, Xing Shi
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Non-fringe subtrees in conditioned Galton-Watson trees2018In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 3, article id P3.40Article in journal (Refereed)
    Abstract [en]

    We study S(T-n), the number of subtrees in a conditioned Galton-Watson tree of size n. With two very different methods, we show that log(S(T-n)) has a Central Limit Law and that the moments of S(T-n) are of exponential scale.

  • 18.
    Casselgren, Carl Johan
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A note on path factors of (3,4)-biregular bipartite graphs2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, p. P218-Article in journal (Refereed)
    Abstract [en]

    A proper edge coloring of a graph G with colors 1,2,3, ... is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graphis (3,4)-biregular if all vertices in one part have degree 3 and all vertices in the other part have degree 4. Recently it was proved [J. Graph Theory 61 (2009), 88-97] that if such a graph G has a spanning subgraph whose components are paths with end points at 3-valent vertices and lengths in {2,4,6,8}, then G has an interval coloring. It was also conjectured that every simple (3,4)-biregular bipartite graph has such a subgraph. We provide some evidence for this conjecture by proving that a simple (3,4)-biregular bipartite graph has a spanning subgraph whose components are nontrivial paths with endpoints at 3-valent vertices and lengths not exceeding 22.

  • 19.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Markstrom, Klas
    Umea Univ, Sweden.
    Pham, Lan Anh
    Umea Univ, Sweden.
    Latin cubes with forbidden entries2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed)
    Abstract [en]

    We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant gamma amp;gt; 0 such that if n = 2(t) and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma n times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 amp;lt;= i, j, k amp;lt;= n, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A.

  • 20. Casselgren, Carl Johan
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Pham, Lan Anh
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin cubes with forbidden entries2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed)
    Abstract [en]

    We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant y>0 such that if n=2k and A is a 3-dimensional n×n×n array where every cell contains at most γn symbols, and every symbol occurs at most γn times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 ≤ i,j,k ≤ n, the symbol in position (i,j,k) of L does not appear in the corresponding cell of A. 

  • 21. Chow, T Y
    et al.
    Eriksson, Henrik
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Fan, C K
    Chess tableaux2005In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 11, no 2, p. A3-Article in journal (Refereed)
    Abstract [en]

    A chess tableau is a standard Young tableau in which, for all i and j, the parity of the entry in cell ( i; j) equals the parity of i + j + 1. Chess tableaux were first defined by Jonas Sjostrand in his study of the sign-imbalance of certain posets, and were independently rediscovered by the authors less than a year later in the completely different context of composing chess problems with interesting enumerative properties. We prove that the number of 3 x n chess tableaux equals the number of Baxter permutations of n - 1, as a corollary of a more general correspondence between certain three-rowed chess tableaux and certain three-rowed Dulucq-Guibert nonconsecutive tableaux. The correspondence itself is proved by means of an explicit bijection. We also outline how lattice paths, or rat races, can be used to obtain generating functions for chess tableaux. We conclude by explaining the connection to chess problems, and raising some unanswered questions, e. g., there are striking numerical coincidences between chess tableaux and the Charney-Davis statistic; is there a combinatorial explanation?

  • 22. Christofides, Demetres
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The guessing number of undirected graph2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, p. P192-Article in journal (Refereed)
    Abstract [en]

    Riis [Electron. J. Combin., 14(1):R44, 2007] introduced a guessing game for graphs which is equivalent to finding protocols for network coding. In this paper we prove upper and lower bounds for the winning probability of the guessing game on undirected graphs. We find optimal bounds for perfect graphs and minimally imperfect graphs, and present a conjecture relating the exact value for all graphs to the fractional chromatic number.

  • 23. Cutler, Jonathan
    et al.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Latin squares with forbidden entries2006In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 13, no 1, p. R47-Article in journal (Refereed)
  • 24.
    Ekedahl, Torsten
    Stockholm University, Faculty of Science, Department of Mathematics.
    Shellability of a Poset of Polygonal Subdivisions2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2, p. R23-Article in journal (Refereed)
  • 25.
    Engström, Alexander
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Dochtermann, Anton
    Techn. Universität , Berlin.
    Algebraic properties of edge ideals via combinatorial topology2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed)
    Abstract [en]

    We apply some basic notions from combinatorial topology to establish various algebraic properties of edge ideals of graphs and more general Stanley-Reisner rings. In this way we provide new short proofs of some theorems from the literature regarding linearity, Betti numbers, and (sequentially) Cohen-Macaulay properties of edge ideals associated to chordal, complements of chordal, and Ferrers graphs, as well as trees and forests. Our approach unifies (and in many cases strengthens) these results and also provides combinatorial/enumerative interpretations of certain algebraic properties. We apply our setup to obtain new results regarding algebraic properties of edge ideals in the context of local changes to a graph (adding whiskers and ears) as well as bounded vertex degree. These methods also lead to recursive relations among certain generating functions of Betti numbers which we use to establish new formulas for the projective dimension of edge ideals. We use only well-known tools from combinatorial topology along the lines of independence complexes of graphs, (not necessarily pure) vertex decomposability, shellability, etc.

  • 26.
    Eriksen, Niklas
    et al.
    Department of Mathematics, KTH, Stockholm.
    Eriksson, Henrik
    NADA, KTH, Stockholm.
    Eriksson, Kimmo
    IMa, Mälardalens högskola, Västerås.
    Diagonal checker-jumping and Eulerian numbers for color-signed permutations2000In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 7, article id R3Article in journal (Refereed)
    Abstract [en]

    We introduce color-signed permutations to obtain a very explicit combinatorial interpretation of the q-Eulerian identities of Brenti and some generalizations. In particular, we prove an identity involving the golden ratio, which allows us to compute upper bounds on how high a checker can reach in a classical checker-jumping problem, when the rules are relaxed to allow also diagonal jumps.

  • 27.
    Eriksen, Niklas
    et al.
    Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden.
    Freij, Ragnar
    Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden.
    Wästlund, Johan
    Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden.
    Enumeration of Derangements with Descents in Prescribed Positions2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 1, article id R32Article in journal (Refereed)
    Abstract [en]

    We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point lambda-coloured permutations, which are easily enumerated. Several formulae regarding these numbers are given, aswell as a generalisation of Euler's difference tables. We also prove that except in a trivial special case, if a permutation pi is chosen uniformly among all permutations on n elements, the events that pi has descents in a set S of positions, and that \p$ is a derangement, are positively correlated.

  • 28. Eriksen, Niklas
    et al.
    Sjöstrand, Jonas
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Equidistributed Statistics on Matchings and Permutations2014In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, no 4, article id P4.43Article in journal (Refereed)
    Abstract [en]

    We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.

  • 29.
    Eriksen, Niklas
    et al.
    Örebro University, School of Science and Technology.
    Sjöstrand, Jonas
    Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden.
    Equidistributed Statistics on Matchings and Permutations2014In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, no 4, article id P4.43Article in journal (Refereed)
    Abstract [en]

    We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.

  • 30.
    Eriksson, Henrik
    et al.
    Kungliga Teknikiska Högskolan.
    Eriksson, Kimmo
    Stockholm University, Faculty of Humanities, Centre for the Study of Cultural Evolution.
    Conjugacy of Coxeter elements2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2, p. -R4Article in journal (Refereed)
    Abstract [en]

    For a Coxeter group (W, S), a permutation of the set S is called a Coxeter word and the group element represented by the product is called a Coxeter element. Moving the first letter to the end of the word is called a rotation and two Coxeter elements are rotation equivalent if their words can be transformed into each other through a sequence of rotations and legal commutations. We prove that Coxeter elements are conjugate if and only if they are rotation equivalent. This was known for some special cases but not for Coxeter groups in general.

  • 31. Eriksson, Henrik
    et al.
    Eriksson, Kimmo
    Mälardalen University, School of Education, Culture and Communication.
    Conjugacy of Coxeter elements2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2, p. R4-Article in journal (Refereed)
  • 32.
    Eriksson, Henrik
    et al.
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Eriksson, Kimmo
    Conjugacy of Coxeter elements2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed)
    Abstract [en]

    For a Coxeter group (W, S), a permutation of the set S is called a Coxeter word and the group element represented by the product is called a Coxeter element. Moving the first letter to the end of the word is called a rotation and two Coxeter elements are rotation equivalent if their words can be transformed into each other through a sequence of rotations and legal commutations. We prove that Coxeter elements are conjugate if and only if they are rotation equivalent. This was known for some special cases but not for Coxeter groups in general.

  • 33.
    Eriksson, Henrik
    et al.
    KTH, School of Computer Science and Communication (CSC).
    Eriksson, Kimmo
    Words with intervening neighbours in infinite Coxeter groups are reduced2010In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 17, no 1, p. N9-Article in journal (Refereed)
    Abstract [en]

    Consider a graph with vertex set S. A word in the alphabet S has the intervening neighbours property if any two occurrences of the same letter are separated by all its graph neighbours. For a Coxeter graph, words represent group elements. Speyer recently proved that words with the intervening neighbours property are reduced if the group is infinite and irreducible. We present a new and shorter proof using the root automaton for recognition of reduced words.

  • 34. Eriksson, Henrik
    et al.
    Eriksson, Kimmo
    Mälardalen University, School of Education, Culture and Communication.
    Words with intervening neighbours in infinite Coxeter groups are reduced2010In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 17, no 1, p. N19-Article in journal (Refereed)
  • 35.
    Falgas-Ravry, Victor
    School of Mathematical Sciences Queen Mary University of London, London E1 4NS, UK.
    Minimal weight in union-closed families2011In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, p. P95-Article in journal (Refereed)
    Abstract [en]

    Let Omega be a finite set and let S subset of P(Omega) be a set system on Omega. For x is an element of Omega, we denote by d(S)(x) the number of members of S containing x.Along-standing conjecture of Frankl states that if S is union-closed then there is some x is an element of Omega with d(S)(x)>= 1/2|S|. We consider a related question. Define the weight of a family S to be w(S) := A.S|A|.SupposeSisunion-closed. How small can w(S) be? Reimer showed w(S) >= 1/2|S|log(2)|S|, and that this inequality is tight. In this paper we show how Reimer's bound may be improved if we have some additional information about the domain Omega of S: if S separates the points of its domain, then w(S) >= ((vertical bar Omega vertical bar)(2)). This is stronger than Reimer's Theorem when |Omega| > root|S|log(2)|S|. In addition we constructa family of examples showing the combined bound on w(S)istightexcept in the region |Omega| = Theta(root|S|log(2)|S|), where it may be off by a multiplicative factor of 2. Our proof also gives a lower bound on the average degree: if S is a point-separating union-closed family on Omega, then 1/ |Omega|Sigma(x is an element of Omega)d(S)(x)>= 1/2 root|S|log(2)|S| broken vertical bar O(1), and this is best possible except for a multiplicative factor of 2.

  • 36.
    Falgas-Ravry, Victor
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the codegree density of complete 3-graphs and related problems2013In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 20, no 4, p. Article number: P28-Article in journal (Refereed)
    Abstract [en]

    Given a 3-graph F, its codegree threshold co-ex(n, F) is the largest number d - d(n) such that there exists an n-vertex 3-graph in which every pair of vertices is contained in at least d triples but which contains no member of F as a subgraph. The limit [GRAPHICS] is known to exist and is called the codegree density of F. In this paper we generalise a construction of Czygrinow and Nagle to bound below the codegree density of complete 3-graphs: for all integers s >= 4, the codegree density of the complete 3-graph on s vertices K-s satisfies [GRAPHICS] We then provide constructions based on Steiner triple systems which show that if this lower bound is sharp, then we do not have stability in general. In addition we prove bounds on the codegree density for two other in finite families of 3-graphs.

  • 37.
    Falgas-Ravry, Victor
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Lo, Allan
    Subgraphs with large minimum ℓ-degree in hypergraphs where almost all ℓ-degrees are large2018In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 2, article id P2.18Article in journal (Refereed)
    Abstract [en]

    Let G be an r-uniform hypergraph on n vertices such that all but at most ε(n ℓ) ℓ-subsets of vertices have degree at least p(n-ℓ r-ℓ). We show that G contains a large subgraph with high minimum ℓ-degree.

  • 38.
    Falgas-Ravry, Victor
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Random subcube intersection graphs I: cliques and covering2016In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 3, article id P3.43Article in journal (Refereed)
    Abstract [en]

    We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Qd to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model 'random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Qd and for the appearance of s-cliques. In addition we pose a number of open problems.

  • 39. Fill, James Allen
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Ward, Mark Daniel
    Partitions with Distinct Multiplicities of Parts: On An "Unsolved Problem" Posed By Herbert Wilf2012In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 2, p. P18-Article in journal (Refereed)
    Abstract [en]

    Wilf's Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We refer to these as Wilf partitions. Using f(n) to denote the number of Wilf partitions,we establish lead-order asymptotics for ln f(n).

  • 40. Friedland, S.
    et al.
    Krop, E.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the number of matching in regular graphs2008In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 15, no 1Article in journal (Refereed)
    Abstract [en]

    For the set of graphs with a given degree sequence, consisting of any number of 2's and 1's, and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of m-matchings. We find the expected value of the number of m-matchings of r-regular bipartite graphs on 2n veritces with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for m-matchings in r-regular bipartite graphs on 2n vertices, and their asymptotic versions for infinite r-regular bipartite graphs. We prove these conjectures for 2-regular bipartite graphs and for m-matchings with m <= 4.

  • 41. Friedland, S.
    et al.
    Krop, E.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On the number of matchings in regular graphs2008In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 15, no 1Article in journal (Refereed)
  • 42. Friedland, S.
    et al.
    Krop, E.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
    On the number of matchings in regular graphs2008In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 15, no 1Article in journal (Refereed)
  • 43.
    Gomez, Daniel
    et al.
    University of Saskatchewan, Canada .
    Lundmark, Hans
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
    Szmigielski, Jacek
    University of Saskatchewan, Canada .
    The Canada Day Theorem2013In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 20, no 1Article in journal (Refereed)
    Abstract [en]

    The Canada Day Theorem is an identity involving sums of k x k minors of an arbitrary n x n symmetric matrix. It was discovered as a by-product of the work on so-called peakon solutions of an integrable nonlinear partial differential equation proposed by V. Novikov. Here we present another proof of this theorem, which explains the underlying mechanism in terms of the orbits of a certain abelian group action on the set of all k-edge matchings of the complete bipartite graph K-n,K-n.

  • 44. Grimmett, Geoffrey
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Random even graphs2009In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 1, p. R46-Article in journal (Refereed)
    Abstract [en]

    We study a random even subgraph of a finite graph G with a general edge-weight p is an element of (0, 1). We demonstrate how it may be obtained from a certain random-cluster measure on G, and we propose a sampling algorithm based on coupling from the past. A random even subgraph of a planar lattice undergoes a phase transition at the parameter-value 1/2p(c), where p(c) is the critical point of the q = 2 random-cluster model on the dual lattice. The properties of such a graph are discussed, and are related to Schramm-Lowner evolutions (SLE).

  • 45. Hofscheier, Johannes
    et al.
    Nill, Benjamin
    Öberg, Dennis
    Stockholm University, Faculty of Science, Department of Mathematics.
    On Ehrhart Polynomials of Lattice Triangles2018In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 1, article id P1.3Article in journal (Refereed)
    Abstract [en]

    The Ehrhart polynomial of a lattice polygon P is completely determined by the pair (b(P), i(P)) where b(P) equals the number of lattice points on the boundary and i(P) equals the number of interior lattice points. All possible pairs (b(P), i(P)) are completely described by a theorem due to Scott. In this note, we describe the shape of the set of pairs (b(T), i(T)) for lattice triangles T by finding infinitely many new Scott-type inequalities.

  • 46.
    Holmgren, Cecilia
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Sileikis, Matas
    Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..
    Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 2, article id P2.51Article in journal (Refereed)
    Abstract [en]

    We study fringe subtrees of random m-ary search trees and of preferential attachment trees, by putting them in the context of generalised Polya urns. In particular we show that for the random m-ary search trees with m <= 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random m-ary search trees for m <= 26 has asymptotically a normal distribution.

  • 47.
    Holmgren, Cecilia
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory. Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..
    Juskevicius, Tomas
    Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA..
    Kettle, Nathan
    Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..
    Majority Bootstrap Percolation on G(n, p)2017In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 1, article id P1.1Article in journal (Refereed)
    Abstract [en]

    Majority bootstrap percolation on a graph G is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have at least half of its neighbours infected become infected. We say that percolation occurs if eventually all vertices in G become infected. In this paper we provide sharp bounds for the critical size of the initially infected set in majority bootstrap percolation on the Erdos-Renyi random graph G(n,p). This answers an open question by Janson, Luczak, Turova and Vallier (2012). Our results obtained for p = clog(n)/n are close to the results obtained by Balogh, Bollobas and Morris (2009) for majority bootstrap percolation on the hypercube. We conjecture that similar results will be true for all regular-like graphs with the same density and sufficiently strong expansion properties.

  • 48. Hultman, Axel
    Directed subgraph complexes2004In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 11, no 1Article in journal (Refereed)
    Abstract [en]

    Let G be a directed graph, and let Delta(G)(ACY) be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of G. Similarly, we define Delta(G)(NSC) to be the simplicial complex with the edge sets of not strongly connected subgraphs of G as simplices. We show that Delta(G)(ACY) is homotopy equivalent to the (n-1-k)-dimensional sphere if G is a disjoint union of k strongly connected graphs. Otherwise, it is contractible. If G belongs to a certain class of graphs, the homotopy type of Delta(G)(NSC) is shown to be a wedge of (2n-4)-dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements.

  • 49.
    Hägglund, Jonas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On snarks that are far from being 3-edge colorable2016In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 2, article id P2.6Article in journal (Refereed)
    Abstract [en]

    In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.

  • 50.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Generalized Galois numbers, inversions, lattice paths, Ferrers diagrams and limit theorems2012In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 3, p. P34-Article in journal (Refereed)
    Abstract [en]

    Bliem and Kousidis recently considered a family of random variables whose distributions are given by the generalized Galois numbers (after normalization). We give probabilistic interpretations of these random variables, using inversions in random words, random lattice paths and random Ferrers diagrams, and use these to give new proofs of limit theorems as well as some further limit results.

12 1 - 50 of 67
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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