On Erdős-Rado numbers

In this paper new proofs of the Canonical Ramsey Theorem, which originally has been proved by Erd?s and Rado, are given. These yield improvements over the known bounds for the arising Erd?s-Rado numbersER(k; l), where the numbersER(k; l) are defined as the least positive integern such that for every partition of thek-element subsets of a totally orderedn-element setX into an arbitrary number of classes there exists anl-element subsetY ofX, such that the set ofk-element subsets ofY is partitioned canonically (in the sense of Erd?s and Rado). In particular, it is shown that $$2^{c1} .l^2 \leqslant ER(2;l) \leqslant 2^{c_2 .l^2 .\log l} $$ for every positive integerl≥3, wherec ₁,c ₂ are positive constants. Moreover, new bounds, lower and upper, for the numbersER(k; l) for arbitrary positive integersk, l are given.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Jacobi and Kummer’s ideal numbers

In this article we give a modern interpretation of Kummer’s ideal numbers and show how they developed from Jacobi’s work on cyclotomy, in particular the methods for studying “Jacobi sums” which he presented in his lectures on number theory and cyclotomy in the winter semester 1836/37.     

Waring’s problem in prime numbers

The existence of a constant V(n) such that any sufficiently large natural number can be represented as a sum of nth degrees of primes in total quantity not exceeding this constant is proved.     

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     

Turán numbers for odd wheels

