Narrow Results

Let $M_0(n)$ (resp. $M_1(n)$) denote the number of partitions of $n$ with even (resp. odd) crank. Choi, Kang and Lovejoy established an asymptotic formula for $M_0(n)-M_1(n)$. By utilizing this formula with the explicit bound, we show that $M_k(n-1)+M_k(n+1)>2M_k(n)$ for $k=0$ or $1$ and $n\ge 39$. This result can be seen as the refinement of the classical result regarding the convexity of the partition function $p(n)$, which counts the number of partitions of $n$. We also show that $M_0(n)$ (resp. $M_1(n)$) is log-concave for $n\ge 94$ and satisfies the higher order Turán inequalities for $n\ge 207$ with the aid of the upper bound and the lower bound for $M_0(n)$ and $M_1(n)$.

Given an undirected graph $G$ and a real edge-weight vector, the connected subgraph problem consists of finding a maximum-weight subset of edges which induces a connected subgraph of $G$. In this paper, we establish a link between the complexity of the connected subgraph problem and the matching number. We study the separation problem associated with the so-called matching-partition inequalities, which were introduced by Didi Biha, Kerivin and Ng [Polyhedral study of the connected subgraph problem, Discr. Math.338 (2015) 80–92] for the connected subgraph polytope.

The inverted weak Schur number $Ŝ(k,n)$ refers to the smallest positive integer $N$ such that any $n$-coloring of $\{1,2,\dots ,N\}$ inevitably contains a solution to the equation:

A representation for a set is defined to be symmetric if the space required for the representation of the set is the same as the space required for representation of the set's complement. The use of symmetric representation is shown to be important when studying the time complexity of algorithms. A symmetric data structure called a flip list is defined, and it is employed for the Clique, Independent Set, and Vertex Cover problems in a case study. The classic reductions among these problems require the complement of either a graph's edge set or a subset of its vertices. Flip lists can be complemented in constant time with no increase in space. When a flip list is used to represent the edge set of a graph, Clique, Independent Set, and Vertex Cover are shown to have identical (and strongly exponential) time complexity when the classical complexity parameter of input length is used. On the other hand, when a flip list is used to represent a set of numbers as input for the Partition problem, an algorithm can be built that retains strongly sub-exponential time complexity. This provides new evidence with respect to which NP- complete problems should be classified as sub-exponential. Symmetric representation has the advantage of space efficiency, at most linear-time and space complement operations, and symmetry in representing sparse and dense sets. These features can have a significant impact on complexity studies.

To study the data association, a structure called a hierarchy tree is constructed. It is based on the approach to hierarchical data processing, and constituted by different level partitions of a data set. This leads to the definition of the data association, thereby links two hierarchy trees together. The research on the data association focuses on the way to check whether data are associated with other data. The investigation includes the issues: the intuitive and formal methods for constructing hierarchy trees, the technique of making granules hierarchical, the sufficient and necessary condition for measuring the data association, the analysis of basing the closer data association on the closer data identity, the discussion of connecting numerical information with association closeness, etc. Crucially, the hierarchical data processing and numerical information are important characteristics of the research. As an applied example, two hierarchy trees are set up, demonstrating the hierarchical granulation process of two actual data sets. Data associations between the data sets are characterized by the approach developed in this paper, which provides the basis of algorithm design for the actual problem. In particular, since the research is relevant to granules and alterations of granularity, it may offer an avenue of research on granular computing.

The d–dimensional k-ary array is the d–fold Cartesian product graph of the path graph P_k with k vertices. We show that the (edge) isoperimetric number of is given by and identify the cardinalities and the structure of the isoperimetric sets. For odd k, the cardinalities of isoperimetric sets in are , whereas every isoperimetric set for k even has cardinality .

