On non-orthogonal main effect plans for asymmetrical factorials

Summary Following the lines of Raktoe and Federer [19] a unified approach for constructing main effect plans in any factorials wherek _i's are the numbers of equispaced levels of each of then _i factors, andk _i's are not necessarily primes or prime powers and need not satisty any relations among themselves, is presented. The method consists of, first, dividing the totality of treatment combinations, omitting, of course, some, if necessary, in to pairs such that the differences within the pairs are clear of ‘even’ effects and the sums are clear of ‘odd’ effects, and then, depending on the number of error d.f. wanted, selecting a suitable sub-set of these pairs which lead to the solution of the estimates of main effects. A general class of non-orthogonal main effect plans for 2 ^m ×2 ⁿ factorials is proposed. Information matrices and their inverses for such plans are worked out. An example followed by discussions and comparison statements is presented.     

Remark on factorials that are products of factorials

In a paper published in 1993, Erdös proved that if n! = a! b!, where 1 < a ≤ b, then the difference between n and b does not exceed 5 log log n for large enough n. In the present paper, we improve this upper bound to ((1 + ε)/ log 2) log log n and generalize it to the equation a ₁!a ₂! ... a _k ! = n!. In a recent paper, F. Luca proved that n ? b = 1 for large enough n provided that the ABC-hypothesis holds.     

Squares and factorials in products of factorials

We study a question of Erd?s and Graham on products of factorials being a square or again a factorial.     

Factorization of factorials

If factorials enter into product-quotient expressions, not allowing approximative calculation, the factorization into powers of primes is recommended. The paper describes a computer program for this process, based on a known formula, which should be applied differently, according as the primes are large or small. A discussion shows how to distinguish between large and small in order to minimize the computing time.     

The exponents in the prime decomposition of factorials

Let ν_p(n) be the exponent of p in the prime decomposition of n. We show that for different primes p, q satisfying some mild constraints the integers ν_p(n!) and ν_q(n!) cannot both be of a rather special form.     

On the complexity of posets

The purpose of this paper is to discuss several invariants each of which provides a measure of the intuitive notion of complexity for a finite partially ordered set. For a poset X the invariants discussed include cardinality, width, length, breadth, dimension, weak dimension, interval dimension and semiorder dimension denoted respectively X, W(X), L(X), B(X), dim(X). Wdim(X), Idim(X) and Sdim(X). Among these invariants the following inequalities hold. $\text{B(}\text{X}\text{)?Idim(}\text{X}\text{)?Sdim(}\text{X}\text{)?Wdim(}\text{X}\text{)?dim(}\text{X}\text{)?W(}\text{X}\text{)}$. We prove that every poset X with three of more points contains a partly with $\text{Idim}\text{(}\text{X}\text{)}\text{Idim}\text{(}\text{X}\text{) {x,v})}$. If M denotes the set of maximal elements and A an arbitrary anticham of X we show that $\text{Idim}\text{(}\text{X}\text{)?W(}\text{X-M}\text{)}$ and $\text{Idim}\text{(}\text{X}\text{)?2W(}\text{X-A}\text{)}$. We also show that there exist functions f(n,t) and (gt) such that $\text{I(}\text{X}\text{)?n}$ and $\text{Idim}\text{(}\text{X}\text{)?t}$simply $\text{dim}\text{(}\text{X}\text{)?f(n,t and Sdim(}\text{X}\text{)?t}$ implies $\text{dim}\text{(}\text{X}\text{)?g(t)}$.     

On the complexity of circulations

We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.     

Remarks on a sum containing factorials

It is shown how readily a sum containing factorials, which was considered recently by Samoletov (J. Comput. Appl. Math. 131 (2001) 503–504), would follow from substantially more general known results.     

Some properties of infinite factorials

With the Axiom of Choice , for any infinite cardinal but, without , we cannot conclude any relationship between and for an arbitrary infinite cardinal . In this paper, we give some properties of in the absence of and compare them to those of for an infinite cardinal . Among our results, we show that “ for any infinite cardinal and any natural number n” is provable in although “ for any infinite cardinal ” is not.     

On the complexity of constrained VC-classes

Sauer's lemma is extended to classes H_N of binary-valued functions h on [n]={1,…,n} which have a margin less than or equal to N on all x∈[n] with h(x)=1, where the margin μ_h(x) of h at x∈[n] is defined as the largest non-negative integer a such that h is constant on the interval I_a(x)=[x-a,x+a]⊆[n]. Estimates are obtained for the cardinality of classes of binary-valued functions with a margin of at least N on a positive sample S⊆[n].     

On the complexity of polyhedral separability

It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be separated withk lines. For every fixedk in any fixed dimension, it takes polynomial time to recognize whether two sets of points can be separated withk hyperplanes.     

On the complexity of diagram testing

In 1987, Neetil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Neetil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.     

On the topological complexity of DC-sets

A DC-set is a set defined by means of convex constraints and one additional inverse convex constraint. Given an arbitrary closed subsetM of the Euclideann-space, we show that there exists a DC-set in (n+1)-space being homeomorphic to the given setM. Secondly, for any fixedn2, we construct a compactn-dimensional manifold with boundary, which is a DC-set and which has arbitrarily large Betti-numbersr _k fork n–2.     

On the complexity of stochastic integration

We study the complexity of approximating stochastic integrals with error for various classes of functions. For Ito integration, we show that the complexity is of order , even for classes of very smooth functions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiener measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorithm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integration, we show that the complexity depends on the smoothness of the integrand and may be much smaller than the complexity of Ito integration.

     

On the complexity of computing treelength

We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007) [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most k is NP-complete for every fixed k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than . Additionally, we show that treelength can be computed in time O^∗(1.7549ⁿ) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.     

On the analytic complexity of discriminants

The paper deals with the notion of analytic complexity introduced by V.K. Beloshapka. We give an algorithm which allows one to check whether a bivariate analytic function belongs to the second class of analytic complexity. We also provide estimates for the analytic complexity of classical discriminants and introduce the notion of analytic complexity of a knot.     

On the equational complexity of RRA

We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function.