A Turán-type inequality for the gamma function

We prove that the following Turán-type inequality holds for Euler's gamma function. For all odd integers n?1 and real numbers x>0 we have

α?Γ(n−1)(x)Γ(n+1)(x)−Γ(n)²(x),     

Turán’s theorem inverted

In this note we complete an investigation started by Erd?s in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let be the complete r-partite graph with parts of sizes s₁≥2,s₂,…,s_r with an edge added to the first part. Letting t_r(n) be the number of edges of the r-partite Turán graph of order n, we prove that:For all r≥2 and all sufficiently small c>0, every graph of sufficiently large order n with t_r(n)+1 edges contains a .We also give a corresponding stability theorem and two supporting results of wider scope.     

The limiting distribution of the trace of a random plane partition

We study the asymptotic behaviour of the trace (the sum of the diagonal parts) τ _n = τ _n (ω) of a plane partition ω of the positive integer n, assuming that ω is chosen uniformly at random from the set of all such partitions. We prove that (τ _n − c ₀ n ^2/3)/c ₁ n ^1/3 log^1/2 n converges weakly, as n → ∞, to the standard normal distribution, where c ₀ = ζ(2)/ [2ζ(3)]^2/3, c ₁ = √(1/3/) [2ζ(3)]^1/3 and ζ(s) = Σ _j=1^∞ j ^−s . Partial support given by the National Science Fund of the Bulgarian Ministry of Education and Science, grant No. VU-MI-105/2005.     

Über einige Extremalaufgaben bezüglich endlicher Körper

Ohne Zusammenfassung Vorgelegt von P. Turán Herrn ProfessorP. Turán zum 50. Geburtstag gewidmet     

Analytic Continuation of Dirichlet Series with Almost Periodic Coefficients

We consider Dirichlet series z_g,a(s)=?_n=1^￥ g(na) e^{-l_n s}{\zeta_{g,\alpha}(s)=\sum_{n=1}^\infty g(n\alpha) e^{-\lambda_n s}} for fixed irrational α and periodic functions g. We demonstrate that for Diophantine α and smooth g, the line Re(s) = 0 is a natural boundary in the Taylor series case λ _n  = n, so that the unit circle is the maximal domain of holomorphy for the almost periodic Taylor series ?_n=1^￥ g(na) zⁿ{\sum_{n=1}^{\infty} g(n\alpha) z^n}. We prove that a Dirichlet series z_g,a(s) = ?_n=1^￥ g(n a)/n^s{\zeta_{g,\alpha}(s) = \sum_{n=1}^{\infty} g(n \alpha)/n^s} has an abscissa of convergence σ ₀ = 0 if g is odd and real analytic and α is Diophantine. We show that if g is odd and has bounded variation and α is of bounded Diophantine type r, the abscissa of convergence σ ₀ satisfies σ ₀ ≤ 1 − 1/r. Using a polylogarithm expansion, we prove that if g is odd and real analytic and α is Diophantine, then the Dirichlet series ζ _g,α (s) has an analytic continuation to the entire complex plane.     

On the Maximal Multiplicity of Parts in a Random Integer Partition

We study the asymptotic behavior of the maximal multiplicity μ_n = μ_n(λ) of the parts in a partition λ of the positive integer n, assuming that λ is chosen uniformly at random from the set of all such partitions. We prove that πμ_n/(6n)^1/2 converges weakly to max _jX_j/j as n→∞, where X₁, X₂, … are independent and exponentially distributed random variables with common mean equal to 1.2000 Mathematics Subject Classification: Primary—05A17; Secondary—11P82, 60C05, 60F05     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

On the multiplicity of parts in a random partition

Let λ be a partition of an integer n chosen uniformly at random among all such partitions. Let s(λ) be a part size chosen uniformly at random from the set of all part sizes that occur in λ. We prove that, for every fixed m≥1, the probability that s(λ) has multiplicity m in λ approaches 1/(m(m+1)) as n→∞. Thus, for example, the limiting probability that a random part size in a random partition is unrepeated is 1/2. In addition, (a) for the average number of different part sizes, we refine an asymptotic estimate given by Wilf, (b) we derive an asymptotic estimate of the average number of parts of given multiplicity m, and (c) we show that the expected multiplicity of a randomly chosen part size of a random partition of n is asymptotic to (log n)/2. The proofs of the main result and of (c) use a conditioning device of Fristedt. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 185–197, 1999     

