Search

In this correspondence, we will introduce a new combinatorial method for a coordinate-wise construction of the homogeneous-weight preserving Gray map for Galois rings by using elementary tools from Affine Geometries. Our construction differs in the methods used from the algebraic constructions done previously in [M. Greferath, S.E. Schmidt, Gray Isometries for finite chain rings and a nonlinear ternary (36, 312, 15) code, IEEE Trans. Inform. Theory 45 (1999) 2522–2524; S. Ling, J.T. Blackford, Zpk+1-linear codes, IEEE Trans. Inform. Theory 48 (2002) 2592–2605].

In this paper we consider a combinatorial method for the analysis of finite words recently introduced in Colosimo and de Luca (Special factors in biological strings, preprint 97/42, Dipt. Matematica, Univ. di Roma) for the study of biological macromolecules. The method is based on the analysis of (right) special factors of a given word. A factor u of a word w is special if there exist at least two occurrences of the factor u in w followed on the right by two distinct letters. We show that in the combinatorics of finite words two parameters play an essential role. The first, denoted by R, represents the minimal integer such that there do not exist special factors of w of length R. The second, that we denote by K, is the minimal length of a factor of w which cannot be extended on the right in a factor of w. Some new results are proved. In particular, a new characterization in terms of special factors and of R and K is given for the set PER of all words w having two periods p and q which are coprimes and such that ¦w¦ = p + q − 2.

We present a combinatorial method to determine the dimension of H-strata in the algebra of mxn quantum matrices O"q(M"m","n(K)) as follows. To a given H-stratum we associate a certain permutation via the notion of pipe dreams. We show that the dimension of the H-stratum is precisely the number of odd cycles in this permutation. Using this result, we are able to give closed formulas for the trivariate generating function that counts the d-dimensional H-strata in O"q(M"m","n(K)). Finally, we extract the coefficients of this generating function in order to settle conjectures proposed by the first and third named authors (Bell and Launois (2010) [3], Bell, Launois and Lutley (2010) [4]) regarding the asymptotic proportion of d-dimensional H-strata in O"q(M"m","n(K)).

We settle a question of Bressoud concerning the existence of an explicit bijection from a class of oriented square-ice graphs to a class of tournaments. We give an algorithm constructing such a bijection., 18 pages, LaTeX; minor corrections. To appear in FoataFest proceedings issue of Advances in Applied Mathematics

In this paper we develop a method for determining the number of integers without large prime factors lying in a given set S. We will apply it to give an easy proof that certain sufficiently dense sets A and B always produce the expected number of “smooth” sums a + b , a ∈ A , b ∈ B . The proof of this result is completely combinatorial and elementary.

A new generating function enumerating column-convex polyominoes is defined and determined. The expression of the generating function which enumerates polyominoes according to area and number of columns, obtained by Delest (1988), immediately follows as a particular case. Our method is constructive and clearly explains the rational nature of these functions. In the last part, another enumerative application of this method is also presented.

A deduction of generalized quantum entropies within the non-Gaussian frameworks, Tsallis and Kaniadakis, is derived using a generalized combinatorial method and the so-called q and κ calculus. In agreement with previous results, we also show that for the Tsallis formulation the q -quantum entropy is well-defined for values of the nonextensive parameter q lying in the interval [0,2].

Erdos and Sarkozy proposed the problem of determining the maximal density attainable by a set S of positive integers having the property that no two distinct elements of S sum up to a perfect square. Massias [(Sur les suites dont les sommes des terms 2 a 2 ne sont par des carr)] exhibited such a set consisting of all x ≡ 1 (mod 4) with x ≡ 14, 26, 30 (mod 32). Lagarias et al. [(J. Combin. Theory Ser. A 33 (1982) 167)] showed that for any positive integer n, one cannot find more than 11/32n residue classes (modn) such that the sum of any two is never congruent to a square (modn), thus essentially proving that the Massias' set has the best possible density. They [(J. Combin. Theory Sen A 34 (1983) 123)] also proved that the density of such a set S is never > 0.475 when we allow general sequences. We improve on the lower bound for general sequences, essentially proving that it is not 0.475, but arbitrarily close to 11/32, the same as that for sequences made up of only arithmetic progressions.

