Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.     

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.     

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).     

Multiplicative Properties of the Number of <Emphasis Type="Italic">k</Emphasis>-Regular Partitions

In a previous paper of the second author with K. Ono, surprising multiplicative properties of the partition function were presented. Here, we deal with k-regular partitions. Extending the generating function for k-regular partitions multiplicatively to a function on k-regular partitions, we show that it takes its maximum at an explicitly described small set of partitions, and can thus easily be computed. The basis for this is an extension of a classical result of Lehmer, from which an inequality for the generating function for k-regular partitions is deduced which seems not to have been noticed before.     

Effect Algebras as Presheaves on Finite Boolean Algebras

For an effect algebra A, we examine the category of all morphisms from finite Boolean algebras into A. This category can be described as a category of elements of a presheaf R(A) on the category of finite Boolean algebras. We prove that some properties (being an orthoalgebra, the Riesz decomposition property, being a Boolean algebra) of an effect algebra A can be characterized in terms of some properties of the category of elements of the presheaf R(A). We prove that the tensor product of effect algebras arises as a left Kan extension of the free product of finite Boolean algebras along the inclusion functor. The tensor product of effect algebras can be expressed by means of the Day convolution of presheaves on finite Boolean algebras.     

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.     

ABELIAN BALANCED HERMITIAN STRUCTURES ON UNIMODULAR LIE ALGEBRAS

Let g be a 2n-dimensional unimodular Lie algebra equipped with a Hermitian structure (J; F) such that the complex structure J is abelian and the fundamental form F is balanced. We prove that the holonomy group of the associated Bismut connection reduces to a subgroup of SU(n – k), being 2k the dimension of the center of g. We determine conditions that allow a unimodular Lie algebra to admit this particular type of structures. Moreover, we give methods to construct them in arbitrary dimensions and classify them if the Lie algebra is 8-dimensional and nilpotent.     

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.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Super Jack-Laurent Polynomials

Let \(\mathcal {D}_{n,m}\) be the algebra of quantum integrals of the deformed Calogero-Moser-Sutherland problem corresponding to the root system of the Lie superalgebra \(\frak {gl}(n,m)\). The algebra \(\mathcal {D}_{n,m}\) acts naturally on the quasi-invariant Laurent polynomials and we investigate the corresponding spectral decomposition. Even for general value of the parameter k the spectral decomposition is not multiplicity free and we prove that the image of the algebra \(\mathcal {D}_{n,m}\) in the algebra of endomorphisms of the generalised eigenspace is k[ε]^?r where k[ε] is the algebra of dual numbers. The corresponding representation is the regular representation of the algebra k[ε]^?r.     

<Emphasis Type="Italic">C</Emphasis>*-simplicity of <Emphasis Type="Italic">n</Emphasis>-periodic products

The C*-simplicity of n-periodic products is proved for a large class of groups. In particular, the n-periodic products of any finite or cyclic groups (including the free Burnside groups) are C*-simple. Continuum-many nonisomorphic 3-generated nonsimple C*-simple groups are constructed in each of which the identity xⁿ = 1 holds, where n ≥ 1003 is any odd number. The problem of the existence of C*-simple groups without free subgroups of rank 2 was posed by de la Harpe in 2007.     

Maximal number of Boolean functions realized by an initial Boolean automaton with two constant states

The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of set of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with two constant states and n inputs is obtained.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.     

Weighted Rogers–Ramanujan partitions and Dyson crank

In this paper, we refine a weighted partition identity of Alladi. We write formulas for generating functions for the number of partitions grouped with respect to a partition statistic other than the norm. We tie our weighted results as well as the different statistics with the crank of a partition. In particular, we prove that the number of partitions into even number of distinct parts whose odd-indexed parts’ sum is n is equal to the number of partitions of n with non-negative crank.     

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.     

Asymptotic analysis of expectations of plane partition statistics

Assuming that a plane partition of the positive integer n is chosen uniformly at random from the set of all such partitions, we propose a general asymptotic scheme for the computation of expectations of various plane partition statistics as n becomes large. The generating functions that arise in this study are of the form Q(x)F(x), where \(Q(x)=\prod _{j=1}^\infty (1-x^j)^{-j}\) is the generating function for the number of plane partitions. We show how asymptotics of such expectations can be obtained directly from the asymptotic expansion of the function F(x) around \(x=1\). The representation of a plane partition as a solid diagram of volume n allows interpretations of these statistics in terms of its dimensions and shape. As an application of our main result, we obtain the asymptotic behavior of the expected values of the largest part, the number of columns, the number of rows (that is, the three dimensions of the solid diagram) and the trace (the number of cubes in the wall on the main diagonal of the solid diagram). Our results are similar to those of Grabner et al. (Comb Probab Comput 23:1057–1086, 2014) related to linear integer partition statistics. We base our study on the Hayman’s method for admissible power series.     

Dyson’s partition ranks and their multiplicative extensions

We study the Dyson rank function N(r, 3; n), the number of partitions of n with rank \(\equiv r \pmod 3\). We investigate the convexity of these functions. We extend N(r, 3; n) multiplicatively to the set of partitions, and we determine the maximum value when taken over all partitions of size n.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.