The Turán number $\text{ex}(n,G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A wheel$W_n$ is a graph on $n$ vertices obtained from a $C_{n?1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n?1}$. We obtain two exact values for small wheels:

$\text{ex}(n,W_5)=?\frac{n^2}{4}+\frac{n}{2}?,$

$\text{ex}(n,W_7)=?\frac{n^2}{4}+\frac{n}{2}+1?.$

Given that $\text{ex}(n,W_6)$ is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound $\text{ex}(n,W_{2k+1})>?\frac{n^2}{4}?+?\frac{n}{2}?$ in general case.     

How quadratic are the natural numbers?

Abstract. For natural numbers n we inspect all factorizations n = ab of n with a ￡ ba \le b in \Bbb N\Bbb N and denote by n=a_n b_nn=a_n b_n the most quadratic one, i.e. such that b_n - a_nb_n - a_n is minimal. Then the quotient k(n) : = a_n/b_n\kappa (n) := a_n/b_n is a measure for the quadraticity of n. The best general estimate for k(n)\kappa (n) is of course very poor: 1/n ￡ k(n) ￡ 11/n \le \kappa (n)\le 1. But a Theorem of Hall and Tenenbaum [1, p. 29], implies(logn)^-d-e ￡ k(n) ￡ (logn)^-d(\log n)^{-\delta -\varepsilon } \le \kappa (n) \le (\log n)^{-\delta } on average, with d = 1 - (1+log₂  2)/log2=0,08607 ?\delta = 1 - (1+\log _2 \,2)/\log 2=0,08607 \ldots and for every e > 0\varepsilon >0. Hence the natural numbers are fairly quadratic.¶k(n)\kappa (n) characterizes a specific optimal factorization of n. A quadraticity measure, which is more global with respect to the prime factorization of n, is k^*(n): = ?_{1 ￡ a ￡ b, ab=n} a/b\kappa ^*(n):= \textstyle\sum\limits \limits _{1\le a \le b, ab=n} a/b. We show k^*(n) ~ \frac 12\kappa ^*(n) \sim \frac {1}{2} on average, and k^*(n)=W(2^{\frac 12(1-e) log n/log ₂n})\kappa ^*(n)=\Omega (2^{\frac {1}{2}(1-\varepsilon ) {\log}\, n/{\log} _2n})for every e > 0\varepsilon>0.     

Liouville numbers and Schanuel’s Conjecture

In this paper, using an argument of P. Erd?s, K. Alniaçik, and É. Saias, we extend earlier results on Liouville numbers, due to P. Erd?s, G.J. Rieger, W. Schwarz, K. Alniaçik, É. Saias, E.B. Burger. We also produce new results of algebraic independence related with Liouville numbers and Schanuel’s Conjecture, in the framework of ${G_\delta}$ -subsets.     

Markoff–Lagrange spectrum and extremal numbers

Let \( \gamma = \frac{1}{2}\left( {1 + \sqrt {5} } \right) \) denote the golden ratio. H. Davenport and W. M. Schmidt showed in 1969 that, for each non-quadratic irrational real number ξ, there exists a constant c > 0 with the property that, for arbitrarily large values of X, the inequalities\( \left| {{x_0}} \right| \leqslant X,\,\,\,\left| {{x_0}\xi - {x_1}} \right| \leqslant c{X^{{{{ - 1}} \left/ {\gamma } \right.}}}\,\,\,{\text{and}}\,\,\,\left| {{x_0}{\xi^2} - {x_2}} \right| \leqslant c{X^{{{{ - 1}} \left/ {\gamma } \right.}}} \)admit no non-zero solution \( \left( {{x_0},{x_1},{x_2}} \right) \in {\mathbb{Z}^3} \). Their result is best possible in the sense that, conversely, there are countably many non-quadratic irrational real numbers ξ such that, for a larger value of c, the same inequalities admit a non-zero integer solution for each X ≥ 1. Such extremal numbers are transcendental and their set is stable under the action of \( {\text{G}}{{\text{L}}_2}\left( \mathbb{Z} \right) \) on \( \mathbb{R}\backslash \mathbb{Q} \) by linear fractional transformations. In this paper, it is shown that there exist extremal numbers ξ for which the Lagrange constant ν(ξ) = liminf _q→∞ q||qξ|| is \( \frac{1}{3} \), the largest possible value for a non-quadratic number, and that there is a natural bijection between the \( {\text{G}}{{\text{L}}_2}\left( \mathbb{Z} \right) \)-equivalence classes of such numbers and the non-trivial solutions of Markoff’s equation.     

Improved bounds on the Hadwiger–Debrunner numbers

Let HD _d (p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in Rd which satisfy the (p, q)-property (p ≥ q ≥ d + 1). In a celebrated proof of the Hadwiger–Debrunner conjecture, Alon and Kleitman proved that HD _d (p, q) exists for all p ≥ q ≥ d + 1. Specifically, they prove that \(H{D_d}(p,d + 1)is\tilde O({p^{{d^2} + d}})\).We present several improved bounds: (i) For any \(q \geqslant d + 1,H{D_d}(p,d) = \tilde O({p^{d(\frac{{q - 1}}{{q - d}})}})\). (ii) For q ≥ log p, \(H{D_d}(p,q) = \tilde O(p + {(p/q)^d})\). (iii) For every ? > 0 there exists a p₀ = p₀(?) such that for every p ≥ p₀ and for every \(q \geqslant {p^{\frac{{d - 1}}{d} + \in }}\) we have p ? q + 1 ≤ HD _d (p, q) ≤ p ? q + 2. The latter is the first near tight estimate of HD _d (p, q) for an extended range of values of (p, q) since the 1957 Hadwiger–Debrunner theorem.We also prove a (p, 2)-theorem for families in R² with union complexity below a specific quadratic bound.     

Total positivity properties of Jacobi–Stirling numbers

The Jacobi–Stirling numbers of the first and second kinds were first introduced in Everitt et al. (2007) [8] and they are a generalization of the Legendre–Stirling numbers. Quite remarkably, they share many similar properties with the classical Stirling numbers. In this paper we study total positivity properties of these numbers. In particular, we prove that the matrix whose entries are the Jacobi–Stirling numbers is totally positive and that each row and each column is a Pólya frequency sequence, except for the columns with (unsigned) numbers of the first kind.     

Sums of products of Apostol–Bernoulli numbers

By expressing the sums of products of the Apostol?CBernoulli polynomials in terms of the special values of multiple Hurwitz?CLerch zeta functions at non-positive integers, we obtain the sums of products identity for the Apostol?CBernoulli numbers which is an analogue of the classical sums of products identity for Bernoulli numbers dating back to Euler.     

Two identities for the Bernoulli–Euler numbers

Two identities for the Bernoulli and for the Euler numbers are derived. These identities involve two special cases of central combinatorial numbers. The approach is based on a set of differential identities for the powers of the secant. Generalizations of the Mittag–Leffler series for the secant are introduced and used to obtain closed-form expressions for the coefficients.     

Narayana numbers and Schur–Szeg? composition

In the present paper we find a new interpretation of Narayana polynomials N_n(x) which are the generating polynomials for the Narayana numbers where stands for the usual binomial coefficient, i.e. . They count Dyck paths of length n and with exactly k peaks, see e.g. [R.A. Sulanke, The Narayana distribution, in: Lattice Path Combinatorics and Applications (Vienna, 1998), J. Statist. Plann. Inference 101 (1–2) (2002) 311–326 (special issue)] and they appeared recently in a number of different combinatorial situations, see for e.g. [T. Doslic, D. Syrtan, D. Veljan, Enumerative aspects of secondary structures, Discrete Math. 285 (2004) 67–82; A. Sapounakis, I. Tasoulas, P. Tsikouras, Counting strings in Dyck paths, Discrete Math. 307 (2007) 2909–2924; F. Yano, H. Yoshida, Some set partitions statistics in non-crossing partitions and generating functions, Discrete Math. 307 (2007) 3147–3160]. Strangely enough Narayana polynomials also occur as limits as n→∞ of the sequences of eigenpolynomials of the Schur–Szeg? composition map sending (n−1)-tuples of polynomials of the form (x+1)ⁿ⁻¹(x+a) to their Schur–Szeg? product, see below. We present below a relation between Narayana polynomials and the classical Gegenbauer polynomials which implies, in particular, an explicit formula for the density and the distribution function of the asymptotic root-counting measure of the polynomial sequence {N_n(x)}.