This paper uses set theory to analyze cellular manufacturing systems. We develop a structural architecture to investigate the previous literature. We divide all research problems into three types — what, why, and how. We advocate studying these three types of problems from two managerial perspectives — philosophy and science. To fully and deeply understand cellular manufacturing, both three-problems and two-perspectives are important. We use the developed architecture to review cellular manufacturing literature and point out the weakness in the previous studies. This review motivates the research of this paper. We use simple but rigorous set theory to analyze two what-problems. Underlying concepts, such as part family, machine cell, cellular manufacturing system, bottleneck machine are defined. Following these definitions, we deduce sufficient and necessary conditions for perfectly partitioned cellular manufacturing systems. Two sufficient and necessary conditions of perfect partition have been discovered — prior perfect partition theorems check the potential independent manufacturing cells within an arbitrary manufacturing system; in contrast, posterior perfect partition theorem verifies a perfectly partitioned cellular manufacturing system. To our knowledge, we are among the first to apply rigorous mathematical models to these two types of what-problems for cellular manufacturing. We try to provide mathematical vocabularies to discuss common problems inherent in the design of cellular manufacturing systems.

In RFID systems, many anti-collision algorithms, driven by the concept of rescheduling the response sequence between the reader and unidentified tags, have been put forward to solve tag collision problem, including ALOHA-based, tree-based and hybrid algorithms. In this paper, we propose a novel RFID anti-collision algorithm called EAQ-CBB, which adopts three main approaches: tag population estimation based on collided bit detection method, optimal partitions and trimmed query tree based on the strategy of collided block bit-mapping (QTCBB). The relatively accurate estimation of tag backlog and optimal partition ensure a great reduction of collisions in the initial phase. For each collided partition, a QTCBB process is introduced immediately, which eliminates all the empty slots and significantly reduces the collided slots. Simulation results show that EAQ-CBB performs good stability and scalability when the key parameters change. Compared with the existing algorithms, such as DFSA, QTI, T-GDFSA and CT, EAQ-CBB outperforms the others with high system throughput, low normalized latency and low normalized overhead at a low cost of energy, which makes it easier to be used widely in the efficient-aware and energy-aware applications.

A method is proposed targeting the decrease of the number of look-up tables (LUTs) in logic circuits of field programmable gate arrays (FPGA)-based Mealy finite state machines. The method is based on constructing a partition for the set of output variables. It diminishes the number of additional variables encoding the collections of output variables (COVs). A formal method is proposed for finding the partition. An example of synthesis is given, as well as the results of investigations. The investigations were conducted for standard benchmarks.

We construct the inverse partition semigroup, isomorphic to the dual symmetric inverse monoid, introduced in [6]. We give a convenient geometric illustration for elements of . We describe all maximal subsemigroups of and find a generating set for when X is finite. We prove that all the automorphisms of are inner. We show how to embed the symmetric inverse semigroup into the inverse partition one. For finite sets X, we establish that, up to equivalence, there is a unique faithful effective transitive representation of , namely to . Finally, we construct an interesting -cross-section of , which is reminiscent of , the -cross-section of , constructed in [4].

Given a $G$-space $X$ and a non-trivial $G$-invariant ideal ${ℐ}$ of subsets of $X$, we prove that for every partition $X=A_1\cup \cdots \cup A_n$ of $X$ into $n\ge 2$ pieces there is a piece $A_i$ of the partition and a finite set $F\subset G$ of cardinality $\left|F\right|\le \varphi (n+1):={max}_{1<x<n+1}\frac{x^{n+1-x}-1}{x-1}$ such that $G=F\cdot \mathrm{\Delta }(A_i)$ where $\mathrm{\Delta }(A_i)=\{g\in G:g{A}_i\cap A_i\notin {ℐ}\}$ is the difference set of the set $A_i$. Also we investigate the growth of the sequence $\varphi (n)={max}_{1<x<n}\frac{x^{n-x}-1}{x-1}$ and show that $ln\varphi (n+1)=nW(ne)-2n+\frac{n}{W(ne)}+\frac{W(ne)}{n}+O(\frac{lnlnn}{n})$ where $W(x)=lnx-lnlnx+O(\frac{lnlnx}{lnx})$ is the Lambert $W$-function, defined implicitly as $W(x)e^{W(x)}=x$. This shows that $\varphi (n)$ grows faster than that any exponent $a^n$ but slower than the sequence $n!$ of factorials.

