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.     

Vertex-minors and the Erdős–Hajnal conjecture

We prove that for every graph $H$, there exists $\epsilon >0$ such that every $n$-vertex graph with no vertex-minors isomorphic to $H$ has a pair of disjoint sets $A$, $B$ of vertices such that $\left|A\right|,\left|B\right|\ge \epsilon n$ and $A$ is complete or anticomplete to $B$. We deduce this from recent work of Chudnovsky, Scott, Seymour, and Spirkl (2018). This proves the analog of the Erd?s–Hajnal conjecture for vertex-minors.     

On a problem of Erdős and Moser

A set A of vertices in an r-uniform hypergraph \(\mathcal H\) is covered in \(\mathcal H\) if there is some vertex \(u\not \in A\) such that every edge of the form \(\{u\}\cup B\), \(B\in A^{(r-1)}\) is in \(\mathcal H\). Erd?s and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.     

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.     

On a problem of Erdős and Graham

In this paper we provide bounds for the size of the solutions of the Diophantine equation

$$\begin{aligned} x(x+1)(x+2)(x+3)(x+m)(x+m+1)(x+m+2)(x+m+3)=y^2, \end{aligned}$$

where \(4\le m\in \mathbb {N}\) is a parameter. We also determine all integral solutions for \(1\le m\le 10^6.\)

     

On a problem of Erdős and Rado

We give some improved estimates for the digraph Ramsey numbersr(K _n ^* ,L _m ), the smallest numberp such that any digraph of orderp either has an independent set ofn vertices or contains a transitive tournament of orderm. By results of Baumgartner and of Erdős and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal κ and positive integersn andm, find the smallest numberp such that

On a Question of Erdős and Ulam

Ulam asked in 1945 if there is an everywhere dense rational set, i.e., 1 a point set in the plane with all its pairwise distances rational. Erdős conjectured that if a set S has a dense rational subset, then S should be very special. The only known types of examples of sets with dense (or even just infinite) rational subsets are lines and circles. In this paper we prove Erdős’ conjecture for algebraic curves by showing that no irreducible algebraic curve other than a line or a circle contains an infinite rational set.     

On a problem of Erdős

Let s≥2 be an integer. Denote by f ₁(s) the least integer so that every integer l>f ₁(s) is the sum of s distinct primes. Erd?s proved that f ₁(s)<p ₁+p ₂+?+p _s +Cslogs, where p _i is the ith prime and C is an absolute constant. In this paper, we prove that f ₁(s)=p ₁+p ₂+?+p _s +(1+o(1))slogs=p ₂+p ₃+?+p _s+1+o(slogs). This answers a question posed by P. Erd?s.     

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     

p-adic logarithmic forms and a problem of Erdős

For any natural number m(>1) let P(m) denote the greatest prime divisor of m. By the problem of Erd?s in the title of the present paper we mean the general version of his problem, that is, his conjecture from 1965 that $$\frac{P(2^n-1)}{n} \to \infty \quad {\rm as}\, n \to \infty$$ (see Erd?s [10]) and its far-reaching generalization to Lucas and Lehmer numbers. In the present paper the author delivers three refinements upon Yu [40] required by C. L. Stewart for solving completely the problem of Erd?s (see Stewart [25]). The author gives also some remarks on the solution of this problem, aiming to be more streamlined with respect to the p-adic theory of logarithmic forms.     

A conjecture of Erdős and Reddy and the rational approximation of Mittag-Leffler type functions

Пусть \(f(z) = \mathop \sum \limits_{k = 0}^\infty a_k z^k ,a_0 \ne 0, a_k \geqq 0 (k \geqq 0)\) — целая функци я,π _n — класс обыкновен ных алгебраических мног очленов степени не вы ше \(n,a \lambda _n (f) = \mathop {\inf }\limits_{p \in \pi _n } \mathop {\sup }\limits_{x \geqq 0} |1/f(x) - 1/p(x)|\) . П. Эрдеш и А. Редди высказали пр едположение, что еслиf(z) имеет порядок ?ε(0, ∞) и $$\mathop {\lim sup}\limits_{n \to \infty } \lambda _n^{1/n} (f)< 1, TO \mathop {\lim inf}\limits_{n \to \infty } \lambda _n^{1/n} (f) > 0$$ В данной статье показ ано, что для целой функ ции $$E_\omega (z) = \mathop \sum \limits_{n = 0}^\infty \frac{{z^n }}{{\Gamma (1 + n\omega (n))}}$$ , где выполняется $$\lambda _n^{1/n} (E_\omega ) \leqq \exp \left\{ { - \frac{{\omega (n)}}{{e + 1}}} \right\}$$ , т.е. $$\mathop {\lim sup}\limits_{n \to \infty } \lambda _n^{1/n} (E_\omega ) \leqq \exp \left\{ { - \frac{1}{{\rho (e + 1)}}} \right\}< 1, a \mathop {\lim inf}\limits_{n \to \infty } \lambda _n^{1/n} (E_\omega ) = 0$$ . ФункцияE _ω (z) имеет порядок ?.     

An Analogue of Hajós' Theorem for the Circular Chromatic Number (II)

This paper designs a set of graph operations, and proves that for 2k/d<3, starting from K_k/_d, by repeatedly applying these operations, one can construct all graphs G with _c(G)k/d. Together with the result proved in [20], where a set of graph operations were designed to construct graphs G with _c(G)k/d for k/d3, we have a complete analogue of Hajós' Theorem for the circular chromatic number. This research was partially supported by the National Science Council under grant NSC 89-2115-M-110-003     

Proof of the Erdős–Faudree Conjecture on Quadrilaterals

In this paper, we prove the Erdős–Faudree’s conjecture: If G is a graph of order 4k and the minimum degree of G is at least 2k then G contains k disjoint cycles of length 4.     

Gap,cosum and product properties of the θ′ bound on the clique number

In a paper published in 1978, McEliece, Rodemich and Rumsey improved the Lovász bound θ for the maximum clique problem. This strengthening has become well known under the name Lovász–Schrijver bound and is usually denoted by θ′. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound and the actual clique number can be arbitrarily large, we establish homomorphy results for this bound under cosums and products of graphs. In particular we show that for circulant graphs of prime order there must be a positive gap between the clique number and the bound.     

On An Extremal Hypergraph Problem Of Brown, Erdős And Sós

Let f_r(n,v,e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi and of Erdős, Frankl and R?dl, we partially resolve a problem raised by Brown, Erdős and Sós in 1973, by showing that for any fixed 2≤k<r, we have

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.