Courses

Topics on Matroid Theory

Henry Crapo (Centre de Recherche Les Moutons Matheux, La Vacquerie-et-Saint-Martin-de-Castries, France)

The concept of matroid is a combinatorial generalization of those relations holding in any finite set of vectors in any vector space, or any finite set of points in a projective geometry. The theory was initially developed in the 1930's by Hassler Whitney, Saunders MacLane, and Garrett Birkhoff. Characterizations of matroids representable as structures related to graphs, those representable over the field of two elements, and similar problems, were solved by William Tutte in the 1960's.

For those who have not previously done any serious study of matroids, we will give a brief introduction to the basics, in a preliminary talk.

Our first talk deals with the interplay between algebra and geometry, as developed in the now classical works of Hermann Grassmann, Giuseppe Peano, Henry Baker, Luigi Cremona, and Emil Artin. Our primary goal is to explain the significance of projective conditions, which may or may not hold in a geometric figure, and which determine properties of the figure relative to rigidity, relative to the possibility of lifting to higher dimensions, and the like. Recent developments include the definition of the Whitney algebra of a matroid, in which such properties find an algebraic formulation.

The second talk looks more closely at two of these applications: the rigidity of graphs viewed as bar and joint structures in d-dimensional space, and the closely related topic of spatial interpretation of polyhedral figures drawn in the plane.

Research in matroid theory is a domain currently witnessing major developments, chiefly within what is known as the matroid minors project, headed up by Jim Geelen, Bert Gerards and Geoff Whittle. Their goal is to extend to matroids the recent theory of graph minors, due to Neil Robertson and Paul Seymour. The aim is to settle a number of conjectures put forward in the 1960's and 1970's by William Tutte and Gian Carlo Rota. Our final talk will provide a glimpse of these remarkable and contemporary theoretical advances.

Topics covered are:

A brief introduction to the basics of matroid theory.
The dialectics of algebra and geometry.

• The complete quadrilateral.
• Arithmetic on the circle.
• Theorem proving.
• The Whitney algebra of a matroid.

Matroids from mechanics and scene analysis.

• Isostatic structures.
• Lifting planar scenes.
• Pure conditions, special position.

A quick sketch of the new frontiers: The matroid minors project. Geelen, Gerards and Whittle.

Triangulations of Polytopes

Francisco Santos (Universidad de Cantabria, Spain)

Triangulations of polytopes play an important role in several parts of mathematics, both pure and applied. This course is an introduction to them, focusing on their relation to oriented matroids and in the theory of regular triangulations and secondary polytopes developed in the last twenty years. We will follow parts of Chapters 2 and 4 of the recent book Triangulations: Structures for Algorithms and Applications (Algorithms and Computation in Mathematics, Vol 25), by J. A. de Loera, J. Rambau and F. Santos.

Topics covered are:

The oriented matroid of a point configuration.
Triangulations of point configurations. Regular triangulations.
Circuits and flips.
Gale transforms. Triangulations vs. Chambers
The secondary polytope of a point configuration.

There will be a problem session for this course.

Contributed Talks

Monday

Rui Duarte (CIDMA - Universidade de Aveiro, Portugal)

Bipartite hypermaps

Abstract:

A hypermap is a cellular imbedding of a hypergraph on a surface. A hypermap is bipartite if we can divide its set of hypervertices in two parts in such a way that consecutive hypervertices around a hyperedge or a hyperface are contained in alternate parts.

In this talk we will see some operators from the category of hypermaps to the category of bipartite hypermaps, and their properties. We will also see the classification of bipartite hypermaps with large symmetry group on surfaces of small genus.

Olga Azenhas (CMUC - Universidade de Coimbra, Portugal)

Key polynomials and crystal graphs in type \(C\)

Abstract:

Key polynomials (in \(n\) variables) were introduced by Demazure for all Weyl groups and were studied combinatorially in type \(A\) by Lascoux and Schützenberger. In type \(A\) they are a linear basis for the ring \(\Z[x_1, x_2, \ldots,x_n]\) which contain the linear basis of Schur polynomials for the subring of symmetric polynomials under the action of the symmetric group, and, in type \(C\), for the ring of Laurent polynomials in the variables \((x_1,\ldots,x_n)\) which contain the linear basis of symplectic Schur polynomials for the subring of symmetric Laurent polynomials under the action of the hyperoctahedral group. In type \(A\), Lascoux and Schützenberger produced a crystal graph indexed by Young tableaux to describe a key polynomial and have characterized the tableaux indexing the vectors of the corresponding Demazure crystal.