Combinatorial (or rule-based) methods for inferring haplotypes from genotypes on a pedigree have been studied extensively in the recent literature. These methods generally try to reconstruct the haplotypes of each individual so that the total number of recombinants is minimized in the pedigree. The problem is NP-hard, although it is known that the number of recombinants in a practical dataset is usually very small. In this paper, we consider the question of how to efficiently infer haplotypes on a large pedigree when the number of recombinants is bounded by a small constant, i.e. the so called k-recombinant haplotype configuration (k-RHC) problem. We introduce a simple probabilistic model for k-RHC where the prior haplotype probability of a founder and the haplotype transmission probability from a parent to a child are all assumed to follow the uniform distribution and k random recombination events are assumed to have taken place uniformly and independently in the pedigree. We present an O(mnlog k+1 n) time algorithm for k-RHC on tree pedigrees without mating loops, where m is the number of loci and n is the size of the input pedigree, and prove that when 90log n

Current economic uncertainties and tighter environmental regulations has led industries to consider energy conservation projects more seriously. In this paper, the option of varying the process stream temperature has been suggested as a mean of increasing heat recovery for heat exchanger networks (HEN). Alternatives are generated and assessed using a developed approach. Essentially, the approach involves systematic steps in varying the Hot and/or Cold streams' temperature for each stream in a way that increases the heat recovery approach temperature (HRAT), thus allowing more heat to be recovered. Using the combinatorial method of paths combinations, the adjustment of heat loads for hot and cold utilities from the heat load shifting through the heat exchanger network could be made and assessed accordingly. The changes in temperature made to the streams while exploring each alternative has to be kept within small magnitude i.e., around 1–5 °C. A user friendly computer program has been developed for performing the approach in view of the significant number of iterations required. An example is used in this paper to demonstrate the application of the developed approach.

Let A∗ be the free monoid of base A and n a fixed positive integer. For any word wϵA∗ we consider the set [w]n of all the words which are equivalent to w modulus the congruence θn generated by the relation xn∼xn+1, where x is any word of A∗. The main result of the paper is that if n>4 then for any word wϵA∗ the congruence class [w]n is a regular language. We also prove that the word problem for the quotient monoid Mn=A∗θn is recursively solvable.

The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp (Theoret. Comput. Sci. 303(2003), 267-301), and was generalized by Kuo (Theoret. Comput. Sci. 319 (2004), 29-57) and Yan and Zhang (J. Combin. Theory Ser. A, 110(2005), 113-125). In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond., Comment: 13 pages, 5 figures. accepted by Theoretial Computer Science

A consecutive-k-out-of-n: F system has n i.i.d. components; the system fails if any k consecutive components fail. This paper gives a simple, direct combinatorial method for determining the system failure probability.

Fisher (1928) introduced a combinatorial method for obtaining the sampling moments/cumulants of k -statistics in terms of population cumulants. His method for infinite populations was modified for finite populations by Tracy (1963).

Bechhofer’s indifference-zone-approach in selection with selection rules based on the sample mean, the α-trimmed mean an the median is investigated. The author investigates the robustness of these selection rules against deviation from an assumed distribution by assuming the distributions belonging to the populations are threepoint distributions. This method yields exact results. The selection rule based on the sample mean is investigated for robustness against deviation from the normal distribution.

After defining robustness for interval estimations and tests, the paper presents an exact method for investigating this property for discrete distributions with finite supports. This method is used to investigate the u- and t-tests in the case of the single sample problem for robustness in respect of two and three point distributions.

