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.     

Tauberian Theorem of Erdős Revisited

Dedicated to the memory of Paul Erdős In connection with the elementary proof of the prime number theorem, Erdős obtained a striking quadratic Tauberian theorem for sequences. Somewhat later, Siegel indicated in a letter how a powerful "fundamental relation" could be used to simplify the difficult combinatorial proof. Here the author presents his version of the (unpublished) Erdős–Siegel proof. Related Tauberian results by the author are described. Received December 20, 1999     

Variants of the Erdős–Szekeres and Erdős–Hajnal Ramsey problems

Given integers $\ell ,n$, the $\ell$th power of the path $P_n$ is the ordered graph $P_n^{\ell }$ with vertex set $v_1<v_2<\cdots <v_n$ and all edges of the form $v_i{v}_j$ where $|i-j|\le \ell$. The Ramsey number $r(P_n^{\ell },P_n^{\ell })$ is the minimum $N$ such that every 2-coloring of $\left(\genfrac{}{}{0ex}{}{\left[N\right]}{2}\right)$ results in a monochromatic copy of $P_n^{\ell }$. It is well-known that $r(P_n^1,P_n^1)={(n-1)}^2+1$. For $\ell >1$, Balko–Cibulka–Král–Kynčl proved that $r(P_n^{\ell },P_n^{\ell })<c_{\ell }{n}^{128\ell }$ and asked for the growth rate for fixed $\ell$. When $\ell =2$, we improve this upper bound substantially by proving $r(P_n^2,P_n^2)<c{n}^{19.5}$. Using this result, we determine the correct tower growth rate of the $k$-uniform hypergraph Ramsey number of a $(k+1)$-clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erdős–Hajnal hypergraph Ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal.     

Ramsey Theory,integer partitions and a new proof of the Erdős–Szekeres Theorem

Let H be a k  -uniform hypergraph whose vertices are the integers 1,…,N$1,\dots ,N$. We say that H contains a monotone path of length n   if there are _x1<_x2<?<_xn+k−1$x_1<x_2<?<x_{n+k-1}$ so that H contains all n   edges of the form {_xi,_xi+1,…,_xi+k−1}$\{x_i,x_{i+1},\dots ,x_{i+k-1}\}$. Let _Nk(q,n)$N_k(q,n)$ be the smallest integer N so that every q-coloring of the edges of the complete k-uniform hypergraph on N vertices contains a monochromatic monotone path of length n  . While the study of _Nk(q,n)$N_k(q,n)$ for specific values of k and q   goes back (implicitly) to the seminal 1935 paper of Erd?s and Szekeres, the problem of bounding _Nk(q,n)$N_k(q,n)$ for arbitrary k and q was studied by Fox, Pach, Sudakov and Suk.     

A Weighted Erdős-Ginzburg-Ziv Theorem

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct so that they can be considered as sets. If S is a sequence of m+n−1 elements from a finite abelian group G of order m and exponent k, and if is a sequence of integers whose sum is zero modulo k, then there exists a rearranged subsequence of S such that . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when m = n and w_i = 1 for all i, and confirms a conjecture of Y. Caro. Furthermore, we in part verify a related conjecture of Y. Hamidoune, by showing that if S has an n-set partition A=A₁, . . .,A_n such that |w_iA_i| = |A_i| for all i, then there exists a nontrivial subgroup H of G and an n-set partition A′ =A′₁, . . .,A′_n of S such that and for all i, where w_iA_i={w_ia_i |a_i∈A_i}.     

Erdős–Szekeres Theorem for Lines

According to the Erd?s–Szekeres theorem, for every n, a sufficiently large set of points in general position in the plane contains n in convex position. In this note we investigate the line version of this result, that is, we want to find n lines in convex position in a sufficiently large set of lines that are in general position. We prove almost matching upper and lower bounds for the minimum size of the set of lines in general position that always contains n in convex position. This is quite unexpected, since in the case of points, the best known bounds are very far from each other. We also establish the dual versions of many variants and generalizations of the Erd?s–Szekeres theorem.     

An extension of the Erdős-Stone theorem

