AbstractWe deal with the problem of existence of uncountable co-Hopfian abelian groups and (absolute) Hopfian abelian groups. Firstly, we prove that there are no co-Hopfian reduced abelian groups G of size < p with infinite Torp(G), and that in particular there are no infinite reduced abelian p-groups of size < p. Secondly, we prove that if $${2^{{\aleph _0}}} < \lambda < {\lambda ^{{\aleph _0}}}$$ 2 ℵ 0 < λ < λ ℵ 0 , and G is abelian of size λ, then G is not co-Hopfian. Finally, we prove that for every cardinal λ there is a torsion-free abelian group G of size λ which is absolutely Hopfian, i.e., G is Hopfian and G remains Hopfian in every forcing extension of the universe.
An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs.
Let v be a grid path made of north and east steps. The lattice TAM(v), based on all grid paths weakly above the grid path v sharing the same endpoints as v, was introduced by Pre ́ville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case v = (NE)n. They showed that TAM(v) is isomorphic to the dual of TAM(←−v ), where ←−v is the reverse of v with N and E exchanged. Our main contribution is a bijection from intervals in TAM(v) to non-separable planar maps. It follows that the number of intervals in TAM(v) over all v of length n is 2(3n+3)! (n+2)!(2n+3)! . This formula was first obtained by Tutte(1963) for non-separable planar maps.
The consecutive pattern poset is the infinite partially ordered set of all permutations where σ ≤ τ if τ has a subsequence of adjacent entries in the same relative order as the entries of σ. We study the structure of the intervals in this poset from topological, poset-theoretic, and enumerative perspectives. In particular, we prove that all intervals are rank-unimodal and strongly Sperner, and we characterize disconnected and shellable intervals. We also show that most intervals are not shellable and have Mo ̈bius function equal to zero.
We construct the affine version of the Fomin-Kirillov algebra, called the affine FK algebra, to investigatethe combinatorics of affine Schubert calculus for typeA. We introduce Murnaghan-Nakayama elements and Dunklelements in the affine FK algebra. We show that they are commutative as Bruhat operators, and the commutativealgebra generated by these operators is isomorphic to the cohomology of the affine flag variety. As a byproduct, weobtain Murnaghan-Nakayama rules both for the affine Schubert polynomials and affine Stanley symmetric functions. This enable us to expressk-Schur functions in terms of power sum symmetric functions. We also provide the defi-nition of the affine Schubert polynomials, polynomial representatives of the Schubert basis in the cohomology of theaffine flag variety.
In this work triangular puzzles that are composed of unit triangles with labelled edges are considered. To be more precise, the labelled unit triangles that we allow are on the one hand the puzzle pieces that compute Schubert calculus and on the other hand the flipped K-theory puzzle piece. The motivation for studying such puzzles comes from the fact that they correspond to a class of oriented triangular fully packed loop configurations. The main result that is presented is an expression for the number of these puzzles with a fixed boundary in terms of Littlewood- Richardson coefficients.
The family of generalized Petersen graphs $G(n,k)$, introduced by Coxeter et al. [4] and named by Mark Watkins (1969), is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover $KC(G)$ of a simple undirected graph $G$ is a a special type of bipartite covering graph of $G$, isomorphic to the direct (tensor) product of $G$ and $K_2$. We characterize all the members of generalized Petersen graphs that are Kronecker covers, and describe the structure of their respective quotients. We observe that some of such quotients are again generalized Petersen graphs, and describe all such pairs.The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published elsewhere.
\textbfAbstract. We construct supercharacter theories of finite unipotent groups in the orthogonal, symplectic and unitary types. Our method utilizes group actions in a manner analogous to that of Diaconis and Isaacs in their construction of supercharacters of algebra groups. The resulting supercharacter theories agree with those of André and Neto in the case of the unipotent orthogonal and symplectic matrices and generalize to a large collection of subgroups. In the unitary group case, we describe the supercharacters and superclasses in terms of labeled set partitions and calculate the supercharacter table. \bigbreak
Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler
Any continuous map of an $N$-dimensional simplex $Δ _N$ with colored vertices to a $d$-dimensional manifold $M$ must map $r$ points from disjoint rainbow faces of $Δ _N$ to the same point in $M$, assuming that $N≥(r-1)(d+1)$, no $r$ vertices of $Δ _N$ get the same color, and our proof needs that $r$ is a prime. A face of $Δ _N$ is called a rainbow face if all vertices have different colors. This result is an extension of our recent "new colored Tverberg theorem'', the special case of $M=ℝ^d$. It is also a generalization of Volovikov's 1996 topological Tverberg theorem for maps to manifolds, which arises when all color classes have size 1 (i.e., without color constraints); for this special case Volovikov's proofs, as well as ours, work when r is a prime power.
Gantert and Müller (2006) proved that a critical branching random walk (BRW) on the integer lattice is transient by analyzing this problem within the more general framework of branching Markov chains and making use of Lyapunov functions. The main purpose of this note is to show how the same result can be derived quite elegantly and even extended to the nonlattice case within the theory of weighted branching processes. This is done by an analysis of certain associated random weighted location measures which, upon taking expectations, provide a useful connection to the well established theory of ordinary random walks with i.i.d. increments. A brief discussion of the asymptotic behavior of the left- and rightmost particles in a critical BRW as time goes to infinity is provided in the final section by drawing on recent work by Hu and Shi (2008).
Frédérique Bassino, Julien Clément, Julien Fayolle
et al.
We consider a component of the word statistics known as clump; starting from a finite set of words, clumps are maximal overlapping sets of these occurrences. This object has first been studied by Schbath with the aim of counting the number of occurrences of words in random texts. Later work with similar probabilistic approach used the Chen-Stein approximation for a compound Poisson distribution, where the number of clumps follows a law close to Poisson. Presently there is no combinatorial counterpart to this approach, and we fill the gap here. We also provide a construction for the yet unsolved problem of clumps of an arbitrary finite set of words. In contrast with the probabilistic approach which only provides asymptotic results, the combinatorial method provides exact results that are useful when considering short sequences.
Severini and Mansour introduced $\textit{square polygons}$, as graphical representations of $\textit{square permutations}$, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.
We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity. We significantly reduce the complexity of the earlier algorithm. Also one particular perpetuity arising in the analysis of the selection algorithm Quickselect is studied in more detail. Our approach works well for distribution functions. For densities we have weaker error bounds although computer experiments indicate that densities can also be well approximated.
One-sided variations on path length in a trie (a sort of digital trees) are investigated: They include imbalance factors, climbing under different strategies, and key sampling. For the imbalance factor accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissonization and the Mellin transform, and the inverse of the two operations. It is also shown from an analysis of the moving poles of the Mellin transform of the poissonized moment generating function that the imbalance factor (under appropriate centering and scaling) follows a Gaussian limit law. The method extends to several variations of sampling keys from a trie and we sketch results of climbing under different strategies. The exact probability distribution is computed in one case, to demonstrate that such calculations can be done, at least in principle.
AbstractLet G be a finite group. By a Moore G-space we mean a G-space X such that for each subgroup H of G the fixed point space XH is a simply connected Moore space of type (MH,n), where MH is an abelian group depending on H, and n is a fixed integer. By a co-Hopf G-space we mean a G-space with a G-equivariant comultiplication. In this note it is shown that, in contrast to the non-equivariant case, there exist Moore G-spaces which are not co-Hopf G-spaces.