David Hök: Parvisa mönster i permutationer
Vi bestämmer formler för antalet permutationer av längd n med k fall som har 0 förekomster av mönstret q_1 och 1 förekomst av mönstret q_2, där q_1 och q_2 har längden 3.
Wednesday 21/2, 13.00 in MV:L14.
Håkan Lennerstad: Generalizations of the floor and ceiling functions using the Stern-Brocot tree
The seminar describes a very basic number theoretic problem with practical applications. The floor and ceiling functions of a rational number are generalized by optimally estimating from above and below by rational numbers with lower denominators. A ratio a/b is decomposed in c ratios preserving the numerator sum and the denominator sum, while maximizing the smallest and minimizing the largest ratio. We also consider the generalized ceiling-floor difference. This is zero iff c <= GCD(a,b), quantifying the distance to divisibility.
It turns out that the Stern-Brocot tree can be used in solving this problem. For example, it follows that no optimal decomposition contains more than three distinct ratios. The problem has arisen from a generalization of the so called 4/3-conjencture in computer science. The generalized floor function allows the optimal solution to this problem to be written in closed form.
Thursday 11/5, 10.15 in MV:L14.
Petter Brändén: Polynomials with the half-plane property, matroids and jump systems.
A multivariate polynomial has the half-plane property if it is non-zero whenever all variables have positive real parts. In a recent paper, Choe, Oxley, Sokal and Wagner proved that the support of a homogeneous multi-linear polynomial with the half-plane property is the set of bases of a matroid. They also raised the question if this can be generalized so that the support of any multivariate polynomial with the half-plane property is a jump system. A jump system is a generalization of matroids. We answer this question to the affirmative. We also give a characterization of multi-linear polynomials with the half-plane property. This is used to answer to two other questions posed by Choe and Wagner.
Friday 28/4, 13.15 in Mallvinden.
Anders Claesson: Conways servettproblem
Servettproblemet formulerades av John H. Conway och nedskrevs i "Mathematical Puzzels: A Connoisseur's Collection" av Peter Winkler.
För att parafrasera Winklers bok: En middag skall serveras vid en matematikkonferens. Vid ett runt bord skall n män - okunniga om etikett - placeras. Männen kommer fram till bordet en i taget i någon slumpvis ordning. När en gäst sätter sig ned kommer han att föredra den vänstra servetten med sannolikhet 1/2 och den högra servetten med sannolikhet 1/2. Om båda servetterna är tillgängliga tar han den han föredrar. Om bara en servett är ledig tar han den, oavsett om det är den föredragna servetten. Den tredje möjligheten är att ingen servett är tillgänglig, och den olycklige gästen får dinera utan servett. Vad är det förväntade antalet gäster som blir utan servett?
Jag kommer att diskutera hur man kombinatoriskt kan angripa detta problem. I själva verket kommer jag diskutera lösningen till det allmännare problemet: Vad är sannolikheten att k personer blir utan servett?
Tuesday 29/11, 15.15 in MD7.Ira Gessel: Indexed Permutations and Affine P-partitions
The theory of P-partitions relates the enumeration of permutations by descents to the study of sets of inequalities of the form x_i < x_j or x_i <= x_j and to posets associated with these inequalities.
Indexed permutations, introduced by Einar Steingrimsson, are permutations of the set {1, 2, 3, ... , n} in which each entry is given an integer subscript. For example, 1_0, 4_3, 3_-1, 2_3 is an indexed permutation with underlying permutation 1, 4, 3, 2. To determine the descents of an indexed permutation we first compare subscripts, and only if they are equal do we compare the entries.
We will show that the enumeration of indexed permutations by descents is closely related to the study of inequalities of the form x_i < x_j + k or x_i <= x_j + k where k is an integer. We associate certain infinite posets, satisfying a translation-invariance property, to sets of such inequalities, and the translation-invariant linear extensions of these posets correspond to indexed permutation.
Thursday 26/5, 16.00 in S2.Daniel Cardell: Fixpunkter i permutationsavbildningar (examensarbete)
Vi studerar (antalet) fixpunkter hos några avbildningar av permutationer till permutationer. Den första är Foatas "bijection fondamentale" som tar en permutation med k fall till en permutation med k överskott. Den andra är "maj-kodningen" av en permutation pi av längd n, d.v.s. permutationen vars i-te bokstav anger hur mycket maj ökar om man sätter in (n+1) på plats i i pi. Den tredje är en mer komplicerad bijektion som vi inte beskriver i detalj här. I alla tre fallen förfinas resultaten till att gälla permutationer med ett givet antal fall. Slutligen visar vi att antalet permutationer som undviker det generaliserade mönstret 12-3 och har exakt en förekomst av 3-12 är 3^n-2^n till antalet.
Thursday 26/5, 13.15 in S1.Niklas Eriksen: An introduction to gene order comparative genomics
Different bacterial species share the same set of genes and have few duplicates. Thus, bacterial genomes can be modelled as permutations on the same set of genes. By comparing these permutations, we can draw conclusions on the evolutionary relationship between different species of bacteria.
In this talk, we will present some ways to compute the evolutionary distance between species, using both computational and mathematical tools. This is an introductary talk, and no previous knowledge of the field is presumed.
Thursday 12/5, 10.15 in S4.Urban Larsson: Fibonacci arrays, Beatty sequences and Wythoff Nim
Abstract: Consider the permutation of the natural numbers which begins 1,3,2,6,8,4,11,5,14,16,7,...
It has the property that the differences f(n)-n are distinct, and f(n) is always the least number chosen so that this condition is satisfied. It turns out that this permutation has a rich variety of interpretations in terms of the concepts in the title, among others. We discuss these, and various attempts (including our own) to understand our permutation in a wider context.
Tisdag 1/3, 13.15 (one hour) in S1 Slides
S. Kitaev (Institut Mittag-Leffler): Independent sets in graphs: Enumeration and connections to other combinatorics
Let G=(V,E) be a simple undirected graph with vertex set V={1,2,..., n} and edge set E. An independent set (also called a stable set) of G is a subset S of V such that no two vertices in S are have an edge between them. The set of all independent sets of a graph G is denoted by I(G).
Determining the cardinality of I(G) is a an interesting (but hard) enumerative problem, which so far has not received much attention. We will sketch a couple of approaches to tackling the problem using Ferrers graphs (to be introduced in the talk), grid graphs and path-schemes. One of the solutions deals with an unexpected application of a result in combinatorics on words.
It turns out that in some cases there is a combinatorial interpretation for I(G). Namely, we might have a bijection between a set of independent sets of a graph and a set of other combinatorial objects. For instance, the set of independent sets of a staircase Ferrers graph on 2n vertices is in one-to-one correspondence with the parts of all compositions (ordered non-empty partitions) of n+1. In such a situation we may talk about coding the combinatorial objects in terms of independent sets.
Torsdag 3/2, 15.15 (one hour) in S2
Roger Lie: Patterns and permutations
Let p and t be permutations of the sets {1,...,n} and {1,...,k}, respectively. We say that p has an occurrence of the pattern t if there is a subsequence of p which is order-isomorphic to t. If there exists no such subsequence p is said to be t-avoiding.
The first part of this paper deals mainly with pattern avoidance but we also consider the problem of counting permutations with a prescribed number of occurrences of a given pattern.
A useful technique when working with patterns is generating trees. We will show how one can use this concept in proving pattern avoidance theorems.
We also give a brief account of generalised patterns, where the constraint that two entries adjacent in the pattern must also be adjacent in the permutation, is admitted. We then give a new proof of a result of Claesson and Mansour on the enumeration of permutations with exactly one occurrence of the generalised pattern 2-13.
In the second part we first consider the following problem. With n and k fixed, we count for every permutation p of length n the number of patterns of length k that occur in p. What does this distribution look like? Here we concentrate on cases where k is only slightly smaller than n, in particular where k=n-2. Computations show that we get prominent peaks in the distribution. We provide an explanation for this and in doing so we introduce the concept of links. By a link we mean a pair of consecutive numbers i and (i+1) that are adjacent in a permutation. We derive a pair of recurrence formulae which produces the number of permutations of length n with k links.
Finally we take a look at the diagonals, i.e. where (n-k) is kept constant, of these link numbers. We prove that the mth diagonal numbers are given by a polynomial in k of degree m-1, provided that k is greater than 0. We conclude by presenting conjectures on the values of these polynomials taken at 0 and -1.
Tisdag 1/6 kl. 13.15 i S1 Slides (In Swedish)
Lina Jansson: Excedances in 132-avoiding involutions
We compute the number of 132-avoiding involutions with respect to excedances. The 132-avoiding involutions with a given number of excedances can be constructed recursively. As a consequence, these involutions can be related to the Ballot paths, in a way that illustrates the excedance properties of the original involution. The proofs are done by constructing bijections, between 132-avoiding involutions of different lengths and between 132-avoiding involutions and Ballot paths.
Onsdag 26/5 kl. 13.15 i S1 Slides (In Swedish)
The main topic of this talk is the study of certain functional equations that occur in various combinatorial or probabilistic questions.
Examples can be found in the enumeration of walks in a quadrant (or, in probability, when one tries to find the law of the associated Markov chain), or in the enumeration of pattern-avoiding permutations. As the latter topic is dear to the heart of the locals, the examples I will study will be taken from this field: Baxter permutations, 1234 avoiding permutations, and so on.
What is special with these equations? They define certain generating functions which count permutations (or other objects) with respect to one main parameter (the lengths of the permutations), but also with respect with *two* other statistics, that are not so significant combinatorially, but are absolutely needed to *write* the equation.
An example being better than long and obscure explanations, here is one such equation:
Q(t;x,y)= 1 + txy Q(t;x,y) + t/x (Q(t;x,y)-Q(t;0,y)) + t/y (Q(t;x,y)-Q(t;x,0)).
It defines a series in t, whose coefficients are polynomials in x and y. The main problem is of course to solve such equations, and, more generally, to classify them according to the nature of their solutions: for instance, in the above example, Q(t;x,y) is actually an algebraic function of t,x,y.
Onsdag 3 mars kl 13.15, S1 Slides
Rieuwert J. Blok (Rome): Activity on matroids, and relations to topology and algebra
A matroid can be thought of as a ground set E together with a family of base-subsets. For example, a finite spanning set E for a vector space, together with the family of linear bases contained in E forms a matroid. Although initially largely motivated by problems in linear algebra and graph theory, matroid theory provides a unified framework for studying topics from a variety of areas including design theory, combinatorial geometry, lattice theory, hyperplane arrangements, and combinatorial optimization.
After ordering the ground set E linearly one can introduce the notion of activity. This is best seen in the context of a graphic matroid, but generalizes easily. A graphic matroid is the matroid on the edge-set of a connected graph G, where the base-sets are the spanning trees. Given a spanning tree T, any edge e not in T closes off a unique circuit C in T + e. If e happens to be the least edge in C, then e is called (externally) active for T. Note that by inserting e and removing any other edge from C one obtains a new spanning tree that is "close" to T, but cheaper. Activity is used for instance to define search algorithms in graphs. Also, the famous Tutte-polynomial is the activity generating function for the base-sets of the matroid.
An interesting invariant of a matroid M is its Orlik-Solomon algebra. For instance, in the context of a complex hyperplane arrangement, it is isomorphic to the cohomology ring of the arrangement's complement. In general however, it is unknown exactly what (combinatorial) aspects of the matroid it captures. It is known though that the independent sets of zero activity yield a (linear) basis for this algebra.
Las Vergnas introduced a partial order on the base-sets whose rank function is (external) activity; its atoms correspond to basis elements of the algebra. This poset encapsulates information on the linear dependence of other elements on the basis corresponding to its atoms. A fundamental invariant of this lattice, its Möbius function, was analyzed by Bruce Sagan and RJB through the topology of its order complex. At this point we present new directions for research, new results, and try to understand their meaning for the Orlik-Solomon algebra and its relation to the matroid.
No prior knowledge of matroid theory, lattice theory, or homology theory is required.
Onsdag 28/1 kl. 13.15-15 S1
Sergey Kitaev (University of Kentucky): On unavoidable sets, universal cycles and word patterns
Let A be an alphabet, A* the set of words over A and let S be a subset of A*. A word that does not contain any word from S as a subword is said to be free from S. The set of all words that are free from S is denoted by S'. If the words in S' are of bounded length, then S is called an unavoidable set.
One can think of a word pattern as a word containing each of the letters 1,2,...,k at least once, and no other letters. An n-pattern word is a word in which each subword of length n is a pattern. I will discuss certain numerical characteristics for n-pattern words and word patterns.
The sequence 00011101 contains every binary triple exactly once, if the end of the sequence is thought of as looping back to the beginning. This is an example of a universal cycle, which is called a (binary) de Brujin cycle. I will discuss a relation between the unavoidability problem for word patterns and intensively studied universal cycles. It turns out that there exists a universal cycle for word patterns of any length over any alphabet.
This is joint work with Alexander Burstein, Iowa State.
Tisdag 9/12 kl. 13.15 S1 Slides
Bodo Lass (Lyon): Acyclic orientations and the chromatic polynomial of a graph
The chromatic polynomial C(n), which is associated with each graph G, enumerates its proper colorings with n colors. Stanley showed that |C(-1)| is equal to the number of acyclic orientations of the graph, a result that was refined by Greene and Zaslavsky. We give a further refinement by interpreting each coefficient of C(n), when the polynomial is expressed in powers of n and (n-1).
A systematic use of the algebra of set functions gives very short and instructive proofs and allows us to use Lascoux's addition of alphabets to deduce results of Stanley on his symmetric function generalization of the chromatic polynomial.
The algebra of set functions used here is the ring A[V] := A[[V]]/S, where A is a commutative ring, V is the set of vertices of G, and S is the ideal generated by the squares of the vertices. Thus each monomial of A[V] is a square-free product of vertices of G (or 1, corresponding to the empty product).
Tisdag 2/12 kl. 13.15 S1
Ömer Egecioglu (Dept. of Computer Science, UC Santa Barbara): Combinatorics of a Polynomial Riemann Hypothesis
The consideration of a certain class of polynomial Riemann hypotheses leads to 3-term and higher order polynomial recursions. The asymptotic versions of the recursions in turn give rise to polynomial sequences where the zeros have the classical properties of the zeros of real orthogonal polynomials. Surprisingly, the associated linear functional is related to Alternating Sign Matrices (ASMs) with vertical symmetry. This talk will present the relationship between 4-term recursions, orthogonality, Hankel determinants, ASMs, classes of tableaux, and the world's longest certificate.
Torsdag 27/11 kl. 13.15 S2 Slides
Antoine Vella: Cyclic pattern avoidance
I will talk about "cyclic" modifications of pattern avoidance, in which we are allowed to cyclically shift the values and/or the positions in a permutation. I will also talk about some "classical" pattern avoidance.
I will give enumeration results for all cyclic patterns of length up to 4 and, via two "well-known" bijections, establish links with two classes of Dyck paths. These are the "non-decreasing" paths, previously studied by Barcucci et. al., and the apparently new "simple" Dyck paths. The simple Dyck paths are those that have at most two long up-edges or at most two long down-edges, where a long edge is a maximal sequence of the same kind of steps, containing at least two steps.
As a by-product, both of these classes give insight into permutation statistics on 321-avoiding permutations. In particular, I give a formula for the descent statistic on these permutations.
Torsdag 19/6 kl. 13.15 S1 Slides
Julian West (Malaspina University-College): Perfect matchings for the Gale-Robinson sequence
A domino is a rectangle of dimensions 1 by 2. An "Aztec diamond" of order n is a diamond-shape array of squares with height and width 2n. The number of different ways of covering an Aztec diamond of order n with dominos is 2^{n(n+1)/2}. (Alternatively this can be viewed as the number of perfect matchings in the dual graph.) There are a number of attractive proofs of this formula, notably the "condensation" proof used by Eric Kuo to verify the recursion formula.
We will generalize this proof to the "Gale-Robinson" recurrences, which have the form a(n)a(n-m) = a(n-i)a(n-j) + a(n-k)a(n-l), where i+j=k+l=m. (The Aztec diamond recurrence corresponds to the case of i=j=k=l=1.) In the process, we construct graphs analogous to the Aztec diamonds and in which the number of perfect matchings are given by the appropriate term in the Gale-Robinson sequence.
This is joint work with Mireille Bousquet-Mélou (Bordeaux) and Jim Propp (Brandeis)
To see a pretty picture related to this, go HERE!
Torsdag 19 juni S1 (time to be announced later) Slides
Sven Persson: Discrete Morse theory and applications
Discrete Morse functions will be related to combinatorial decompositions, such as generalized shellings, following Chari. We also discuss Morse matching and the pre-WDVV complex, as treated by Readdy.
Fredag 13/6 kl. 13.15 S1 Slides
This talk will be a continuation of a talk given in the number theory/algebraic geometry seminar last Fall with new results presented (for those who missed that talk, it shouldn't matter).
One of the classical questions of additive, combinatorial number theory is: how large can a subset of {1,...,n} be which contains no arithmetic progressions? This problem and its generalisations have inspired a lot of research over nearly a century.
In enumerative combinatorics, there has recently emerged the new field of studying permutations which avoid given "patterns." Here we will study a problem which is sort of a cross between these two. In its simplest form, it is best formulated as the following problem in combinatorial group theory:
Let G be an abelian group. A permutation p: G --> G is said to avoid arithmetic progressions if there does not exist any triple (a,b,c) of elements of G such that c-b = b-a and p(c)-p(b)=p(b)-p(a). The simplest question is, which groups possess such a permutation?
We give a complete answer for infinite groups (assuming the axiom of choice), and partial results for finite groups. We will also study some specific permutations of the natural numbers.
Tisdag 3/6 kl. 13.15 in MD9 Slides
Sergey Kitaev: Non-attacking placements on chessboards.
I will discuss placements of nonattacking pawns on an m-by-n chessboard, as well as the placements of the maximum number of nonattacking kings on a 2m-by-2n chessboard, the latter of which was studied by Wilf.
The basic approach for studying these problems is the transfer-matrix method, which I am going to explain for the problem of the kings. However, we will see how some other ideas work here also. In particular, I will explain a relation of the pawns problem to tiling an m-by-n board with square tiles of size 1-by-1 and 2-by-2. Also, I will mention a connection between these problems and the independent sets in certain graphs.
This is joint work with Toufik Mansour.
Tuesday May 27 15.15 in S1
Slides
Cecilia Holmgren: Discrete Morse Theory
I will discuss Robin Forman's article "A user's guide to discrete Morse theory". My goal is to present an overview of the subject of discrete Morse theory and explain how you can become a user of this theory. Discrete Morse-theory is closely related to classical Morse theory, which I will describe briefly.
Although discrete Morse theory is in many cases much simpler than the classical version, it is still a powerful tool that can be used to obtain results about the topology of spaces related to combinatorial objects such as simplicial complexes.
Discrete Morse theory often allows us to replace a simplicial complex K by a so called CW-complex that is simpler and easier to deal with, although it is homotopy equivalent to K and thus preserves many of the topological properties of K.
In discrete Morse theory, just as in the classical case, one works with Morse functions or with gradient vector fields of such functions, which are usually much easier to work with. I will describe how to construct such vector fields and why the vector field contains much of the important information about the function it arises from.
Torsdag 22 maj kl. 13.15 sal S1 Slides
Lina Jansson: Fixed points of poset maps and homology
The fixed-point properties of certain posets can be derived from the homology properties of the corresponding order complex. Some of these connections are discussed and a few proved. Basic definitions of homology groups are given. The results on posets and homology are from a paper by Baclawski and Björner in 1979.
Torsdag 3 april kl. 13.15 i S2
By means of Gröbner bases we can effectively answer questions about ideal membership and ideal identity in the polynomial ring k[x_1,..., x_n]. Furthermore, using Gröbner bases we can solve systems of polynomial equations, and do effective computations in k[x_1,...,x_n]/I, where I is an ideal. I will give an introduction to Gröbner bases addressed to novices without prior knowledge in the field.
Torsdag 20 Mars kl. 13.15 Sal S2 Slides
Petter Brändén: f-vectors of multicomplexes, and polynomials with real zeros
Abstract: Several interesting results and conjectures in algebraic combinatorics involve polynomials with positive integer coefficients that have (or are conjectured to have) only real zeros. We will talk about a theorem of Skandera and Bell which gives a combinatorial interpretation of the coefficients of a real-rooted polynomial: Any real-rooted polynomial with positive integer coefficients and constant term equal to one is the f-vector of a multicomplex.
A multicomplex M is a collection of multisets that is closed under inclusion. The k-th coordinate of the f-vector is the number of k-element multisets in M.
Tisdag 18 Mars kl. 13.15 Sal S2
Fredrik Engström: The Schützenberger-Kruskal-Katona Theorem
I will present a proof by Clements and Lindström of the Katona-Kruskal-Schutzenberger theorem characterizing the f-vectors of simplicial complexes.
Torsdag 13 Mars kl. 13.15 Sal S2
Toufik Mansour: The average norm of polynomials with a fixed coefficient set
Let T be any finite set of complex numbers. We say that a polynomial p(z) is a T-polynomial if all its coefficients are in T. If T={-1,1} these are called Littlewood polynomials. The N_{2a}-norm of a polynomial p(z) is essentially the integral (suitably normalized) of |p(z)|^{2a} on the unit circle. We give an explicit formula for the average of the N_{2a}-norm over all T-polynomials of degree n, where a is a positive integer and n a nonnegative integer.
Tisdag 4 mars kl. 13.15 Sal S2
I will give an introduction to entropy and its uses in combinatorics, illustrating it to prove the following theorem of Friedgut and Kahn: The maximum number of copies N(H,k) of a graph H that can appear in a graph with k edges is a constant times kr(H) where r(H) is the so called fractional cover number of H.
One aim of the talk will be to show that the entropy method is a nice complement to the probabilistic method in combinatorics that Jeff Steif talked about a few weeks ago.
I will also prove a theorem of Kahn and Lawrence about the number of independent sets in a regular bipartite graph.
All concepts needed will be introduced from scratch.
Torsdag 27 februari kl. 15.15 Sal S4
Einar Steingrimsson: The coloring ideal and coloring complex of a graph
Let G be a simple graph on d vertices. We define a monomial ideal K in the Stanley-Reisner ring A of the order complex of the Boolean algebra on d atoms. The monomials in K are in one-to-one correspondence with the proper colorings of G. In particular, the Hilbert polynomial of K equals the chromatic polynomial of G.
The ideal K is generated by square-free monomials, so A/K is the Stanley-Reisner ring of a simplicial complex C. The h-vector of C is a certain invertible transformation of the chromatic polynomial of G.
The combinatorial structure of the complex C is described explicitly and it is shown that the Euler characteristic of C equals the number of acyclic orientations of G.
Recently, Jakob Jonsson proved, among many other things, that the complex is constructible, and thus Cohen-Macaulay.
Torsdag 20 feb kl. 13.15 Sal S2
Elizabeth Wulcan: Pattern avoidance in involutions
We consider pattern avoidance in involutions. We give a complete solution for the number of involutions avoiding one or two classical 3-patterns, mainly by relating these to well known combinatorial structures such as Dyck paths and Young tableaux. The results for single 3-patterns were previously obtained by Simion and Schmidt. However, we give new proofs in most cases. We also give some results for the number of involutions avoiding generalised patterns.
Onsdag 18 dec. kl. 10.00 Sal S1
Toufik Mansour: Counting occurrences of 132 in even permutations
We study the generating function for the number of even (or odd) permutations on n letters containing exactly k occurrences of 132. It is shown that finding this function for a given k amounts to a routine check of all permutations in S2k.
Torsdag 12 dec. kl. 13.15 Sal S1
Petter Brändén: On real-rooted polynomials and their connection with combinatorics
In the last fifteen years, combinatorialists have become increasingly interested in real-rootedness of polynomials carrying combinatorial information.
In a paper from 1914, I. Schur defined a certain product on polynomials that preserves real-rootedness. We refine the technique in this paper to obtain new results on real-rootedness, and use this to strengthen recent results on polynomials related to posets.
Torsdag 5/12 kl. 13.15-15.15 Sal S1
We study the generating function for the number of permutations on n letters containing exactly r occurrences of 132. We show that finding this function for a given r amounts to doing certain computations on all permutations in S2r. This is joint work with Alek Vainshtein, Haifa.
I will also talk about counting generalized patterns of length 3 in a permutation, which is joint work with Anders Claesson.
Tisdag 1/10 kl. 15.15-16.15 Sal S4 Slides
We study generating functions for the number of permutations of length n that avoid two patterns. One of the patterns is always of length 3, while the other one can be of arbitrary length. The latter class contains all two-layered patterns and many more. It turns out that in a large variety of cases the answer can be expressed via Chebyshev polynomials of the second kind. Much of this is joint work with Alek Vainshtein, Haifa
Tisdag 24/9 kl. 15.15-16.15 Sal S4 Slides
Björn Winterfjord: Binary strings and substring avoidance (Masters thesis)
A binary string b is said to avoid a binary string s if b does not contain s as a substring. As an example, the string 10011011 avoids the string 111, but not the string 011 (which appears twice).
An interesting question is how many strings of length n avoid a given string. For example, the number of strings of length n avoiding 00 is given by the n-th Fibonacci number. More generally, we may ask for the number of strings of length n avoiding all strings from an arbitrary set of strings.
We give an explicit answer to this question, in terms of a rational generating function. In the case of avoiding the string 00, this is the function 1/(1-x-x2). The general solution involves determinants of matrices whose entries are computed from the correlation of the strings involved, that is, how two strings can overlap each other.
Torsdag 23/5 kl. 13.15 Sal S1
Petter Brändén: The Poset Conjecture
The Poset Conjecture (or Neggers-Stanley Conjecture) asserts that certain polynomials associated with a finite poset have real nonpositive zeros. The conjecture has been verified for all posets of size at most 7 and proved for certain classes of posets. It has also been shown that the property involved is preserved under certain operations on posets.
We will state some of the conjecture's implications and give some results related to it. We will also talk about the relation between real zeros of a polynomial and log-concavity and unimodality of its coefficients. A sequence of numbers is unimodal if it increases to a maximum and then decreases. Unimodality of combinatorial sequences is often intuitively plausible and easy to prove analytically, but exceedingly hard to prove combinatorially.
Onsdag 12/12 kl 13.15-15 S1 Slides
Sverker Lundin: Young Tableaux and pattern avoiding involutions
We study some connections between Young Tableaux, Ballot numbers and pattern avoiding permutations. We also show that, for some patterns p, the number of involutions avoiding p can be explained in terms of the cycle structure of p. To facilitate the interpretation of patterns in terms of their cycle structures, we propose a technique for visualisation of permutations of length at most 4.
Onsdag 28/11 kl. 13.15-15 S1 Slides
Sergey Kitaev: Partially Ordered Generalized Patterns
A descent in a permutation a1a2
. . . an is an i such that ai
> ai+1. The distribution of the number of descents is
given by the well known Eulerian numbers. We define a new statistic,
namely the maximum number of non-overlapping descents in a
permutation. Two descents i and j overlap if
j=i+1.
We find the distribution of this new statistic by using partially
ordered generalized patterns (POGPs). These are generalizations of
the Babson-Steingrimsson patterns, which in turn generalize the
classical permutation patterns. We also introduce shuffle patterns and
multi-patterns as special cases of POGPs and investigate them.
Onsdag 21/11 kl. 13.15-15 S1
Slides
Anders Claesson: Permutations, Patterns, and Binary Trees
I will present some recent results on the number of permutations avoiding a given set (typically a pair) of patterns. If one casts these results in their appropriate setting, namely binary trees, then they are quite easy to prove. I will show how permutations avoiding a given set of patterns can be put in one-to-one correspondence with a family of binary trees, and how to enumerate the trees. No previous knowledge of patterns or binary trees is required to understand this talk.
Onsdag 10/10 kl. 13.15-15 S1
Let A be an alphabet and A* the set
of words over A. A set of prohibited words is a
subset S of A*. A word that does not
contain any word from S as a subword is said to be
free from S. The set of all words that are free from
S is denoted by S'. If there exists an integer
k such that the length of any word in S' is less
than k, then S is called a complete set.
I will give some examples of complete and incomplete sets, and then
consider two problems about complete sets for a special class of sets
of prohibitions. Namely, what is the minimal size of such a complete
set, and what is the maximum length of a word that is free from some
set S in this class. I will also mention the case of an
arbitrary set of prohibited words.
I will also discuss the complexity of two problems. In one of them we
decide if a given set of prohibited subwords S is complete;
in the other one we ask the question if there exists, for a given
m, a word of length at least m that is free from
S.
Onsdag 26/9 kl. 13.15-15 S1
Slides
Anders Claesson: The Coding of Permutations and Set Partitions by Labelled Motzkin Paths
A Motzkin path is a lattice path in the plane with unitary east, north-east and south-east steps that starts at the origin and ends at the x-axis and newer goes below the x-axis. A labelled Motzkin path is a Motzkin path together with a vector of labels, one label for each unitary step.
In 1979 Françon and Viennot gave a bijection between permutations and a family of labelled Motzkin paths. I will present this bijection, and also an injection, due to Flajolet (1980), from set partitions into the same family of labelled Motzkin paths. Finally, I may discuss the effect of applying the Françon-Viennot bijection to (a-cb)-avoiding permutations. As I have recently proved, (a-cb)-avoiding permutations are in one-to-one correspondence with set partitions.
Torsdag 5/4 kl. 13.15-15 S2
Petter Brändén: Continued Fractions and Increasing Subsequences in Permutations
We present a generalization of a theorem of Robertson, Wilf and Zeilberger, giving a continued fraction expansion for the joint distribution of the numbers of increasing subsequences of length k in 132-avoiding permutations, for all k simultaneously. (A permutation is 132-avoiding if it contains no subsequence whose first letter is the smallest and whose middle letter is the largest). This shows that any Stieltjes continued fraction with monomial denominators is the generating function of a permutation statistic consisting of a linear combination of statistics counting increasing patterns of various lengths. Applications are given to several other combinatorial structures and continued fractions.
A Stieltjes continued fraction with monomial denominators is on the form 1/(1-x/(1-y/(1-z/... where x, y, z,... are monomials in any set of variables.
This is joint work with Anders Claesson and Einar Steingrímsson.
Torsdag 22/3 kl. 13.15-15 S1
I will present the basic concepts of Latin Squares, and some of the problems of interest regarding them. From the intuitive approach that views Latin Squares as arrays with some permutation properties, we then move to an approach that views Latin Squares as a kind of algebraic structure called quasigroups (cancellative groupoids).
The properties of Latin Squares and problems related to them are then phrased in terms of equational formulas in quasigroups. These formulas can be translated into propositional formulas using a technique developed by H. Zhang and others. A computer program for determinining propositional satisfiability can then be used to solve the problems of existence of Latin Squares with interesting properties. In particular, I will give an overview of the SATO model generator, a software developed by H. Zhang based on the Davis-Putnam method for satisfiability problems.
Many previously open existence problems of Latin Squares have been solved by combining the translation technique and the model generator software, and I will give a summary of these results. Finally, I will discuss how this translation method can be refined and adapted to more complex Latin Squares problems, such as Latin Squares with holes.
Måndag 29/1 kl. 15.15-17 S2 Slides
Svante Linusson, Linköping: The Random Assignment Problem
Let A be an n by n matrix with non-negative entries ai,j, which can be thought of as the cost of letting machine i do job j. It is a well studied problem in optimization to find the best assignment of jobs to machines to minimize the cost, i.e. to find the minimum over all permutations p of the sum of ai,p(i) over all i.
If we now let the entries be random variables, the size of the minimal assignment is also a random variable. There is a beautiful conjecture from 1998 by Parisi that says that if the ai,j are all exponentially distributed with mean one, then the expected value of this minimal assignment is 1+1/4+1/9+...+1/n2. This conjecture has been verified up to n=7. There is no explanation why such a simple answer comes up. Many partial results and some wrong proofs by physicists have been published in the last years. There have also been several generalizations of this conjecture which show surprisingly simple formulas as well, the latest by Johan Wästlund and myself using tools from enumerative combinatorics. No deep knowledge of probability theory is needed to follow the talk.
Fredag 26/1 kl. 13.15-15 S2
Kimmo Eriksson, Mälardalens Högskola: Two-sided matching
Make the standard assumption in game theory that people behave rationally. Can n men and n women form marriages in such a way that afterwards no pair will find it preferable to divorce their current partners and match up together instead? I will present the basic theory of stable matchings (the stable marriage theorem of Gale and Shapley) and discuss some recent progress on related problems, where money and bisexuality is added to the model.
Torsdag 11/1 kl. 14-16 S1
Sergey Kitaev: Pattern avoidance
A k-pattern p is a permutation on {1,2,...,k}. A permutation of n letters is said to avoid the pattern p if it contains no subsequence whose letters are in the same relative order as those of p. The study of pattern avoidance deals with the (surprisingly hard) problem of finding the number of permutations of length n that avoid a given pattern. A generalization is to determine the number of permutations with exactly k occurrences of a given pattern.
I will review a classical paper on pattern avoidance by Simion and Schmidt from 1985 and some of the results obtained since then.
Among other things, I will talk about the relation of this problem to that of "stack-sortable" permutations introduced by Knuth, as well as a technique called "generating trees."
I will also mention recent results by Anders Claesson and myself, respectively, that concern avoidance of the generalized patterns recently introduced by Babson and Steingrímsson, where some of the letters in a pattern are required to be adjacent in the permutation.
Tisdag 14/11 kl. 13.15-15 S1
Slides
Einar Steingrimsson: Generalized permutation patterns and a classification of the Mahonian statistics
Every mathematician knows the number of inversions of a permutation. Its distribution on the symmetric group, which is given by (1+x)(1+x+x2)···(1+x+···+xn), is the defining criterion of the Mahonian permutation statistics. Two such statistics have been known for a hundred years, but in the last decade scores of them have been discovered in different contexts, ranging from pure combinatorics to algebra and orthogonal polynomials.
Seemingly, these statistics have very different character, which is underscored by their disparate definitions. However, we shall show that almost all Mahonian statistics in the literature essentially belong to a class of statistics containing only fourteen different such. The classification was achieved by generalizing the idea of permutation patterns, whose study has grown explosively in the last five years or so.
This is joint work with Eric Babson, Seattle. I will also mention recent work by Anders Claesson in this area.
Tisdag 26/9 kl. 13.15-15 S2 Slides
Sven Persson: Combinatorial Chemistry
In this talk we will show that enumeration under finite group action can cover well known examples of combinatorial chemistry.
Firstly we will introduce some concepts from graph theory, such as molecular graphs, reaction schemes and topological indices. We will also discuss concepts as permutations, symmetry and symmetric groups, finite group action and orbits, and present the Cauchy-Frobenius lemma. The main point will be a demonstration of how these concepts and methods can be utilized to evaluate the size of combinatorial libraries.
Moreover, we can obtain a generating function for the elements of a library, which enumerates these elements by weight.
Finally we show how to construct the library using the double coset reformulation of the orbits and orderly generation. The talk will be concluded by a brief discussion on corresponding software and on screening of the combinatorial libraries generated.
Måndag 29/5 kl. 13.15-15 S1
Petter Brändén: Shellable complexes and lattice paths
A shelling of a simplicial complex is an ordering of its maximal simplices (w.r.t. inclusion) that allows one to compute the h-vector of the complex in a simple way. The h-vector is an invertible transformation of the f-vector, which in turn counts the number of simplices of cardinality k for each k.
I will talk about shellings and h-vectors of certain simplicial complexes associated to some much studied lattice paths, namely the Dyck paths. Dyck paths are paths in the positive quadrant of the plane, from the origin to (2n,0), with steps of type (1,1) and (1,-1).
I will prove some theorems concerning statistics defined on Dyck paths. These statistics are related to the ballot numbers, the Catalan numbers and the Narayana numbers and the theorems shed light on previously unnoticed connections to shellings of the order complexes of certain posets.
Fredag 26/5 kl. 15.15-17 S1 Paper
Olof Hanner: On Bridge Movements
When organizing competition in the game of bridge you meet some combinatoric situations. They will be considered mainly from the practical point of view but have connections with Hadamard matrices and orthogonal Latin squares.
Måndag 22/5 kl. 13.15-15 S1
Peter Hegarty: Extremal set systems
This talk will introduce the audience to an area of combinatorics whose scope is not very well-defined, since obviously problems of extremisation arise in many branches of the subject and in many different contexts. As an informal definition, we might say that we are interested in extremal problems related to (finite) collections of finite sets which are assumed to satisfy some property of a purely "set-theoretic" nature (rather than say graphical or arithmetic, for example). Having elaborated on this statement, I will discuss some of the best-known problems in the field, both solved and unsolved, together with (hopefully) one or two ideas of mine which have yet to see the light of day. By the way, despite all the references above to sets, the talk will have absolutely nothing to do with set theory !
Måndag 15/5 kl. 12.30-14.15 S1 Slides and notes
Sergey Kitaev: The Involution Principle and the Rogers-Ramanujan identities
The number of ways to partition the integer n into parts congruent to 1 or 4 modulo 5 is equal to the number of partitions of n whose parts differ by at least 2.
This is one of the famous Rogers-Ramanujan identities, about which G.H. Hardy once remarked that ``there are now seven published proofs ... but none of these proofs can be said to be `simple' and`straightforward'... and no doubt it would be unreasonable to expect a really easy proof.'' G.A. Andrews added in 1976 that Hardy's comments ``are still true today.''
The purpose of this talk is to give a general method for constructing bijective proofs, the so called Involution Principle of Garsia and Milne. The Rogers-Ramanujan identities are among a myriad of partition identities that the Involution Principle produces bijective proofs of.
Måndag 8/5 kl. 13.15-15 S1 Slides
Fredrik Engström: Ramsey Theory
If six people are having a party then either three of them mutually know each other or three of them mutually do not know each other. This result is a special case of the finite version of Ramsey's theorem, which is the main theorem in Ramsey theory.
In the first part of the talk I will state and prove some of the major theorems in Ramsey theory, including the infinite and the finite version of Ramsey's theorem, Van der Waerden's theorem and the Hales-Jewett theorem.
In 1977 J. Paris and L. Harrington found a very interesting version of Ramsey's theorem. They proved that although this version is true (i.e. it is a true statement about the natural numbers) it can not be proved by finitistic arguments (i.e. it can not be proved in Peano Arithmetic). This is the first ``natural'' example of such a theorem (the first example of such a theorem is the one that arises in Gödel's incompleteness theorem). This result is known as the Paris-Harrington theorem. In the second part I will try to give an argument why this is so.
Torsdag 4/5 kl. 13.15-15 S2 Notes
Devdatt Dubhashi: Sorting under Partial
Information: Balanced Pairs and Graph Entropy
It is folklore that to sort a list of n numbers, it is necessary and sufficient to make n log n comparisons. This, if one is given no information to start with. Now suppose we are given some partial information for free at the beginning (represented by a partial order on the underlying elements). How many further comparisons are required? A natural information theoretic answer suggests itself. I will survey two approaches to determining how good the information theoretic bound is.
Tisdag 2/5 kl. 13.15-15 S2 References
Konstantin Karagatsos: The Matrix-Tree theorem and generalizations
The Matrix-Tree theorem states that the number of spanning trees of a graph G is equal to the determinant of any cofactor of the Laplacian of G. The Laplacian is a slight variation of the adjacency matrix of G. This classical result can be traced back to Kirchhoff, Sylvester, Cayley and Maxwell, in the latter half of the nineteenth century. We will consider some recent generalizations of this theorem, and relations to other graph invariants.
Torsdag 27/4 kl. 13.15-15 S2 Slides
The study of combinatorics of words (finite sequences of elements of a set) is naturally carried on within the framework of free monoids. A short introduction to free monoids, their associated concepts and some useful properties will be provided, mainly the ideas and results that are useful for such a combinatorial study.
The rest of this talk will deal with free monoids arising in the study of rearrangements of words, a rearrangement being just a permutation of the symbols of a word. Two specific monoids (derived by sets of commutation rules), called the flow monoid and the circuit monoid, are of particular interest. These monoids allow us to extend to arbitrary words the combinatorial result known as 'the first fundamental transformation.' In the case of permutations (words with no repeated letters), this transformation proves the equidistribution of two statistics on permutations, namely the number of descents and the number of excedances. This extension will be explained in the last part of the talk.
Måndag 10 april kl. 13.15-15 S3 Slides
A 2-separated path in the n-dimensional unit cube Cn is a sequence of adjacent vertices of the cube such that the distance between any two non-adjacent vertices is at least two (the distance is the number of coordinates in which the vertices differ). Let L(n) be the maximal length of such a path in Cn . A problem is to find L(n) for each n.
In 1969, Evdokimov found the order of L(n), which is equal to a constant times 2n. The problem was not solved by any complicated geometric considerations, but rather by considering the following equivalent problem: Find a word W of maximal length in an n-letter alphabet, such that any subword S of W (of length greater then one) has at least two letters that occur an odd number of times in S.
Måndag 3 april kl. 13.15-15 S1 Slides
Anders Claesson: Rook Theory
I will discuss the problem of placing a fixed number of rooks on a subset of a finite "chess-board" in such a way that no two rooks attack each other. I will also address a few applications of this theory. It is easy to see that many problems involving permutations with restrictions, such as permutations with no fixed points, can be reduced to a problem of placing non-attacking rooks on a board. A more subtle application is that the Stirling numbers of the second kind count the number of ways of placing non-attacking rooks on a triangular board. Finally, I will try to make visible the relationship between the rook polynomial of a general board and the chromatic structure of an associated set of graphs.
Monday March 20, 13.15-15, S1 Slides
Einar Steingrímsson: Linear algebra in combinatorics.
I will review a paper by Gian-Carlo Rota where he derives many properties of the Bell numbers (counting the partitions of a set) using elementary linear algebra. I will also discuss other uses of linear algebra in combinatorial problems, in particular the combinatorial meaning of certain base changes for vector spaces of polynomials. Finally, I may mention some example(s) from recent literature using linear algebra to solve enumerative problems.
Monday March 13, 13.15-15, S1
Julian West (Malaspina College, Canada):
Jeux de Tableaux: Complementation and Internal Insertion
Note: The first half of the talk will be an introduction to Young Tableaux and jeu-de-taquin.
We study four operations defined on pairs of Young tableaux. Algorithms for the first three involve the familiar procedures of jeu de taquin, row insertion, and column insertion, respectively. The fourth operation is new, although specialised versions have appeared previously. Like the other three operations, this new operation may be computed with a set of local rules in a growth diagram, and it preserves Knuth equivalence class. Each of these four operations gives rise to an a priori distinct theory of dual equivalence. We show that these four theories coincide. The four operations are linked via the involutive tableau operations of complementation and conjugation in illuminating commutative diagrams. This is joint work with Tom Roby and Frank Sottile.
Fredag 10 december kl. 13.15-15.15 S1
Eric Babson, Univ. of Washington, Seattle: The space of simplices
Let X be the space of all affinely independent sets of n labeled points in complex projective n-1 space. This is the space of all (n-1)-simplices where two simplices are close to each other if and only if their corresponding vertices are close to each other.
We wish to construct a space which is a compactification of X and which records all the faces of each simplex. This can also be phrased as finding a space mapping to X = SLn which factors through all of the Bott-Samuelson resolutions. Our goal is to construct a smooth, minimal such compactification.
This is a problem which in the n = 3 case was studied by Schubert, and has applications to enumerative geometry questions. In particular, once the space is constructed, we wish to compute the intersection ring. This might allow the computation of such values as the number of tetrahedra in projective 3-space with all 6 edges tangent to each of 2 given surfaces.
At this point we have constructed the space for n = 4, and computed most of it's intersection ring. We also have a space which we conjecture to work for all n.
This is joint work with Paul Gunnells and Richard Scott.
Onsdag 25 augusti kl. 13.15-15 S1
Bob Clarke, Adelaide: A new Mahonian permutation statistic
related to derangements
A permutation statistic is a function from the symmetric group Sn to the natural numbers. The most familiar such is INV, the number of inversions of a permutation. A statistic equidistributed with INV is called Mahonian. A new Mahonian statistic will be described, and some open problems discussed.
Torsdag 13 maj 13.15 - 14.15 S2
Vincent Moulton, Mitthögskolan: Injective hulls, six-point
metrics, and octehedral-free split systems
In this talk we give a brief introduction to T-theory, a new branch of discrete mathematics concerned with the theory of similarity. We then discuss its application to the analysis of six-point metrics, which leads us via a curious route to Buneman networks.
Tisdag 13 april, 13.15-14.15 S1
Richard Ehrenborg, Cornell: Generic canonical
forms for polynomials and tensors.
Abstract: A result due to Sylvester is that a generic polynomial of degree 2k-1 in two variables can be written as the sum of k (2k-1)th powers of linear polynomials. This and other similar results can be proved using the theory of apolarity. This theory also gives upper bounds for the essential rank of higher dimensional matrices.
Måndagen den 2/6 kl 13.15-14.15 S1