A key polynomial of type \(C\) may also be described by a subset of a crystal graph of type \(C\) indexed by sympletic tableaux in the sense of De Concini or Kashiwara and Nakashima. This crystal structure is obtained by means of the crystal operations in type \(C\) to give a combinatorial interpretation of a Demazure operator of type \(C\). This is a joint work with Ricardo Mamede.

Inês Legatheaux Martins (CELC - Universidade de Lisboa, Portugal)

A meeting point between matroid and representation theory

Abstract:

In this talk, we introduce a matroid invariant known as the rank partition which was defined by J. A. Dias da Silva in 1990. For matroids realizable over the complex numbers, following recent work of A. Berget, we explain how this concept relates matroid theory to the representation theory of the complex general linear group \({\GL}_m(\C)\).

In addition, we present an elegant duality, usually referred to as Schur-Weyl duality, between the representations of \({\GL}_m(\C)\) and those of an algebraic structure called the rook monoid.

The rook monoid is an extension of the symmetric group and thus its representation theory provides a natural context to generalize concepts such as symmetry classes of tensors and symmetrized tensors. We present such generalizations and how they may be applied to obtain new results in matroid theory involving the rank partition.

Wednesday

Mahdi Amani (Università di Pisa, Italy | University of Tehran, Iran)

A new encoding for Generation, Ranking and Unranking of \((k,l)\)-trees and \((k,l)\)-Catalan numbers

Abstract:

Let \(T\) be a tree with root \(r\). For each vertex \(v\) of \(T\), we say that \(v\) is on level \(j\) if the unique path from \(v\) to \(r\) is of length \(j\), and the root is said to be on the level \(0\). We can then define \((k,m)\)-ary tree of order \(n\) as follows: For \(k,m\ge 1\) and \(n\ge 0\), a \((k,m)\)-ary tree of order \(n\) is a tree that:

a) All vertices on even levels have degree \(k\), and
b) All vertices on odd levels have degree \(m\) or \(0\), and there are exactly \(n\) vertices of degree \(m\) [1].

We use \(T_{k,m}(n)\) to denote the set of \((k,m)\)-ary trees of order \(n\). A \((k,m)\)-ary tree, which is also called a \((k,m)\)-Catalan number is a generalization of \(k\)-ary tree [1].

The problem of generation is to propose a linear ordering among the studied trees or using an available one, in order to generate the trees with respect to this ordering. Two such natural orderings are the \(A\)-order and the \(B\)-order [2]. The problem of ranking consists of determining the order number of a given tree and conversely unranking means constructing the tree of a given rank [2].

Generation, ranking and unranking of different classes of trees were studied earlier in the literature, but there is no generation, ranking and unranking algorithms for \(T_{k,m}(n)\). In this work, we use Zaks encoding presented in [3] for representing the \(T_{k,m}(n)\) trees. We use this encoding for generating \(T_{k,m}(n)\) trees in \(A\)-order. Generating algorithm has constant average time and \(O(n)\) time complexity in the worst case. Also, new ranking and unranking algorithms are presented in time complexity of \(O(n)\) and \(O(n \log n)\),respectively.

Henrique Cruz (CELC - Universidade da Beira Interior, Portugal)

On algorithms for constructing \((0,1)\)-matrices with prescribed row and column sum vectors

Abstract:

Given partitions \(R\) and \(S\) with the same weight and \(S\preceq R^*\) let \({\cal A}(R,S)\) be the class of the \((0,1)\)-matrices with row sum \(R\) and column sum \(S\). These matrices play an active role in modern mathematics and the applications extend from their natural context (Matrix Theory, Combinatorics or Graph Theory) to many other areas of knowledge. The Robinson-Schensted-Knuth correspondence establishes a bijection between the class \({\cal A}(R,S)\) and pairs of Young tableaux with conjugate shape \(\lambda\) and \(\lambda^*\) with \(S\preceq \lambda\preceq R^*\). We give a canonical construction for matrices in \({\cal A}(R,S)\) whose insertion tableau has a prescribed shape (\lambda\), with \(S\preceq \lambda\preceq R^*\). This algorithm generalizes some recent constructions due to R. Brualdi for the extremal cases \(\lambda =S\) and \(\lambda =R^*\).

Maria Elisa Fernandes (CIDMA - Universidade de Aveiro, Portugal)

Polytopes of high rank for symmetric and alternating groups