An Edgeworth expansion of first order is established for general linear rank statistics under the null hypothesis with a remainder term that is usually of order $n^{-1}$. Furthermore, corresponding results for the second order are formulated, but not proved here. The proof for the first order is based on Stein's method and on an extension of a combinatorial method of Bolthausen. It is also shown that conditions of van Zwet imply up to a small factor our conditions for the validity of Edgeworth expansions. Moreover, our proof for the first order also provides us with a result about Edgeworth expansions for smooth functions.

In the paper a finite method for bilinear programming is given. It is based on an algorithm, which was developed by Thoai [l6j for the minimization of a concave function on a bounded polyhedron.

The problem described in this paper arises whenever, for political or administrative reasons, a geographical region must be partitioned into an unknown number of districts so that, within each district,the total amount of service supplied by existing facilities of known location and capacity may satisfy a given demand, according to some optimality criterion. The philosophy of the problem is quite different from that of the so-called Location Problem (see for example TOREGAS et AL. [I]), since we are neither seeking locations for new facilities nor trying to modify their capacities. The following assumptions will define the problem more clearly. I. The region is considered to be made up of a certain number of assigned undivisible communities of known concentrated population. 2. Each community must be univocally assigned to a district, no overlap among districts is allowed. 3. The location and capacity of every facility are assigned. 4. 5. 6. i. e.

A combinatorial method is described for grouping cases with multiple malformations for the purpose of identifying previously undescribed syndromes. This method includes ways of carrying out 'tight' or 'loose' grouping, of allowing for variability of reporting of physical features by different observers, and of minimising the number of 'spurious' groups. Evaluation using a test data set of known dysmorphic syndromes showed that the method provides a feasible and useful means of grouping undiagnosed cases.

Wishart has demonstrated and Kendall has justified the application of a combinatorial method to products of $k$-statistics. Wishart's combinatorial method is, essentially, that introduced by Fisher though modifications were necessary since Fisher's method is applied directly to the writing of cumulant results while Wishart's method applies to products of $k$-statistics. It is the purpose of this paper to show that the combinatorial method may be further modified and extended so as to produce products of polykays and to present general formulae resulting from the new combinatorial method.

This paper is a sequel to a paper by the author entitled “Restricted Transition Probabilities and Their Applications to Some Problems in the Dynamics of Biological Populations” (Bull. Math. Biophysics, 1966,28, 315–331). The paper is divided into two parts. In part one some aspects of the maximum size attained by the population during a finite time interval are studied for the case the stochastic process underlying the evolution of the population is a birth process. Two interesting by-products emerge from the study presented in part one; namely a combinatorial method of finding solutions to the Kolmogorov differential equations in special cases, and secondly, a set of criteria for the optimum allocation of genotypes in the host population of a host-pathogen system. The optimum allocation of genotypes in the host population is a problem of practical importance in controlling plant pathogens. In part two the theory of restricted transition probabilities developed in the companion paper is applied in finding the distribution of the time to the appearance of the first mutation for the case of a two dimensional birth process. The distribution of the time to the appearance of the first mutation is of importance in understanding the role mutation plays in the evolution of a population, particularly in the pathogen population of a host-pathogen system.

Although successfully employed on many industrial problems, Combinatorial Optimization still has limited applicability on several real-world domains, often due to modeling difficulties. This is typically the case for systems under the control of an on-line policy: even when the policy itself is well known, capturing its effect on the system in a declarative model is often impossible by conventional means. Such a difficulty is at the root of the classical, sharp separation between off- line and on-line approaches. In this paper, we investigate a general method to model controlled systems, based on the integration of Machine Learning and Constraint Programming (CP). Specifically, we use an Artificial Neural Network (ANN) to learn the behavior of a controlled system (a multicore CPU with thermal con- trollers) and plug it into a CP model by means of Neuron Constraints. The method obtains significantly better results compared to an approach with no ANN guidance. Neuron Constraints were first introduced in [Bartolini et al., 2011b] as a mean to model complex systems: providing evidence of their applicability to controlled systems is a significant step forward, broadening the application field of combinatorial methods and disclosing opportunities for hybrid off-line/on-line optimization.

The problem of designing molecules or compounds with desired properties is complex primarily because it is combinatorial. A novel approach is proposed here by resorting to a combinatorial analysis of the problem. It is supposed that the set of functional groups is available and that the intervals of values of the desired properties of the molecule or compound to be designed are known. The desired properties constitute constraints on the integer variables assigned to the functional groups. The feasible region defined by such constraints is determined by an algorithm involving a branching strategy. This algorithm generates those collections of the functional groups that can constitute structurally feasible molecules or compounds satisfying the constraints on the given properties. The efficacy of the approach has been demonstrated with several examples.

Recent improvements in the accessibility of high-throughput genotyping have brought a great deal of attention to disease association and susceptibility studies. This paper explores possibility of applying combinatorial methods to disease susceptibility prediction. The proposed combinatorial methods as well as standard statistical methods are applied to publicly available genotype data on Crohn's disease and autoimmune disorders for predicting susceptibility to these diseases. The quality of susceptibility prediction algorithm is assessed using leave-one-out and leave-many-out tests - the disease status of one or several individuals is predicted and compared to the their actual disease status which is initially made unknown to the algorithm. The best prediction rate achieved by the proposed algorithms is 77.78% for Crohn's disease and 64.99% for autoimmune disorders, respectively.

In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure. No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constraints imposed by the chosen grid. In this paper we present a new approach which combines the grid-based combinatorial method with Simulated Annealing on a continuous model. This allows us to explore arbitrary orientations and placements of boxes, hence closing the gap even further, and - in some cases - even surpass the manual expert solution. The implemented software system allows our industrial partner to incorporate the trunk volume in a very early stage of the car design process without relying on a repeated and cumbersome manual evaluation of the volume. Copyright © 2005 by the Association for Computing Machinery, Inc.

Menger's basis property is a generalization of $\sigma$-comp\-actness and admits an elegant combinatorial interpretation. We introduce a general combinatorial method to construct non $\sigma$-compact sets of reals with Menger's property. Special instances of these constructions give known counterexamples to conjectures of Menger and Hurewicz. We obtain the first explicit solution to the Hurewicz 1927 problem, that was previously solved by Chaber and Pol on a dichotomic basis. The constructed sets generate nontrivial subfields of the real line with strong combinatorial properties, and most of our results can be stated in a Ramsey-theoretic manner. Since we believe that this paper is of interest to a diverse mathematical audience, we have made a special effort to make it self-contained and accessible.

We present several multivariate histogram density estimates that are universallyL1-optimal to within a constant factor and an additive term\(O\left( {\sqrt {\log {n \mathord{\left/ {\vphantom {n n}} \right. \kern-\nulldelimiterspace} n}} } \right)\). The bin widths are chosen by the combinatorial method developed by the authors inCombinatorial Methods in Density Estimation (Springer-Verlag, 2001). The present paper solves a problem left open in that book.

The paper describes facilities and computation methods of the new RTS&T Monte Carlo code. This code performs simulations of three dimensional electromagnetic shower development and low energy neutron production and transport in accelerator and in shielding components with a calculation of the isotope transmutation problem. RTS&T is based on a compilation from ENDF/B-VI, JENDL-3, EAF, FENDL and EPNDL evaluated data libraries to detailed physical process simulation and only a few approximations are made. It is possible to use RTS&T to solve the critical reactor problem. A combinatorial method of geometry definition is provided with the program. Recently the RTS& T code interface to the ANSYS 4.4 code system has been developed and tested.

In this paper a method for solving the short term transmission network expansion planning (STTNEP) problem is presented. The STTNEP is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In this work we present a constructive heuristic algorithm to find a solution of the STTNEP of excellent quality. In each step of the algorithm a sensitivity index is used to add a circuit (transmission line or transformer) to the system. This sensitivity index is obtained solving the STTNEP problem considering as a continuous variable the number of circuits to be added (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an interior points method that uses a combination of the multiple predictor corrector and multiple centrality corrections methods, both belonging to the family of higher order interior points method (HOIPM). Tests were carried out using a modified Garver system and the results presented show the good performance of both the constructive heuristic algorithm to solve the STTNEP problem and the HOIPM used in each step.

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 parameter 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 emphasize the fact that, in contrast with the probabilistic approach which only provides asymptotic results, the combinatorial approach provides exact results that are useful when considering short sequences., 12 p., 2 figs

This paper presents a combinatorial analysis of limited-availability groups to which the mixture of different multi-channel traffic streams is offered. The availability distributions of an exactly determined number of subgroups has been derived for traffic streams of various classes. The determined distributions enable calculation of blocking probabilities in multi-stage switching networks carrying different multi-channel traffic streams by the effective availability method. The paper defines the components of effective availability and gives procedures for their determination in the case of multi-channel traffic. In this paper, two calculation methods are derived, one used for point-to-point selection, and the other for point-to-group selection. The results of analytical calculations are compared with the results of digital simulation of three-stage switching networks. The proposed formulae can be used in the analysis of isdn and ?-isdn systems.

The application and success of combinatorial approaches to protein engineering problems have increased dramatically. However, current directed evolution strategies lack a combinatorial methodology for creating libraries of hybrid enzymes which lack high homology or for creating libraries of highly homologous genes with fusions at regions of non-identity. To create such hybrid enzyme libraries, we have developed a series of combinatorial approaches that utilize the incremental truncation of genes, gene fragments or gene libraries. For incremental truncation, Exonuclease III is used to create a library of all possible single base-pair deletions of a given piece of DNA. Incremental truncation libraries (ITLs) have applications in protein engineering as well as protein folding, enzyme evolution, and the chemical synthesis of proteins. In addition, we are developing a methodology of DNA shuffling which is independent of DNA sequence homology.

We formulate the local combinatorial method for constructing the complete set of operators that commute with the transfer matrix of the Zamolodchikov-Bazhanov-Baxter model in the vertex formulation. We find the compact functional equation satisfied by the generating functional of this complete set of operators.

Molecular structural effects on infinite dilution activity coefficients of solutes in n-alkanes and other hydrocarbons are studied within the UNIFAC model. Characteristic chain-length dependencies and other structural relationships imbedded in the model are discussed with emphasis to the consequences this has for model development. The cases treated have subtle but major implications for the correlation of activity coefficients and derivatives since these imply that combinatorial terms may not be small and they can be essential to the success of correlations based on UNIFAC. We have examined a number of infinite dilution properties and find that current expressions do not adequately describe these and other cases. The analysis is described and comparisons of the expressions with data for important systems are presented. New models are not presented, but improvements with either modified group definitions or revised relationships are discussed. The importance of such adjustments, for adding new terms to the existing equations, is stressed.

The numerical quantum transfer-matrix method and an advanced algebraic and combinatorial approach applicable to the mesoscopic rings have been worked out. Characterization of the ring [Mn(hfac)2NITPh]6 with non-uniform spin is also presented.

The free-fermion model is solved by means of a combinatorial method which amounts to counting free random walks on a lattice.

Vector quantization is a classical method used in mobile communications. Each sequence of d samples of the discretized vocal signal is associated to the closest d-dimensional codevector of a given set called codebook. Only the binary indices of these codevectors (the codewords) are transmitted over the channel. Since channels are generally noisy, the codewords received are often slightly different from the codewords sent. In order to minimize the distortion of the original signal due to this noisy transmission, codevectors indexed by one-bit different codewords should have a small mutual Euclidean distance. This paper is devoted to this problem of index assignment of binary codewords to the codevectors. When the vector quantizer has a Gaussian structure, we show that a fast index assignment algorithm based on simple geometrical and combinatorial considerations can improve the SNR at the receiver by 5dB with respect to a purely random assignment. We also show that in the Gaussian case this algorithm outperforms the classical combinatorial approach in the field.