KAIST Discrete Math Seminar

It is well known that the the central objects in the theory of symmetric functions, Schur functions, are generating functions of semistandard Young tableaux. We present a collection of generalizations of semistandard tableaux. The generating functions of these tableaux are symmetric functions occurring in the study of the (co)homology of the affine Grassmannian, and the K-(co)homology of the Grassmanian.

For a labeled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij as i to j if i<j. The indegree sequence λ=1^e₁2^e₂ … is then a partition of n-1. Let a_λ be the number of trees on [n] with indegree sequence λ. In a recent paper (arXiv:0706.2049v2) Cotterill stumbled across the following remarkable formulas  where k = Σ_i e_i. In this talk, we first construct a bijection from (unrooted) trees to rooted trees which preserves the indegree sequence. As a consequence, we obtain a bijective proof of the formula. This is a joint work with Jiang Zeng.</div>

Equational reasoning is fundamental in automated theorem proving (that is, the proving of mathematical theorems by a computer program), and rewriting is a powerful method for equational reasoning. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them.

Using category theory, we have developed a framework for equational reasoning. A Term Equational System (TES) is given by a semantic universe and an abstract notion of syntax; and given this, we automatically derive a sound logical deduction system, called Term Equational Logic (TEL). Furthermore, we provide an algebraic free construction for the system, which may be used to synthesize a sound and complete rewriting system for it.

Existing systems arising in this framework include:

• first-order equational logic and rewriting system;
• combinatory reduction system of Klop;
• binding equational logic and rewriting system of Hamana; and
• nominal equational logics independently developed by Gabbay and Matheijssen, and Clouston and Pitts.

 

Especially, following the above scenario in our framework, we have newly developed a sound and complete rewriting system for nominal equational logic.

In this talk, rather than going into the technical details, I will focus on explaining basic ideas of category theory and how it can be used in practice.

This is joint work with Marcelo Fiore.

The Euler number E_n counts the number of alternating permutations on the set [n]. It is well known that its exponential generating function equals Tan z + Sec z. For this reason, E_2n and E_2n+1 are called secant numbers and tangent numbers, respectively. Certain polynomials arising in series expansions for zeros of generalized Rogers-Ramanujan functions provide a q-analog of the tangent numbers, which is part of a wider class of polynomials with similar combinatorial interpretations. In this talk, we will discuss various q-Euler numbers. This is a joint work with Tim Huber from Iowa State University.</div>

We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.

For a given unknown weighted graph G with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of G using O((m log n)/log m) queries of both types provided that m≤ n^ε for any constant ε>0. For a graph, it is shown that the same bound holds for all range of m.

This settles a conjecture of Grebinski for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered. (Joint work with S. Choi)