Restricted <Emphasis Type="Italic">k</Emphasis>-color partitions

We generalize overpartitions to (k, j)-colored partitions: k-colored partitions in which each part size may have at most j colors. We find numerous congruences and other symmetries. We use a wide array of tools to prove our theorems: generating function dissections, modular forms, bijections, and other combinatorial maps. In the process of proving certain congruences, we find results of independent interest on the number of partitions with exactly 2 sizes of part in several arithmetic progressions. We find connections to divisor sums, the Han/Nekrasov–Okounkov hook length formula and a possible approach to finitization, and other topics, suggesting that a rich mine of results is available. We pose several immediate questions and conjectures.     

Binomial transforms and integer partitions into parts of <Emphasis Type="Italic">k</Emphasis> different magnitudes

A relationship between the general linear group of degree n over a finite field and the integer partitions of n into parts of k different magnitudes was investigated recently by the author. In this paper, we use a variation of the classical binomial transform to derive a new connection between partitions into parts of k different magnitudes and another finite classical group, namely the symplectic group Sp. New identities involving the number of partitions of n into parts of k different magnitudes are introduced in this context.     

On the number of derangements and derangements of prime power order of the affine general linear groups

A derangement is a permutation that has no fixed points. In this paper, we are interested in the proportion of derangements of the finite affine general linear groups. We prove a remarkably simple and explicit formula for this proportion. We also give a formula for the proportion of derangements of prime power order. Both formulae rely on a result of independent interest on partitions: we determine the generating function for the partitions with m parts and with the kth largest part not k, for every \(k\in \mathbb {N}\).     

On the subsemiring generated by almost idempotents of a k-regular semiring

An element e of a semiring S with commutative addition is called an almost idempotent if \(e + e^2 = e^2\). Here we characterize the subsemiring \(\langle E(S)\rangle \) generated by the set E(S) of all almost idempotents of a k-regular semiring S with a semilattice additive reduct. If S is a k-regular semiring then \(\langle E(S)\rangle \) is also k-regular. A similar result holds for the completely k-regular semirings, too.     

Representation of normal bands as semigroups of <Emphasis Type="Italic">k</Emphasis>-bi-ideals of a semiring

Here we show that every normal band N can be embedded into the normal band \(\mathcal {B(S)}\) of all k-bi-ideals, the left part \(N/ \mathcal {R}\) of N into the left normal band \(\mathcal {R(S)}\) of all right k-ideals, the right part \(N/ \mathcal {L}\) of N into the right normal band \(\mathcal {L(S)}\) of all left k-ideals, and the greatest semilattice homomorphic image \(N/ \mathcal {J}\) of N into the semilattice of all k-ideals of a same k-regular and intra k-regular semiring S.     

Some inequalities for <Emphasis Type="Italic">k</Emphasis>-colored partition functions

Motivated by a partition inequality of Bessenrodt and Ono, we obtain analogous inequalities for k-colored partition functions \(p_{-k}(n)\) for all \(k\ge 2\). This enables us to extend the k-colored partition function multiplicatively to a function on k-colored partitions and characterize when it has a unique maximum. We conclude with one conjectural inequality that strengthens our results.     

The <Emphasis Type="Italic">m</Emphasis>th Largest and <Emphasis Type="Italic">m</Emphasis>th Smallest Parts of a Partition

The theory of overpartitions is applied to determine formulas for the number of partitions of n where (1) the mth largest part is k and (2) the mth smallest part is k.     

Variations of Landau’s theorem for p-regular and p-singular conjugacy classes

The well-known Landau’s theorem states that, for any positive integer k, there are finitely many isomorphism classes of finite groups with exactly k (conjugacy) classes. We study variations of this theorem for p-regular classes as well as p-singular classes. We prove several results showing that the structure of a finite group is strongly restricted by the number of p-regular classes or the number of p-singular classes of the group. In particular, if G is a finite group with O_p(G) = 1 then |G/F(G)|_p' is bounded in terms of the number of p-regular classes of G. However, it is not possible to prove that there are finitely many groups with no nontrivial normal p-subgroup and kp-regular classes without solving some extremely difficult number-theoretic problems (for instance, we would need to show that the number of Fermat primes is finite).     

Congruences modulo 4 for broken <Emphasis Type="Italic">k</Emphasis>-diamond partitions

The notion of broken k-diamond partitions was introduced by Andrews and Paule. Let \(\Delta _k(n)\) denote the number of broken k-diamond partitions of n for a fixed positive integer k. Recently, a number of parity results satisfied by \(\Delta _k(n)\) for small values of k have been proved by Radu and Sellers and others. However, congruences modulo 4 for \(\Delta _k(n)\) are unknown. In this paper, we will prove five congruences modulo 4 for \(\Delta _5(n)\), four infinite families of congruences modulo 4 for \(\Delta _7(n)\) and one congruence modulo 4 for \(\Delta _{11}(n)\) by employing theta function identities. Furthermore, we will prove a new parity result for \(\Delta _2(n)\).     

