An exponential separation between the parity principle and the pigeonhole principle

The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai (1990) previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai's lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory.

Our lower bound is also related to the inherent complexity of particular search classes (see Papadimitriou, 1991). In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques (Beame et al., 1995).     

Matrix identities and the pigeonhole principle

We show that short bounded-depth Frege proofs of matrix identities, such as PQ=IQP=I (over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since the latter principle is known to require exponential-size bounded-depth Frege proofs, it follows that the propositional version of the matrix principle also requires bounded-depth Frege proofs of exponential size.     

An optimal lower bound for the Frobenius problem

Given N?2 positive integers a₁,a₂,…,aN with GCD(a₁,…,aN)=1, let fN denote the largest natural number which is not a positive integer combination of a₁,…,aN. This paper gives an optimal lower bound for fN in terms of the absolute inhomogeneous minimum of the standard (N−1)-simplex.     

An upper bound on the size of the snake-in-the-box

A snake in a graph is a simple cycle without chords. We give an upper bound on the size of a snake S in then-dimensional cube of the form |S|2 ^n–1(1–n ^1/2/89+O(1/n)).     

An egg-yolk principle and exponential integrability for quasiregular mappings

Quasiregular mappings f:ⁿⁿ are a natural generalization of analyticfunctions from complex analysis and provide a theory which isrich with new phenomena. In this paper we extend a well-knownresult of Chang and Marshall on exponential integrability ofanalytic functions in the disk, to the case of quasiregularmappings defined in the unit ball of ⁿ. To this end, an ‘egg-yolk’principle is first established for such maps, which extendsa recent result of the first author. Our work leaves open aninteresting problem regarding n-harmonic functions.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

Upper bound on the lengthening of proofs by cut elimination

In this paper there are constructed sequential calculi KGL and IGL. The calculus KGI is a version of the classical predicate calculus, and IGL is a version of constructive calculus. KGL and IGL do not contain structural rules and there are no rules in them for which in some premise more than one lateral formula would be contained. A procedure for eliminating cuts from proofs in these calculi is described. It is shown that the height of a derivation obtained by this procedure exceeds 2 ^h, where h is the height of the original derivation, is the number of sequences in the original derivation,.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 87–98, 1984.     

Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r−1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, and very recently the conjecture was proved for the case where r=3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.     

An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order

We prove that each OBDD (ordered binary decision diagram) for the middle bit of n-bit integer multiplication for one of the variable orders which so far achieve the smallest OBDD sizes with respect to asymptotic order of growth, namely the pairwise ascending order x₀,y₀,…,x_n−1,y_n−1, requires a size of Ω(2^(6/5)n). This is asymptotically optimal due to a bound of the same order by Amano and Maruoka (2007) [1].     

On the upper bound of uniformly bounded solutions

New conditions of uniform boundedness of solutions are obtained and methods for calculating upper bounds are suggested.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 5, pp. 501–505, May, 1994.     

An approximate lower tolerance bound for the three-parameter Weibull applied to lumber property characterization

We investigate a large sample approach for obtaining tolerance bounds where the underlying population is a three-parameter Weibull distribution. Accurate tolerance bounds could play an important role in the development of lumber standards. Properties of the maximum likelihood based approach are compared with those of the standard nonparametric tolerance procedure. The asymptotic normal approximation to the tolerance bound was found to be inadequate for most of the cases considered.     

A lower bound on the size of an absorbing set in an arc-coloured tournament

Bousquet, Lochet and Thomassé recently gave an elegant proof that for any integer $n$, there is a least integer $f\left(n\right)$ such that any tournament whose arcs are coloured with $n$ colours contains a subset of vertices $S$ of size $f\left(n\right)$ with the property that any vertex not in $S$ admits a monochromatic path to some vertex of $S$. In this note we provide a lower bound on the value $f\left(n\right)$.