On the maximum deviation in random walks

We consider a random walk with drift to the left. LetM _n denote the extreme position to the right of the particle during its firstn steps. An approximate expression for the characteristic function of the distribution of this random variable is evaluated. The numerical inversion of this characteristic function is performed with the aid of the Fast Fourier Transform.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant     

Partitioning Sets of Triples into Small Planes

We study partitions of the set of all ₃ ^v triples chosen from a v-set intopairwise disjoint planes with three points per line. Our partitions may contain copies of PG(2,2) only (Fano partitions) or copies of AG(2, 3) only (affine partitions)or copies of some planes of each type (mixed partitions).We find necessary conditions for Fano or affine partitions to exist. Such partitions are already known in severalcases: Fano partitions for v = 8 and affine partitions for v = 9 or 10. We constructsuch partitions for several sporadic orders, namely, Fano partitions for v = 14, 16, 22, 23, 28, andan affine partition for v = 18. Using these as starter partitions, we prove that Fano partitionsexist for v = 7 ⁿ + 1, 13 ⁿ + 1,27 ⁿ + 1, and affine partitions for v = 8 ⁿ + 1,9 ⁿ + 1, 17 ⁿ + 1. In particular, both Fano and affine partitionsexist for v = 3⁶ⁿ + 1. Using properties of 3-wise balanced designs, weextend these results to show that affine partitions also exist for v = 3²ⁿ .Similarly, mixed partitions are shown to exist for v = 8 ⁿ ,9 ⁿ , 11 ⁿ + 1.     

Exchangeable and partially exchangeable random partitions

Summary Call a random partition of the positive integerspartially exchangeable if for each finite sequence of positive integersn ₁,...,n _k, the probability that the partition breaks the firstn ₁+...+n_k integers intok particular classes, of sizesn ₁,...,n_k in order of their first elements, has the same valuep(n ₁,...,n_k) for every possible choice of classes subject to the sizes constraint. A random partition is exchangeable iff it is partially exchangeable for a symmetric functionp(n ₁,...n_k). A representation is given for partially exchangeable random partitions which provides a useful variation of Kingman's representation in the exchangeable case. Results are illustrated by the two-parameter generalization of Ewens' partition structure.Research supported by N.S.F. Grants MCS91-07531 and DMS-9404345     

On the Minimal Number of Even Submatrices of 0-1 Matrices

An asymptotic formula for the minimum possible number of even p x q submatrices of an m x n 0-1 matrix A is obtained. It is shown that if Ais considered random and pq is even, then the distributionof the number of the even p x q submatricesof A is highly skewed to the right, the left endpointof the distribution being very close to its mean, while its rightendpoint is twice the mean. A relation to Turán numbersis indicated.     

Über orthogonale Polynome

Ohne Zusammenfassung Vorgelegt von P. Turán     

Bounds on Turán determinants

Let μ denote a symmetric probability measure on [−1,1] and let (p_n) be the corresponding orthogonal polynomials normalized such that p_n(1)=1. We prove that the normalized Turán determinant Δ_n(x)/(1−x²), where , is a Turán determinant of order n−1 for orthogonal polynomials with respect to . We use this to prove lower and upper bounds for the normalized Turán determinant in the interval −1<x<1.     

Distribution Functions of Poisson Random Integrals: Analysis and Computation

We want to compute the cumulative distribution function of a one-dimensional Poisson stochastic integral I(g) = ò₀^T g(s) N(ds)I(g) = \displaystyle \int_0^T g(s) N(ds), where N is a Poisson random measure with control measure n and g is a suitable kernel function. We do so by combining a Kolmogorov–Feller equation with a finite-difference scheme. We provide the rate of convergence of our numerical scheme and illustrate our method on a number of examples. The software used to implement the procedure is available on demand and we demonstrate its use in the paper.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

Integer-empty polytopes in the 0/1-cube with maximal Gomory–Chvátal rank

We provide a complete characterization of all polytopes P⊆[0,1]ⁿ with empty integer hulls, whose Gomory–Chvátal rank is n (and, therefore, maximal). In particular, we show that the first Gomory–Chvátal closure of all these polytopes is identical.     

Über ein Problem von K. Zarankiewicz

Ohne Zusammenfassung Vorgelegt von P. Turán