共查询到20条相似文献,搜索用时 15 毫秒
1.
In 2009, Kyaw proved that every -vertex connected -free graph with contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected -free graphs. We show that every -vertex connected -free graph with contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “” is best possible. 相似文献
2.
3.
Let be an array of nonnegative numbers satisfying the recurrence relation with and unless . In this paper, we first prove that the array can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of . Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type , and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong -log-convexity of some generating functions. 相似文献
4.
Natalie C. Behague 《Discrete Mathematics》2019,342(6):1696-1702
5.
In this article, we study the structure of finitely ramified mixed characteristic valued fields. For any two complete discrete valued fields and of mixed characteristic with perfect residue fields, we show that if the n-th residue rings are isomorphic for each , then and are isometric and isomorphic. More generally, for , there is depending only on the ramification indices of and such that any homomorphism from the -th residue ring of to the -th residue ring of can be lifted to a homomorphism between the valuation rings. Moreover, we get a functor from the category of certain principal Artinian local rings of length n to the category of certain complete discrete valuation rings of mixed characteristic with perfect residue fields, which naturally generalizes the functorial property of unramified complete discrete valuation rings. Our lifting result improves Basarab's relative completeness theorem for finitely ramified henselian valued fields, which solves a question posed by Basarab, in the case of perfect residue fields. 相似文献
6.
《Discrete Mathematics》2022,345(9):112945
The coinvariant algebra is a quotient of the polynomial ring whose algebraic properties are governed by the combinatorics of permutations of length n. A word over the positive integers is packed if whenever appears as a letter of w, so does . We introduce a quotient of which is governed by the combinatorics of packed words. We relate our quotient to the generalized coinvariant rings of Haglund, Rhoades, and Shimozono as well as the superspace coinvariant ring. 相似文献
7.
《Discrete Mathematics》2019,342(5):1275-1292
A discrete function of variables is a mapping , where , and are arbitrary finite sets. Function is called separable if there exist functions for , such that for every input the function takes one of the values . Given a discrete function , it is an interesting problem to ask whether is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of variables is known only for . In this paper we will show that a slightly more general recognition problem, when is not fully but only partially defined, is NP-complete for . We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for .The general recognition problem contains the above mentioned special case for . This case is well-studied in the context of game theory, where (separable) discrete functions of variables are referred to as (assignable) -person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of variables for any , thus generalizing the above result known for . Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function of variables one can construct separating functions in polynomial time with respect to the size of the input function. 相似文献
8.
Ion Grama Ronan Lauvergnat Émile Le Page 《Stochastic Processes and their Applications》2019,129(7):2485-2527
Let be a branching process in a random environment defined by a Markov chain with values in a finite state space . Let be the probability law generated by the trajectories of starting at We study the asymptotic behaviour of the joint survival probability , as in the critical and strongly, intermediate and weakly subcritical cases. 相似文献
9.
10.
《Journal of Pure and Applied Algebra》2023,227(1):107146
For a commutative ring R and an ADE Dynkin quiver Q, we prove that the multiplicative preprojective algebra of Crawley-Boevey and Shaw, with parameter , is isomorphic to the (additive) preprojective algebra as R-algebras if and only if the bad primes for Q – 2 in type D, 2 and 3 for , and 2, 3 and 5 for – are invertible in R. We construct an explicit isomorphism over in type D, over for , and over for . Conversely, if some bad prime is not invertible in R, we show that the additive and multiplicative preprojective algebras differ in zeroth Hochschild homology, and hence are not isomorphic. In fact, one only needs the vanishing of certain classes in zeroth Hochschild homology of the multiplicative preprojective algebra, utilizing a rigidification argument for isomorphisms that may be of independent interest.In the setting of Ginzburg dg-algebras, our obstructions are new in type E and give a more elementary proof of the negative result of Etgü–Lekili [5, Theorem 13] in type D. Moreover, the zeroth Hochschild homology of the multiplicative preprojective algebra, computed in Section 4, can be interpreted as the space of unobstructed deformations of the multiplicative Ginzburg dg-algebra by Van den Bergh duality. Finally, we observe that the multiplicative preprojective algebra is not symmetric Frobenius if , a departure from the additive preprojective algebra in characteristic 2 for , and , . 相似文献
11.
For given graphs , , the -color Ramsey number, denoted by , is the smallest integer such that if we arbitrarily color the edges of a complete graph of order with colors, then it always contains a monochromatic copy of colored with , for some . Let be a cycle of length and a star of order . In this paper, firstly we give a general upper bound of . In particular, for the 3-color case, we have and this bound is tight in some sense. Furthermore, we prove that for all and , and if is a prime power, then the equality holds. 相似文献
12.
《Discrete Mathematics》2022,345(9):112977
Consider functions , where A and C are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let and . When a function is chosen from all possibilities uniformly at random, then we find the following limiting behaviour as . If , then the size of the maximal mapping component goes to infinity almost surely; if , a constant, then process counting numbers of mapping components of different sizes converges; if , then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order when and constant when , . These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees. 相似文献
13.
14.
15.
《Stochastic Processes and their Applications》2020,130(4):2127-2158
Let be an ergodic diffusion with invariant distribution . Consider the empirical measure where is an Euler scheme with decreasing steps which approximates . Given a test function , we obtain sharp concentration inequalities for which improve the results in Honoré et al. (2019). Our hypotheses on the test function cover many real applications: either is supposed to be a coboundary of the infinitesimal generator of the diffusion, or is supposed to be Lipschitz. 相似文献
16.
The Erd?s–Gallai Theorem states that every graph of average degree more than contains a path of order for . In this paper, we obtain a stability version of the Erd?s–Gallai Theorem in terms of minimum degree. Let be a connected graph of order and be disjoint paths of order respectively, where , , and . If the minimum degree , then except several classes of graphs for sufficiently large , which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path. 相似文献
17.
18.
20.
《Discrete Mathematics》2022,345(11):113059
Let be the finite field of q elements and let be the dihedral group of 2n elements. Left ideals of the group algebra are known as left dihedral codes over of length 2n, and abbreviated as left -codes. Let . In this paper, we give an explicit representation for the Euclidean hull of every left -code over . On this basis, we determine all distinct Euclidean LCD codes and Euclidean self-orthogonal codes which are left -codes over . In particular, we provide an explicit representation and a precise enumeration for these two subclasses of left -codes and self-dual left -codes, respectively. Moreover, we give a direct and simple method for determining the encoder (generator matrix) of any left -code over , and present several numerical examples to illustrative our applications. 相似文献