Search

Leclerc and Zelevinsky described quasicommuting families of quantum minors in terms of a certain combinatorial condition, called weak separation. They conjectured that all inclusion-maximal weakly separated collections of minors have the same cardinality, and that they can be related to each other by a sequence of mutations. Postnikov studied total positivity on the Grassmannian. He described a stratification of the totally non-negative Grassmannian into positroid strata, and constructed theirparameterization using plabic graphs. In this paper, we link the study of weak separation to plabic graphs. We extend the notion of weak separation to positroids. We generalize the conjectures of Leclerc and Zelevinsky, and related ones of Scott, and prove them. We show that the maximal weakly separated collections in a positroid are in bijective correspondence with the plabic graphs. This correspondence allows us to use the combinatorial techniques of positroids and plabic graphs to prove the (generalized) purity and mutation connectedness conjectures., National Science Foundation (U.S.) (CAREER Award DMS-0504629)

Opportunistic Mobile Social Networks (OMSNs), formed by people moving around carrying mobile devices such as smartphones, PDAs, and laptops, have become popular in recent years. The OMSNs we discuss here are a special kind of delay tolerant networks (DTNs) that help enhance spontaneous interaction and communication among users that opportunistically encounter each other, without additional infrastructure support. Multicast is an important routing service in OMSNs which supports the dissemination of messages to a group of users. Most of the existing multicast algorithms are designed for general-purpose DTNs where social factors are neglected or reflected in static social features which are not updated to catch nodes' dynamic contact behavior. In this paper, we introduce the concept of dynamic social features and its enhancement to capture nodes' dynamic contact behavior, consider more social relationships among nodes, and adopt the community structure in the multicast compare-split scheme to select the best relay node for each destination in each hop to improve multicast efficiency. We propose two multicast algorithms based on these new features. The first community and social feature-based multicast algorithm is called Multi-CSDO which involves destination nodes only in community detection, and the second one is called Multi-CSDR which involves both the destination nodes and the relay candidates in community detection. The analysis of the algorithms is given and simulation results using a real trace of an OMSN show that our new algorithms outperform the existing one in terms of delivery rate, latency, and number of forwardings.

We link Schubert varieties in the generalized flag manifolds with hyperplane arrangements. For an element of a Weyl group, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the corresponding Schubert variety if and only if the Schubert variety is rationally smooth., Nous relions des variétés de Schubert dans le variété flag généralisée avec des arrangements des hyperplans. Pour un élément dún groupe de Weyl, nous construisons un certain arrangement graphique des hyperplans. Nous montrons que la fonction génératrice pour les régions de cet arrangement coincide avec le polynome de Poincaré de la variété de Schubert correspondante si et seulement si la variété de Schubert est rationnellement lisse.

Postnikov gave a combinatorial description of the cells in a totally-nonnegative Grassmannian. These cells correspond to a special class of matroids called positroid. We prove his conjecture that a positroid is exactly an intersection of permuted Schubert matroids. This leads to a nice combinatorial description of positroids that is easily computable., Comment: 10 pages, 1 figure. v5 simpler proof with improved writing. Submitted