Contributions to zero-sum problems

A prototype of zero-sum theorems, the well-known theorem of Erd?s, Ginzburg and Ziv says that for any positive integer n, any sequence a₁,a₂,…,a_2n-1 of 2n-1 integers has a subsequence of n elements whose sum is 0 modulo n. Appropriate generalizations of the question, especially that for (Z/pZ)^d, generated a lot of research and still have challenging open questions. Here we propose a new generalization of the Erd?s-Ginzburg-Ziv theorem and prove it in some basic cases.     

The classical overdetermined Serrin problem

Abstract

In this survey, we consider the classical overdetermined problem which was studied by Serrin in 1971. The original proof relies on Alexandrov’s moving plane method, maximum principles, and a refinement of Hopf’s boundary point Lemma. Since then other approaches to the same problem have been devised. Among them we consider the one due to Weinberger which strikes for the elementary arguments used and became very popular. Then we discuss also a duality approach involving harmonic functions, a shape derivative approach and a purely integral approach, all of them not relying on maximum principle. For each one, we consider pros and cons as well as some generalizations.     

A generalization of the classical sphere theorem

In this paper, we prove a sphere theorem for Riemannian manifolds with partially positive curvature which generalizes the classical sphere theorem.

     

A generalization of the classical Laguerre polynomials

We consider a modification of the gamma distribution by a discrete measure supported in the pointx=0. For largen we analyze the existence of orthogonal polynomials with respect to such a distribution. Finally we represent them as the hypergeometric function₃ F ₃     

A generalization of a conservativity theorem for classical versus intuitionistic arithmetic

A basic result in intuitionism is Π⁰₂‐conservativity. Take any proof p in classical arithmetic of some Π⁰₂‐statement (some arithmetical statement ?x.?y.P(x, y), with P decidable). Then we may effectively turn p in some intuitionistic proof of the same statement. In a previous paper [1], we generalized this result: any classical proof p of an arithmetical statement ?x.?y.P(x, y), with P of degree k, may be effectively turned into some proof of the same statement, using Excluded Middle only over degree k formulas. When k = 0, we get the original conservativity result as particular case. This result was a by‐product of a semantical construction. J. Avigad of Carnegie Mellon University, found a short, direct syntactical derivation of the same result, using H. Friedman's A‐translation. His proof is included here with his permission. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A generalization of a classical number-theoretic problem,condensate of zeros,and phase transition to an amorphous solid

Regularization of the Bose–Einstein distribution using a parastatistical correction, i.e., by means of the Gentile statistics, is carried out. It is shown that the regularization result asymptotically coincides with the Erd?s formula obtained by using Ramanujan’s formula for the number of variants of the partition of an integer into summands. TheHartley entropy regarded as the logarithm of the number of variants defined by Ramanujan’s exact formula asymptotically coincides with the polylogarithm associated with the entropy of the Bose–Einstein distribution. The fact that these formulas coincide makes it possible to extend the entropy to the domain of the Fermi–Dirac distribution with minus sign. Further, the formulas for the distribution are extended to fractional dimension and also to dimension 1, which corresponds to the Waring problem. The relationship between the resulting formulas and the liquid corresponding to the case of nonpolar molecules is described and the law of phase transition of liquid to an amorphous solid under negative pressure is discussed. Also the connection of the resulting formulas with the gold reserve in economics is considered.     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

Some zero-sum constants with weights

For an abelian group G, the Davenport constant D(G) is defined to be the smallest natural number k such that any sequence of k elements in G has a nonempty subsequence whose sum is zero (the identity element). Motivated by some recent developments around the notion of Davenport constant with weights, we study them in some basic cases. We also define a new combinatorial invariant related to (ℤ/nℤ) ^d , more in the spirit of some constants considered by Harborth and others and obtain its exact value in the case of (ℤ/nℤ)² where n is an odd integer.     

A generalized bottleneck assignment problem

A solution procedure is presented for a generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. A partitioning problem is modeled by this bottleneck problem to provide an example of its application.     

Value of information in two-team zero-sum problems

The situation in which two groups of people have conflicts of interest is considered as a two-team zero-sum game problem. Two special cases of this problem are solved to illustrate that communication among members of a team may not be worth-while and extra information need not always be desired by decision makers. In the appendix, it is shown that the optimal saddle-point solution exists and is still affine for the general problem with quadratic Gaussian performance index.Dedicated to Professor M. R. HestenesThe research reported in this paper was made possible through support extended to the Division of Engineering and Applied Physics, Harvard University, by the U.S. Office of Naval Research under the Joint Services Electronics Program, Contract No. N00014-67-A-0298-0006, and by the National Science Foundation, Grant No. GK-31511.     

On a problem of Recaman and its generalization

We solve some cases of a conjecture of Pomerance concerning reduced residue systems modulo k consisting of the first φ(k) primes not dividing k. We cover the case when k is a prime, thus giving a complete solution to a problem of Recaman.     

A generalization of the construction of test problems for nonconvex optimization

In this paper we adopt and generalize the basic idea of the method presented in [3] and [4] to construct test problems that involve arbitrary, not necessarily quadratic, concave functions, for both Concave Minimization and Reverse Convex Programs     

A look at a problem in heat transfer

Consideration and careful investigation of a simple physical problem in heat transfer shows that even such a problem may not always have solutions and meaningful solutions exist only under restricted conditions. In other words, not all physical problems are well posed. The analysis given here shows that in many practical problems in fluid mechanics and heat transfer the question ‘how well posed is it?’ is non-trivial.     

A variant of the classical Ramsey problem

For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK _p K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK _p subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK _n . We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erds and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414.