The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

Maximal continuants and the Fine-Wilf theorem

The following problem was posed by C.A. Nicol: given any finite sequence of positive integers, find the permutation for which the continuant (i.e. the continued fraction denominator) having these entries is maximal, resp. minimal. The extremal arrangements are known for the regular continued fraction expansion. For the singular expansion induced by the backward shift ⌈1/x⌉-1/x the problem is still open in the case of maximal continuants. We present the explicit solutions for sequences with pairwise different entries and for sequences made up of any pair of digits occurring with any given (fixed) multiplicities. Here the arrangements are uniquely described by a certain generalized continued fraction. We derive this from a purely combinatorial result concerning the partial order structure of the set of permutations of a linearly ordered vector. This set has unique extremal elements which provide the desired extremal arrangements. We also prove that the palindromic maximal continuants are in a simple one-to-one correspondence with the Fine and Wilf words with two coprime periods which gives a new analytic and combinatorial characterization of this class of words.     

A constructive proof of Ky Fan's generalization of Tucker's lemma

We present a proof of Ky Fan's combinatorial lemma on labellings of triangulated spheres that differs from earlier proofs in that it is constructive. We slightly generalize the hypotheses of Fan's lemma to allow for triangulations of Sⁿ that contain a flag of hemispheres. As a consequence, we can obtain a constructive proof of Tucker's lemma that holds for a more general class of triangulations than the usual version.     

Topology of dynamical systems in finite groups and number theory

We study and develop a very new object introduced by V.I. Arnold: a monad is a triple consisting of a finite set, a map from that finite set to itself and the monad graph which is the directed graph whose vertices are the elements of the finite set and whose arrows lead each vertex to its image (by the map). We consider the case in which the finite set entering in the monad definition is a finite group G and the map is the Frobenius map, for some k∈Z. We study the Frobenius dynamical system defined by the iteration of the monad fk, and also study the combinatorics and topology (i.e., the discrete invariants) of the monad graph. Our study provides useful information about several structures on the group associated to the monad graph. So, for example, several properties of the quadratic residues of finite commutative groups can be obtained in terms of the graph of the Frobenius monad .     

q-Analogs of some congruences involving Catalan numbers

We present some variations on the Greene–Krammer?s identity which involve q-Catalan numbers. Our method reveals an intriguing analogy between these new identities and some congruences modulo a prime.     

The Farahat-Higman ring of wreath products and Hilbert schemes

We study the structure constants of the class algebra of the wreath products Γ_n associated to an arbitrary finite group Γ with respect to the basis of conjugacy classes. We show that a suitable filtration on gives rise to the graded ring with non-negative integer structure constants independent of n (some of which are computed), which are then encoded in a Farahat-Higman ring . The real conjugacy classes of Γ come to play a distinguished role and are treated in detail in the case when Γ is a subgroup of . The above results provide new insight to the cohomology rings of Hilbert schemes of points on a quasi-projective surface X.     

Variance of the spectral numbers and Newton polygons

Using the theory of the mixed Hodge structure one can define a notion of spectrum of a singularity or of a polynomial. Recently Claus Hertling proposed a conjecture about the variance of the spectrum of a singularity. Alexandru Dimca proposed a similar conjecture on polynomials. Here, we prove these two conjectures in the case of dimension 2 and when the singularity or the polynomial is Newton non-degenerated and commode.     

Cambrian lattices

For an arbitrary finite Coxeter group W, we define the family of Cambrian lattices for W as quotients of the weak order on W with respect to certain lattice congruences. We associate to each Cambrian lattice a complete fan, which we conjecture is the normal fan of a polytope combinatorially isomorphic to the generalized associahedron for W. In types A and B we obtain, by means of a fiber-polytope construction, combinatorial realizations of the Cambrian lattices in terms of triangulations and in terms of permutations. Using this combinatorial information, we prove in types A and B that the Cambrian fans are combinatorially isomorphic to the normal fans of the generalized associahedra and that one of the Cambrian fans is linearly isomorphic to Fomin and Zelevinsky's construction of the normal fan as a “cluster fan.” Our construction does not require a crystallographic Coxeter group and therefore suggests a definition, at least on the level of cellular spheres, of a generalized associahedron for any finite Coxeter group. The Tamari lattice is one of the Cambrian lattices of type A, and two “Tamari” lattices in type B are identified and characterized in terms of signed pattern avoidance. We also show that open intervals in Cambrian lattices are either contractible or homotopy equivalent to spheres.     

Simple arguments on consecutive power residues