Degree sequences and edge connectivity

For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\), this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too.     

A Generating Tree Approach to <Emphasis Type="Italic">k</Emphasis>-Nonnesting Partitions and Permutations

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature which uses the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter. Key to the solution is a superset of diagrams that permit semi-arcs. Many of the resulting counting sequences also count other well-known objects, such as Baxter permutations, and Young tableaux of bounded height.     

Abelian Groups With Sufficiently <Emphasis Type="Italic">π</Emphasis>-Regular Endomorphism Ring

The notion of π-regular endomorphism ring of an abelian group, which generalizes the notion of regular endomorphism ring, was introduced in papers of L. Fuchs and K. Rangaswamy. They described periodic abelian groups with π-regular endomorphism ring and found necessary conditions for an abelian group to have π-regular endomorphism ring. In this paper, we study abelian groups with sufficiently π-regular endomorphism ring, which form a subclass of the class of abelian groups with π-regular endomorphism ring, and find necessary and sufficient conditions for an abelian group to have sufficiently π-regular endomorphism ring.     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

Conductors in <Emphasis Type="Italic">p</Emphasis>-adic families

Let the function \(s_g\) map a positive integer to the sum of its digits in the base g. A number k is called n-flimsy in the base g if \(s_g(nk)<s_g(k)\). Clearly, given a base g, \(g\geqslant 2\), if n is a power of g, then there does not exist an n-flimsy number in the base g. We give a constructive proof of the existence of an n-flimsy number in the base g for all the other values of n (such an existence follows from the results of Schmidt and Steiner, but the explicit construction is a novelty). Our algorithm for construction of such a number, say k, is very flexible in the sense that, by easy modifications, we can impose further requirements on k—k ends with a given sequence of digits, k begins with a given sequence of digits, k is divisible by a given number (or belongs to a certain congruence class modulo a given number), etc.     

An improved approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level facility location problem with soft capacities

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u _i along with an initial opening cost f _i ≥ 0, i.e., the capacity of facility i is an integer multiple of u _i incurring a cost equals to the corresponding multiple of f _i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.     

The regular digraph of ideals of a commutative ring

Let R be a commutative ring and Max?(R) be the set of maximal ideals of R. The regular digraph of ideals of R, denoted by \(\overrightarrow{\Gamma_{\mathrm{reg}}}(R)\), is a digraph whose vertex set is the set of all non-trivial ideals of R and for every two distinct vertices I and J, there is an arc from I to J whenever I contains a J-regular element. The undirected regular (simple) graph of ideals of R, denoted by Γ_reg(R), has an edge joining I and J whenever either I contains a J-regular element or J contains an I-regular element. Here, for every Artinian ring R, we prove that |Max?(R)|?1≦ω(Γ_reg(R))≦|Max?(R)| and \(\chi(\Gamma_{\mathrm{ reg}}(R)) = 2|\mathrm{Max}\, (R)| -k-1\), where k is the number of fields, appeared in the decomposition of R to local rings. Among other results, we prove that \(\overrightarrow{\Gamma_{\mathrm{ reg}}}(R)\) is strongly connected if and only if R is an integral domain. Finally, the diameter and the girth of the regular graph of ideals of Artinian rings are determined.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

Largest <Emphasis Type="Italic">H</Emphasis>-eigenvalue of uniform <Emphasis Type="Italic">s</Emphasis>-hypertrees

The k-uniform s-hypertree G = (V,E) is an s-hypergraph, where 1 ≤ s ≤ k - 1; and there exists a host tree T with vertex set V such that each edge of G induces a connected subtree of T. In this paper, some properties of uniform s-hypertrees are establised, as well as the upper and lower bounds on the largest H-eigenvalue of the adjacency tensor of k-uniform s-hypertrees in terms of the maximal degree Δ. Moreover, we also show that the gap between the maximum and the minimum values of the largest H-eigenvalue of k-uniform s-hypertrees is just Θ(Δ ^s/k ).     

Neighborhood Conditions for Fractional ID-<Emphasis Type="Italic">k</Emphasis>-factor-critical Graphs

Let G be a graph and k ≥ 2 a positive integer. Let h: E(G) → [0, 1] be a function. If \(\sum\limits_{e \mathrel\backepsilon x} {h(e) = k} \) holds for each x ∈ V (G), then we call G[F_h] a fractional k-factor of G with indicator function h where F_h = {e ∈ E(G): h(e) > 0}. A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical), if G ? I has a fractional k-factor for every independent set I of G. In this paper, we prove that if n ≥ 9k ? 14 and for any subset X ? V (G) we have

$${N_G}(X) = V(G)if|X| \geqslant \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ;or|{N_G}(X)| \geqslant \frac{{3k - 1}}{k}|X|if|X| < \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ,$$

then G is fractional ID-k-factor-critical.