AbstractFor a character$\chi $of a finite groupG, the number$\chi ^c(1)={[G:{\textrm {ker}}\chi ]}/{\chi (1)}$is called the co-degree of$\chi $. A finite groupGis an${\textrm {NDAC}} $-group (no divisibility among co-degrees) when$\chi ^c(1) \nmid \phi ^c(1)$for all irreducible characters$\chi $and$\phi $ofGwith$1< \chi ^c(1) < \phi ^c(1)$. We study finite groups admitting an irreducible character whose co-degree is a given primepand finite nonsolvable${\textrm {NDAC}} $-groups. Then we show that the finite simple groups$^2B_2(2^{2f+1})$, where$f\geq 1$,$\mbox {PSL}_3(4)$,${\textrm {Alt}}_7$and$J_1$are determined uniquely by the set of their irreducible character co-degrees.
Based on results by Brugallé and Mikhalkin, Fomin and Mikhalkin give formulas for computing classical Severi degrees Nd,δ using long-edge graphs. In 2012, Block, Colley and Kennedy considered the logarithmic versionof a special function associated to long-edge graphs which appeared in Fomin-Mikhalkin’s formula, and conjecturedit to be linear. They have since proved their conjecture. At the same time, motivated by their conjecture, we considera special multivariate function associated to long-edge graphs that generalizes their function. The main result of thispaper is that the multivariate function we define is always linear.The first application of our linearity result is that by applying it to classical Severi degrees, we recover quadraticity of Qd,δ and a bound δ for the threshold of polynomiality ofNd,δ.Next, in joint work with Osserman, we apply thelinearity result to a special family of toric surfaces and obtain universal polynomial results having connections to the Göttsche-Yau-Zaslow formula. As a result, we provide combinatorial formulas for the two unidentified power series B1(q) and B2(q) appearing in the Göttsche-Yau-Zaslow formula.The proof of our linearity result is completely combinatorial. We defineτ-graphs which generalize long-edge graphs,and a closely related family of combinatorial objects we call (τ,n)-words. By introducing height functions and aconcept of irreducibility, we describe ways to decompose certain families of (τ,n)-words into irreducible words,which leads to the desired results.
We prove that the external activity complex Act<(M) of a matroid is shellable. In fact, we show that every linear extension of Las Vergnas's external/internal order <ext/int on M provides a shelling of Act<(M). We also show that every linear extension of Las Vergnas's internal order <int on M provides a shelling of the independence complex IN(M). As a corollary, Act<(M) and M have the same h-vector. We prove that, after removing its cone points, the external activity complex is contractible if M contains U3,1 as a minor, and a sphere otherwise.
In their 1987 paper Kraskiewicz and Pragacz defined certain modules, which we call KP modules, over the upper triangular Lie algebra whose characters are Schubert polynomials. In a previous work the author showed that the tensor product of Kraskiewicz-Pragacz modules always has KP filtration, i.e. a filtration whose each successive quotients are isomorphic to KP modules. In this paper we explicitly construct such filtrations for certain special cases of these tensor product modules, namely Sw Sd(Ki) and Sw Vd(Ki), corresponding to Pieri and dual Pieri rules for Schubert polynomials.
We show that an element $\mathcal{w}$ of a finite Weyl group W is rationally smooth if and only if the hyperplane arrangement $\mathcal{I} (\mathcal{w})$ associated to the inversion set of \mathcal{w} is inductively free, and the product $(d_1+1) ...(d_l+1)$ of the coexponents $d_1,\ldots,d_l$ is equal to the size of the Bruhat interval [e,w]. We also use Peterson translation of coconvex sets to give a Shapiro-Steinberg-Kostant rule for the exponents of $\mathcal{w}$.
Federico Ardila, Federico Castillo, Michael Henley
Many combinatorial and topological invariants of a hyperplane arrangement can be computed in terms of its Tutte polynomial. Similarly, many invariants of a hypertoric arrangement can be computed in terms of its <i>arithmetic</i> Tutte polynomial. We compute the arithmetic Tutte polynomials of the classical root systems $A_n, B_n, C_n$, and $D_n$ with respect to their integer, root, and weight lattices. We do it in two ways: by introducing a \emphfinite field method for arithmetic Tutte polynomials, and by enumerating signed graphs with respect to six parameters.
Extending an idea of Suppakitpaisarn, Edahiro and Imai, a dynamic programming approach for computing digital expansions of minimal weight is transformed into an asymptotic analysis of minimal weight expansions. The minimal weight of an optimal expansion of a random input of length $\ell$ is shown to be asymptotically normally distributed under suitable conditions. After discussing the general framework, we focus on expansions to the base of $\tau$, where $\tau$ is a root of the polynomial $X^2- \mu X + 2$ for $\mu \in \{ \pm 1\}$. As the Frobenius endomorphism on a binary Koblitz curve fulfils the same equation, digit expansions to the base of this $\tau$ can be used for scalar multiplication and linear combination in elliptic curve cryptosystems over these curves.
We continue a study of the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order. For each possible set of allowed replacements, we characterise and/or enumerate the set of permutations reachable from the identity. In some cases we also count the number of equivalence classes.
We study the Gilbert-Shannon-Reeds model for riffle shuffles and ask 'How many times must a deck of cards be shuffled for the deck to be in close to random order?'. In 1992, Bayer and Diaconis gave a solution which gives exact and asymptotic results for all decks of practical interest, e.g. a deck of 52 cards. But what if one only cares about the colors of the cards or disregards the suits focusing solely on the ranks? More generally, how does the rate of convergence of a Markov chain change if we are interested in only certain features? Our exploration of this problem takes us through random walks on groups and their cosets, discovering along the way exact formulas leading to interesting combinatorics, an 'amazing matrix', and new analytic methods which produce a completely general asymptotic solution that is remarkable accurate.
We refine the classical Littlewood-Richardson rule in several different settings. We begin with a combinatorial rule for the product of a Demazure atom and a Schur function. Building on this, we also describe the product of a quasisymmetric Schur function and a Schur function as a positive sum of quasisymmetric Schur functions. Finally, we provide a combinatorial formula for the product of a Demazure character and a Schur function as a positive sum of Demazure characters. This last rule implies the classical Littlewood-Richardson rule for the multiplication of two Schur functions.
In this paper, we study the distribution of distances in random Apollonian network structures (RANS), a family of graphs which has a one-to-one correspondence with planar ternary trees. Using multivariate generating functions that express all information on distances, and singularity analysis for evaluating the coefficients of these functions, we prove a Rayleigh limit distribution for distances to an outermost vertex, and show that the average value of the distance between any pair of vertices in a RANS of order $n$ is asymptotically $\sqrt{n}$.
Boltzmann random generation applies to well-defined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.
The minimal length of a plateau (a sequence of horizontal steps, preceded by an up- and followed by a down-step) in a Motzkin path is known to be of interest in the study of secondary structures which in turn appear in mathematical biology. We will treat this and the related parameters <i> maximal plateau length, horizontal segment </i>and <i>maximal horizontal segment </i>as well as some similar parameters in unary-binary trees by a pure generating functions approach―-Motzkin paths are derived from Dyck paths by a substitution process. Furthermore, we provide a pretty general analytic method to obtain means and limiting distributions for these parameters. It turns out that the maximal plateau and the maximal horizontal segment follow a Gumbel distribution.
Message passing algorithms are popular in many combinatorial optimization problems. For example, experimental results show that \emphsurvey propagation (a certain message passing algorithm) is effective in finding proper k-colorings of random graphs in the near-threshold regime. In 1962 Gallager introduced the concept of Low Density Parity Check (LDPC) codes, and suggested a simple decoding algorithm based on message passing. In 1994 Alon and Kahale exhibited a coloring algorithm and proved its usefulness for finding a k-coloring of graphs drawn from a certain planted-solution distribution over k-colorable graphs. In this work we show an interpretation of Alon and Kahale's coloring algorithm in light of Gallager's decoding algorithm, thus showing a connection between the two problems - coloring and decoding. This also provides a rigorous evidence for the usefulness of the message passing paradigm for the graph coloring problem.
This work is devoted to the understanding of properties of random graphs from graph classes with structural constraints. We propose a method that is based on the analysis of the behaviour of Boltzmann sampler algorithms, and may be used to obtain precise estimates for the maximum degree and maximum size of a biconnected block of a "typical'' member of the class in question. We illustrate how our method works on several graph classes, namely dissections and triangulations of convex polygons, embedded trees, and block and cactus graphs.