Notes on a classic theorem of Erdős and Grünwald

We establish a companion result to a classic theorem of Erd?s and Grünwald on the maximum of the fundamental functions of Lagrange interpolation based on the Chebyshev nodes.     

Lattice-point examples for a question of Erdős

Here we establish a set of eight points in general position in the plane, i.e. no three on a line, no four on a circle, and they determine 7 distinct distances, so that, thei-th distance occursi times,i = 1, 2, , 7. The points are embedded in a triangular net, and the distances are not ordered by size or in any other way. We shall show that some known and unknown examples forn < 8 with the above properties may also be lattice points of a similar net.Research (partially) supported by the Hungarian National Foundation for Scientific Research (OTKA) grant, no. 1808.     

Kőnig’s edge-colouring theorem for all graphs

We show that the maximum degree of a graph G$G$ is equal to the minimum number of ocm sets covering  G$G$, where an ocm set is the vertex-disjoint union of elementary odd cycles and one matching, and a collection of ocm sets covers   G$G$ if every edge is in the matching of an ocm set or in some odd cycle of at least two ocm sets.     

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.     

A Question from a Famous Paper of Erdős

Given a convex body $K$ K , consider the smallest number $N$ N so that there is a point $P\in \partial K$ P ∈ ? K such that every circle centred at $P$ P intersects $\partial K$ ? K in at most $N$ N points. In 1946 Erd?s conjectured that $N=2$ N = 2 for all $K$ K , but there are convex bodies for which this is not the case. As far as we know there is no known global upper bound. We show that no convex body has $N=\infty $ N = ∞ and that there are convex bodies for which $N = 6$ N = 6 .     

An Erdős–Fuchs theorem for ordered representation functions

The Ramanujan Journal - Let $$k\ge 2$$ be a positive integer. We study concentration results for the ordered representation functions $$r^{{ \le }}_k({\mathcal {A}},n) = \# \big \{ (a_1 \le \dots...     

Erdős–Gyárfás conjecture for some families of Cayley graphs

The Paul Erd?s and András Gyárfás conjecture states that every graph of minimum degree at least 3 contains a simple cycle whose length is a power of two. In this paper, we prove that the conjecture holds for Cayley graphs on generalized quaternion groups, dihedral groups, semidihedral groups and groups of order \(p^3\).     

Erdős-Ginzburg-Ziv theorem for finite commutative semigroups

Let \(\mathcal{S}\) be a finite additively written commutative semigroup, and let \(\exp(\mathcal{S})\) be its exponent which is defined as the least common multiple of all periods of the elements in \(\mathcal{S}\) . For every sequence T of elements in \(\mathcal{S}\) (repetition allowed), let \(\sigma(T) \in\mathcal{S}\) denote the sum of all terms of T. Define the Davenport constant \(\mathsf{D}(\mathcal{S})\) of \(\mathcal{S}\) to be the least positive integer d such that every sequence T over \(\mathcal{S}\) of length at least d contains a proper subsequence T′ with σ(T′)=σ(T), and define \(\mathsf{E}(\mathcal{S})\) to be the least positive integer ? such that every sequence T over \(\mathcal{S}\) of length at least ? contains a subsequence T′ with \(|T|-|T'|= \lceil\frac{|\mathcal{S}|}{\exp(\mathcal{S})} \rceil \exp(\mathcal{S})\) and σ(T′)=σ(T). When \(\mathcal{S}\) is a finite abelian group, it is well known that \(\lceil\frac{|\mathcal{S}|}{\exp(\mathcal{S})} \rceil\exp (\mathcal{S})=|\mathcal{S}|\) and \(\mathsf{E}(\mathcal{S})=\mathsf{D}(\mathcal{S})+|\mathcal{S}|-1\) . In this paper we investigate whether \(\mathsf{E}(\mathcal{S})\leq \mathsf{D}(\mathcal{S})+ \lceil\frac{|\mathcal{S}|}{\exp(\mathcal {S})} \rceil \exp(\mathcal{S})-1\) holds true for all finite commutative semigroups \(\mathcal{S}\) . We provide a positive answer to the question above for some classes of finite commutative semigroups, including group-free semigroups, elementary semigroups, and archimedean semigroups with certain constraints.     

A fractional version of the Erdős-Faber-Lovász conjecture

LetH be any hypergraph in which any two edges have at most one vertex in common. We prove that one can assign non-negative real weights to the matchings ofH summing to at most |V(H)|, such that for every edge the sum of the weights of the matchings containing it is at least 1. This is a fractional form of the Erds-Faber-Lovász conjecture, which in effect asserts that such weights exist and can be chosen 0,1-valued. We also prove a similar fractional version of a conjecture of Larman, and a common generalization of the two.Supported in part by NSF grant MCS 83-01867, AFOSR Grant 0271 and a Sloan Research Fellowship     

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 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 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 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.