LetK _p(u₁, ..., u_p) be the completep-partite graph whoseith vertex class hasu _i vertices (lip). We show that the theorem of Erds and Stone can be extended as follows. There is an absolute constant >0 such that, for allr1, 0<1 and=">1/r, every graphG=G ⁿ of sufficiently large order |G|=n with at least

On the proof of Erdős’ inequality

Using undergraduate calculus, we give a direct elementary proof of a sharp Markov-type inequality \({\left\| {p'} \right\|_{\left[ { - 1,1} \right]}} \leqslant \frac{1}{2}{\left\| p \right\|_{\left[ { - 1,1} \right]}}\) for a constrained polynomial p of degree at most n, initially claimed by P. Erd?s, which is different from the one in the paper of T.Erdélyi (2015). Whereafter, we give the situations on which the equality holds. On the basis of this inequality, we study the monotone polynomial which has only real zeros all but one outside of the interval (?1, 1) and establish a new asymptotically sharp inequality.     

Towards a de Bruijn–Erdős Theorem in the L_1-Metric

A well-known theorem of de Bruijn and Erd?s states that any set of $n$ non-collinear points in the plane determines at least $n$ lines. Chen and Chvátal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of $n$ points in the plane with the $L_1$ metric, provided that no two points share their $x$ - or $y$ -coordinate. In this case, either there is a line that contains all $n$ points, or $X$ induces at least $n$ distinct lines. If points of $X$ are allowed to share their coordinates, then either there is a line that contains all $n$ points, or $X$ induces at least $n/37$ distinct lines.     

Erdős Type Problems in Modules over Cyclic Rings

In the present paper, we study various Erd?s type geometric problems in the setting of the integers modulo q, where \(q=p^l\) is an odd prime power. More precisely, we prove certain results about the distribution of triangles and triangle areas among the points of \(E\subset \mathbb {Z}_q^2\).     

On the General Taylor Theorem and its Applications in Solving Non-lin-ear Problems

ＯｎｔｈｅＧｅｎｅｒａｌＴａｙｌｏｒＴｈｅｏｒｅｍａｎｄｉｔｓＡｐｐｌｉｃａｔｉｏｎｓｉｎＳｏｌｖｉｎｇＮｏｎｌｉｎｅａｒＰｒｏｂｌｅｍｓ１１ＴｈｅｐａｐｅｒｗａｓｒｅｃｅｉｖｅｄｏｎＪｕｌｙ．２０，１９９７ＳｈｉＪｕｎＬＩＡＯ（Ｄｅｐａｒｔｍｅ...     

A General Darling–Erdős Theorem in Euclidean Space

We provide an improved version of the Darling–Erd?s theorem for sums of i.i.d. random variables with mean zero and finite variance. We extend this result to multidimensional random vectors. Our proof is based on a new strong invariance principle in this setting which has other applications as well such as an integral test refinement of the multidimensional Hartman–Wintner LIL. We also identify a borderline situation where one has weak convergence to a shifted version of the standard limiting distribution in the classical Darling–Erd?s theorem.     

Stability in the Erdős–Gallai Theorem on cycles and paths,II

The Erd?s–Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k?1)(n?1)$ edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e\left(G\right)\le max\{h(n,k,2),h(n,k,?\frac{k?1}{2}?)\}$, where $h(n,k,a)?\left(\genfrac{}{}{0ex}{}{k?a}{2}\right)+a(n?k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,?\frac{k?1}{2}?)$ edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex 2-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e\left(G\right)\le max\{h(n,k,3),h(n,k,\frac{k?3}{2})\}$. The upper bound for $e\left(G\right)$ here is tight.     

A Decomposition Theorem for the Solutions to the Interface Problems of Quasi-Linear Elliptic Equations

Interface problems for second order quasi-linear elliptic partial differential equations in a two-dimensional space are studied. We prove that each weak solution can be decomposed into two parts near singular points, one of which is a finite sum of functions of the form cr^a log^m rφ(θ), where the coefficients c depend on the H^1-norm of the solution, the C^(0,δ) -norm of the solution, and the equation only; and the other one of which is a regular one, the norm of which is also estimated.