| 51. |
- Eriksen, Niklas, 1974-
(author)
-
Expected number of breakpoints after t random reversals in genomes with duplicate genes
- 2008
-
In: Discrete Applied Mathematics. - Amsterdam, Netherlands : Elsevier. - 0166-218X .- 1872-6771. ; 156:12, s. 2320-2335
-
Journal article (peer-reviewed)abstract
- In comparative genomics, one wishes to deduce the evolutionary distance between different species by studying their genomes. Using gene order information, we seek the number of times the gene order has changed between two species. One approach is to compute the method of moments estimate of this edit distance from a measure of dissimilarity called the breakpoint measure. In this paper, we extend formulae and bounds of this estimate on gene permutations to genomes with duplicate genes.
|
|
| 52. |
- Eriksson, Henrik, et al.
(author)
-
Conjugacy of Coxeter elements
- 2009
-
In: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 16:2, s. R4-
-
Journal article (peer-reviewed)
|
|
| 53. |
|
|
| 54. |
- Hellström, Lars, 1974-
(author)
-
Critical Pairs in Network Rewriting
- 2014
-
In: IWC 2014. ; , s. 9-13
-
Conference paper (peer-reviewed)abstract
- This extended abstract breifly introduces rewriting of networks (directed acyclic graphs with the extra structure needed to serve as expressions for PROducts and Permutations categories) and describes the critical pairs aspects of this theory. The author's interest in these comes from wanting to do equational reasoning in algebraic theories (such as Hopf algebras) that mix ordinary operations with co-operations; networks then serve as a formalism for expressions.The main message is to point out two phenomena that arise in network rewriting. The first is that of non-convexity of rules, wherein the left hand side of a rule need not be syntactically similar to a symbol in any extension of the underlying signature. The second is one of critical pairs potentially arising where two redexes wrap around each other even when they do not intersect.
|
|
| 55. |
- Krüger, Oliver, 1988-
(author)
-
On linear graph invariants related to Ramsey and edge numbers : or how I learned to stop worrying and love the alien invasion
- 2019
-
Doctoral thesis (other academic/artistic)abstract
- In this thesis we study the Ramsey numbers, R(l,k), the edge numbers, e(l,k;n) and graphs that are related to these. The edge number e(l,k;n) may be defined as the least natural number m for which all graphs on n vertices and less than m edges either contains a complete subgraph of size l or an independent set of size k. The Ramsey number R(l,k) may then be defined as the least natural number n for which e(l,k;n) = ∞ .In Paper I, IV and V we study strict lower bounds for e(l,k;n). In Paper I we do this in the case where l = 3 by, in particular, showing e(G) ≥ (1/3)(17n(G) - 35α(G) - N(C4;G)) for all triangle-free graphs G, where N(C4;G) denotes the number of cycles of length 4 in G. In Paper IV we describe a general method for generating similar inequalities to the one above but for graphs that may contain triangles, but no complete subgraphs of size 4. We then show a selection of the inequalities we get from the computerised generation. In Paper V we study the inequality e(G) ≥ (1/2)(ceil((7l - 2)/2)n(G) - l floor((5l + 1)/2)α(G))for l ≥ 2, and examine the properties of graphs G without cliques of size l+1 such that G is minimal with respect to the above inequality not holding, and show for small l that no such graphs G can exist.In Paper II we study constructions of graphs G such that e(G) - e(3,k;n) is small when n ≤ 3.5(k-1). We employ a description of some of these graphs in terms of 'patterns' and a recursive procedure to construct them from the patterns. We also present the result of computer calculations where we actually have performed such constructions of Ramsey graphs and compare these lists to previously computed lists of Ramsey graphs.In Paper III we develop a method for computing, recursively, upper bounds for Ramsey numbers R(l,k). In particular the method uses bounds for the edge numbers e(l,k;n). In Paper III we have implemented this method as a computer program which we have used to improve several of the best known upper bounds for small Ramsey numbers R(l,k).
|
|
| 56. |
- Linusson, Svante, et al.
(author)
-
On random shifted standard Young tableaux and 132-avoiding sorting networks
-
Other publication (other academic/artistic)abstract
- We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman-Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.
|
|
| 57. |
- Sjöstrand, Jonas
(author)
-
On the sign-imbalance of partition shapes
- 2005
-
In: Journal of combinatorial theory. Series A (Print). - : Elsevier BV. - 0097-3165 .- 1096-0899. ; 111:2, s. 190-203
-
Journal article (peer-reviewed)abstract
- Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2([n/2]). We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux. We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.
|
|
| 58. |
- Sjöstrand, Jonas
(author)
-
The cover pebbling theorem
- 2005
-
In: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 12:1, s. N22-
-
Journal article (peer-reviewed)abstract
- For any configuration of pebbles on the nodes of a graph, a pebbling move replaces two pebbles on one node by one pebble on an adjacent node. A cover pebbling is a move sequence ending with no empty nodes. The number of pebbles needed for a cover pebbling starting with all pebbles on one node is trivial to compute and it was conjectured that the maximum of these simple cover pebbling numbers is indeed the general cover pebbling number of the graph. That is, for any configuration of this size, there exists a cover pebbling. In this note, we prove a generalization of the conjecture. All previously published results about cover pebbling numbers for special graphs (trees, hypercubes et cetera) are direct consequences of this theorem. We also prove that the cover pebbling number of a product of two graphs equals the product of the cover pebbling numbers of the graphs.
|
|
| 59. |
|
|
| 60. |
- Strohmayer, Henrik
(author)
-
Operads of compatible structures and weighted partitions
- 2008
-
In: Journal of Pure and Applied Algebra. - : Elsevier BV. - 0022-4049. ; 212:11, s. 2522-
-
Journal article (peer-reviewed)abstract
- In this paper we describe operads encoding two different kinds of compatibility of algebraic structures. We show that there exist decompositions of these in terms of black and white products and we prove that they are Koszul for a large class of algebraic structures by using the poset method of B. Vallette. In particular we show that this is true for the operads of compatible Lie, associative and pre-Lie algebras.
|
|