By some extremely simple arguments, we point out the following:

(i)

If n is the least positive kth power non-residue modulo a positive integer m, then the greatest number of consecutive kth power residues mod m is smaller than m/n.

(ii)

Let OK be the ring of algebraic integers in a quadratic field with d∈{−1,−2,−3,−7,−11}. Then, for any irreducible π∈OK and positive integer k not relatively prime to , there exists a kth power non-residue ω∈OK modulo π such that .

     

Rank and crank moments for overpartitions

We study two types of crank moments and two types of rank moments for overpartitions. We show that the crank moments and their derivatives, along with certain linear combinations of the rank moments and their derivatives, can be written in terms of quasimodular forms. We then use this fact to prove exact relations involving the moments as well as congruence properties modulo 3, 5, and 7 for some combinatorial functions which may be expressed in terms of the second moments. Finally, we establish a congruence modulo 3 involving one such combinatorial function and the Hurwitz class number H(n).     

Legendre inversions and balanced hypergeometric series identities

By means of Legendre inverse series relations, we prove two terminating balanced hypergeometric series formulae. Their reversals and linear combinations yield several known and new hypergeometric series identities.     

Asymptotic formulas for the diameter of sections of symmetric convex bodies

Sharpening work of the first two authors, for every proportion λ∈(0,1) we provide exact quantitative relations between global parameters of n-dimensional symmetric convex bodies and the diameter of their random ⌊λn⌋-dimensional sections. Using recent results of Gromov and Vershynin, we obtain an “asymptotic formula” for the diameter of random proportional sections.     

Interval stability and interval covering property in finite posets

Given a finite ranked posetP, let (P) be the maximum size of a subset ofP such that no two elements of it belong simultaneously to some interval ofP and let (P) be the minimum number of intervals covering all elements ofP. We say thatP has the strong interval stability property (resp. the strong interval covering property) if for each subposetP induced by consecutive levels ofP, i.e.,P=P _(l)...P _(u), one has (P)=max{|P _(l)|, |P _(u)|} (resp. (P)=max{|P _(l)|, |P _(u)|}).We prove these properties for several classes of posets and discuss some general facts concerning the numbers (P) and (P), e.g., NP-completeness and min-max relations.     

Projective Schur groups of Henselian fields

One of the open questions that has emerged in the study of the projective Schur group of a field F is whether or not is an algebraic relative Brauer group over F, i.e. does there exist an algebraic extension L/F such that ? We show that the same question for the Schur group of a number field has a negative answer. For the projective Schur group, no counterexample is known. In this paper we prove that is an algebraic relative Brauer group for all Henselian valued fields F of equal characteristic whose residue field is a local or global field. For this, we first show how is determined by for an equicharacteristic Henselian field with arbitrary residue field k.     

Stability properties of solutions of linear second order differential equations with random coefficients

The equation

     

Non-divisible cycles on surfaces over local fields

In this paper, we are concerned with the reciprocity map of unramified class field theory for smooth projective surfaces over non-archimedean local fields which do not have potentially good reduction. We will construct two types of smooth projective surfaces whose reciprocity maps modulo positive integers are not injective. The first type is the case where the kernel of the reciprocity map is not divisible. The second is the case where the kernel of the reciprocity map is divisible, but where nevertheless the reciprocity map modulo some integer is not injective.     

The wild kernel of exceptional number fields

For an infinite class of exceptional number fields, F, we prove that a map of Keune from to the 2-Sylow subgroup of the wild kernel of F is an isomorphism, and in all cases we give an upper bound for the kernel and cokernel of this map. We find examples which show that the map is neither injective nor surjective in general.     

The smallest regular polytopes of given rank

An abstract polytope is called regular   if its automorphism group has a single orbit on flags (maximal chains). In this paper, the regular n$n$-polytopes with the smallest number of flags are found, for every rank n>1$n>1$. With a few small exceptions, the smallest regular n$n$-polytopes come from a family of ‘tight’ polytopes with 2⋅4ⁿ⁻¹$2\cdot 4^{n-1}$ flags, one for each n$n$, with Schläfli symbol {4∣4∣?∣4}$\{4\mid 4\mid ?\mid 4\}$. Also with few exceptions, these have both the smallest number of elements, and the smallest number of edges in their Hasse diagram.     

Domb's numbers and Ramanujan-Sato type series for 1/π

In this article, we construct a general series for . We indicate that Ramanujan's -series are all special cases of this general series and we end the paper with a new class of -series. Our work is motivated by series recently discovered by Takeshi Sato.