This paper formulates "partition type fuzzy integral" which is a fuzzy integral of functions on a partition of the set of all attributes. The identity of it is the set of intermediate fuzzy integrals between the linear form and the usual multilinear fuzzy integrals. In this fuzzy integral, any combination of attributes in the same macro-attribute yields no interactions, but any set of attributes, each member of which belongs to a distinct macro-attribute, causes an interaction. Therefore, we can extract only the essential interactions from the evaluation process by discovering the best expressive partition. An application to a concrete evaluation problem shows the effectiveness of this model.

In this paper, based on the concept of the semantic proximity, a partition method of fuzzy inheritance hierarchies has been given. It is shown that this method is reasonable and effective. Particularly, for a problem with fuzzy concepts, such as systematic botany and zoology, this partition method has especial advantages.

We present an algorithm that for a given simple non-convex polygon P finds an approximate inner-cover by large convex polygons. The algorithm is based on an initial partitioning of P into a set C of disjoint convex polygons which are an exact tessellation of P. The algorithm then builds a set of large convex polygons contained in P by constructing the convex hulls of subsets of C. We discuss different strategies for selecting the subsets and we claim that in most cases our algorithm produces an effective approximation of P.

We show that there are eight special cases of the conditionally free convolution of Bożejko, Leinert and Speicher with the property that in the corresponding moment-cumulant formula no nontrivial weights appear. All the eight convolutions are given. These include the free, the boolean and the Fermi convolutions, another special case of the bold t-free convolution and four more convolution laws that were not treated before.

A Dedekind-finite set is said to be divisible by a natural number n if it can be partitioned into pieces of size n. We study several aspects of this notion, as well as the stronger notion of being partitionable into n pieces of equal size. Among our results are that the divisors of a Dedekind-finite set can consistently be any set of natural numbers (containing 1 but not 0), that a Dedekind-finite power of 2 cannot be divisible by 3, and that a Dedekind-finite set can be congruent modulo 3, to all of 0, 1, and 2 simultaneously. (In these results, 2 and 3 serve as typical examples; the full results are more general.)

Let $T(X)$ be the full transformation monoid on a nonempty set $X$. An element $f$ of $T(X)$ is said to be semi-balanced if the collapse of $f$ is equal to the defect of $f$. In this paper, we prove that an element of $T(X)$ is unit-regular if and only if it is semi-balanced. For a partition ${𝒫}$ of $X$, we characterize unit-regular elements in the monoid $T(X,{𝒫})=\{f\in T(X)|(\forall X_i\in {𝒫})(\exists X_j\in {𝒫})X_{i}f\subseteq X_j\}$ under composition. We characterize regular elements in the submonoids $\mathrm{\Sigma }(X,{𝒫})=\{f\in T(X,{𝒫})|(\forall X_i\in {𝒫})Xf\cap X_i\ne \varnothing \}$ and $\mathrm{\Omega }(X,{𝒫})=\{f\in T(X,{𝒫})|(\forall x,y\in X,x\ne y)(x,y)\in E\Rightarrow xf\ne yf\}$ of $T(X,{𝒫})$, where $E$ is the equivalence induced by ${𝒫}$. We also characterize unit-regular elements in $\mathrm{\Sigma }(X,{𝒫})$, $\mathrm{\Omega }(X,{𝒫})$, and the other two known submonoids of $T(X,{𝒫})$.

We discuss the partial separability and its criteria problems of multipartite qubit mixed states. First, we strictly define what is the partial separability of a multipartite qubit system. Next, we provide a way of reduction from N-partite qubit density matrixes to bipartite qubit density matrixes, and prove a necessary condition that an N-partite qubit mixed state to be partially separable is its reduction to satisfy the PPT condition.

The authors discuss the partition of a finite set of points in the plane into empty convex polygons, and improve some upper bound and lower bound in the related enumeration problems.

Let G be a finite classical group of characteristic p. In this paper, we give an arithmetic criterion of the primes r ≠ p, for which the Steinberg character lies in the principal r-block of G. The arithmetic criterion is obtained from some combinatorial objects (the so-called partition and symbol).