Abstract:

There exists only one polytope with automorphism group \({Sym}(n)\) of rank \(n-1\) for \(n>6\), that is the symplicial complex. We show that when \(n>7\) there is also a unique polytope of rank \(n-2\), up to duality and isomorphism.

For the alternating group, we show that for \(n>11\), \({Alt}(n)\) acts on at least one abstract regular polytope of rank equal to the floor of \((n-1)/2\). We conjecture that this is the highest possible rank. In this talk we show the work done in order to prove this conjecture.

Posters

Mahdi Amani (Università di Pisa, Italy | University of Tehran, Iran)

A new encoding for efficient Generation, Ranking and Unranking of trees with \(n\) nodes and \(m\) leaves

Abstract:

Trees with \(n\) nodes and \(m\) leaves represents the \(2^{nd}\) structure of RNAs, which is an object of research in Bioinformatics and Combinatorics [1].

The problem of generation is proposing a linear ordering among the studied trees or using an available ordering; then generating the trees with respect of this ordering. Rank of a tree is its position in the exhaustive generated list. Unranking is, as usual, the inverse of ranking.

Generation, ranking and unranking of different classes of trees were studied earlier in the literature, but the problem of generation, ranking and unranking of trees with \(n\) nodes and \(m\) leaves has been studied only by Pallor in [2]. He generalized a coding of binary trees (introduced in a previous work) to regular \(k\)-ary trees. This coding is used in order to generate all the trees with \(n\) nodes and \(m\) leaves as a list, by embedding them in a set of regular \(m\)-ary trees. It is quite challenging to find an encoding without embedding a given tree to a regular \(m\)-ary tree to propose the efficient algorithms.

In this work, a new encoding is introduced for representing the trees with \(n\) nodes and \(m\) leaves. This encoding is used for generating this class of trees in \(A\)-order (an ordering based on global information concerning tree nodes and appear to be a natural ordering of trees) with constant average time and \(O(n)\) time complexity in the worst case. Also new ranking and unranking algorithms are presented in time complexity of \(O(n \log n)\).

References

1. R. Giegerich, B. Voss and M. Rehmsmeier, Abstract shapes of RNA, Nucleic Acids Research 32 (2004), 4843--4851.
2. J. Pallor, Generating trees with n nodes and m leaves, Intern. J. Comput. Math. I 21 (1987), 133--144.

Marcin Jurkiewicz (Gdansk University of Technology, Poland)

The coloring and clique cover problems for triangulations of a polygon and their products

Abstract:

It is well know that triangulations of a polygon can be vertex colored with three colors, however, there seems lack of such results for complements and strong product of triangulations of a polygon. It is interesting to note that such problems have certain applications in information theory, e.g. to determine index codes and Witsenhausen's rates of graphs, which are obtained from polygon triangulations. We present some new results for the above-mentioned problems, for example we give bounds on the chromatic number of the complements of triangulations.

Camilo Sarmiento (Max Planck Institut für Mathematik
in den Naturwissenschaften, Germany)

Estimating Betti numbers of cut ideals from path graphs

Abstract:

A cut ideal is an homogeneous ideal in a polynomial ring which can be associated to any simple graph. We study minimal free resolutions of such ideals for the class of path graphs. By employing basic methods from topological combinatorics, we obtain simple formulas on the number of vertices of a path graph, which bound the Betti numbers of its cut ideal from above. These formulas arise from the enumeration of induced subgraphs of certain incomparability graphs associated to the path graphs. Ongoing work with Samu Potka and Hakan Gueler.

José Agapito Ruiz (CELC - Universidade de Lisboa, Portugal)

A symbolic umbral characterization of Riordan arrays

Abstract:

Riordan arrays are infinite lower triangular complex valued-matrices that have been applied to a wide range of subjects, from Computer Science to Combinatorial Physics, in connection with combinatorial identities, recurrence relations, walk problems, asymptotic approximation and the problem of normal ordering for boson strings, among other relevant topics. The usual way of approaching Riordan arrays is by means of generating functions. I will present a promising alternative characterization of Riordan arrays based on a symbolic renewed approach to umbral calculus. A deep generalization of an Abel's identity for polynomials is a key tool in our symbolic approach.

Schedule

Here is the timetable for the workshop.

Social Dinner

It will take place at restaurant, on Tuesday at 8pm. Here are the menu options you can choose from. You will be asked on Monday to sign up a form letting us know your preferences.

More Information

Sponsors