Search

If two squares with no interior point in common are drawn inside a unit square then prove that the sum of their side-lengths is at most 1.This problem was posed in the 1930s by Paul Erdős [1]. It is the simplest case of a still unsolved conjecture.If k2 + 1 squares with no interior point in common are drawn inside a unit square then the maximum possible sum of their side-lengths is k [2].We shall use the notation S(n) to denote the maximum possible sum of the side-lengths for n squares drawn with no interior point in common inside a unit square. The main aim of this article will be to develop an approach to the study of the function S which will give surprisingly simple proofs of a number of known results. This approach will then be used to prove a new result about the asymptotic behaviour of S.

Let s > k ≧ 2 be integers. It is shown that there is a positive real e = e(k) such that for all integers n satisfying (s + 1)k ≦ n < (s + 1)(k + e) every k-graph on n vertices with no more than s pairwise disjoint edges has at most $$\left( {\begin{array}{*{20}{c}} {\left( {s + 1} \right)k - 1} \\ k \end{array}} \right)$$ edges in total. This proves part of an old conjecture of Erdős.

Let k ⩾ 2 , s ⩾ 2 be positive integers. Let [n] be an n-element set, n ⩾ k s . Subsets of 2 [ n ] are called families. If F ⊂ ( [ n ] k ) , then it is called k-uniform. What is the maximum size e k ( n , s ) of a k-uniform family without s pairwise disjoint members? The well-known Erdős Matching Conjecture would provide the answer for all n, k, s in the above range. For n > 2 k s it is known that the maximum is attained by A 1 ( T ) : = { A ⊂ [ n ] : | A | = k , A ∩ T ≠ ∅ } for some fixed ( s − 1 )-element set T ⊂ X . We discuss recent progress on this problem. In particular, our recent stability result states that for n > ( 2 + o ( 1 ) ) k s and a k-uniform family F , F ⊈ A 1 ( T ) , then | F | is considerably smaller. This result is applied to obtain the corresponding anti-Ramsey numbers in a wide range. Removing the condition of uniformness, we arrive at another classical problem of Erdős, which was solved by Kleitman for n ≡ 0 or −1 (mod s). We succeeded in resolving this long-standing problem for n ≡ − 2 ( mod s ) via a new averaging technique which might prove useful in various other situations.

Using undergraduate calculus, we give a direct elementary proof of a sharp Markov-type inequality ||p'||[−1,1] ≤ 1/2||p||[−1,1] 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.Erde 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.

In this paper, by employing linear algebra methods we obtain the following main results: (i)Let L={l1,l2,...,ls} and K={k1,k2,...,kr} be two disjoint subsets of {0,1,...,n} such that n>s−2r+1+maxK. Suppose that F={F1,F2,...,Fm} is a family of subsets of [n]:={1,2,...,n} such that |Fi∩Fj|∈L for every pair i≠j and |Fi|∈K for every i. Then m⩽n−1s+n−1s−1+⋯+n−1s−2r+1. Furthermore, we extend this theorem to k-wise L-intersecting and obtain the corresponding result on two cross L-intersecting families. These results show that Snevily's conjectures proposed by Snevily (2003) are true under some restricted conditions. This result also gets an improvement of a theorem of Liu and Hwang (2013). (ii)Let p be a prime and let L={l1,l2,...,ls} and K={k1,k2,...,kr} be two subsets of {1,2,...,p−1} such that minK>s−2r+1, or r(s−r+1)⩽p−1 and n⩾s+maxK. Suppose that F={F1,F2,...,Fm} is a family of subsets of [n] such that (1) |Fi−Fj|(modp)∈L for every pair i≠j; (2) |Fi|(modp)∈K for every i. Then m⩽n−1s+n−1s−1+⋯+n−1s−2r+1. This result improves the existing upper bound substantially.

Let $\mathcal{H}=(V,\mathcal{E})$ be an $r$-uniform hypergraph on $n$ vertices and fix a positive integer $k$ such that $1\le k\le r$. A $k$-matching of $\mathcal{H}$ is a collection of edges $\mathcal{M}\subset \mathcal{E}$ such that every subset of $V$ whose cardinality equals $k$ is contained in at most one element of $\mathcal{M}$. The $k$-matching number of $\mathcal{H}$ is the maximum cardinality of a $k$-matching. A well-known problem, posed by Erdős, asks for the maximum number of edges in an $r$-uniform hypergraph under constraints on its $1$-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices subject to the constraint that its $k$-matching number is strictly less than $a$. The problem can also be seen as a generalization of the well-known $k$-intersection problem. We propose candidate hypergraphs for the solution of this problem, and show that the extremal hypergraph is among this candidate set when $n\ge 4r\binom{r}{k}^2\cdot a$.

The 25-year old LCGD Conjecture is that the genus distribution of every graph is log-concave. We present herein a new topological conjecture, called the Local Log-Concavity Conjecture. We also present a purely combinatorial conjecture, which we prove to be equivalent to the Local Log-Concavity Conjecture. We use the equivalence to prove the Local Log-Concavity Conjecture for graphs of maximum degree four. We then show how a formula of David Jackson could be used to prove log-concavity for the genus distributions of various partial rotation systems, with straight-forward application to proving the local log-concavity of additional classes of graphs. We close with an additional conjecture, whose proof, along with proof of the Local Log-Concavity Conjecture, would affirm the LCGD Conjecture.

Text Let p and q be distinct primes. We show that digits of the base q expansions of p n are equidistributed on average (averaging over n). More precisely, for fixed m, we first prove a result for the first m q-adic bits of p n (averaging over n), then taking the large m limit we show equidistribution. A non-averaged version of this result would imply a conjecture of Erdős which states that there are only finitely many n such that the base 3 expansion of 2 n omits a 2. We prove our results by proving a nonexistence theorem for “higher Wieferich primes”. Video For a video summary of this paper, please visit http://youtu.be/L_dZkdQwxVI .

A classical conjecture of Erdős and Szekeres states that, for every integer k ≥ 2 , every set of 2 k − 2 + 1 points in the plane in general position contains k points in convex position. In 2006, Peters and Szekeres introduced the following stronger conjecture: every red-blue coloring of the edges of the ordered complete 3-uniform hypergraph on 2 k − 2 + 1 vertices contains an ordered subhypergraph with k vertices and k − 2 edges, which is a union of a red monotone path and a blue monotone path that are vertex disjoint except for their two common end-vertices. Applying a state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.

In this article, we prove that infinite number of integers satsify Erdős–Woods conjecture. Moreover, it follows that the number of natural numbers ≤ x satisfies Erdős–Woods conjecture with k = 2 is at least c x/(logx) for some positive constant c > 2.

The Erdős-Faber-Lovasz conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovasz conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that can be proved in the spirit of the Kahn-Seymour result, and others that are equivalent to the original conjecture.

Paul Erdős (26 March 1913—20 September 1996) was a mathematicianpar excellencewhose results and initiatives have had a large impact and made a strong imprint on the doing of and thinking about mathematics. A mathematician of alacrity, detail, and collaboration, Erdős in his six decades of work moved and thought quickly, entertained increasingly many parameters, and wrote over 1500 articles, the majority with others. Hismodus operandiwas to drive mathematics through cycles of problem, proof, and conjecture, ceaselessly progressing and ever reaching, and hismodus vivendiwas to be itinerant in the world, stimulating and interacting about mathematics at every port and capital.

Schinzel showed that the set of primes that divide some value of the classical partition function is infinite. For a wide class of sets 𝒜, we prove an analogous result for the function p𝒜(n) that counts partitions of n into terms belonging to 𝒜.

The Erdős–Sos Conjecture states that if G is a graph with average degree more than k − 1 , then G contains every tree with k edges. A spider is a tree with at most one vertex of degree more than 2. In this paper, we prove that if G is a graph on n vertices with average degree more than k − 1 , then G contains every spider with k edges, where k ≥ n + 5 2 .

We show that for every e > 0 there exist δ > 0 and n 0 ∈ N such that every 3-uniform hypergraph on n ⩾ n 0 vertices with the property that every k-vertex subset, where k ⩾ δ n , induces at least ( 1 4 + ϵ ) ( k 3 ) edges, contains K 4 − as a subgraph, where K 4 − is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdős and Sos. The constant 1/4 is the best possible.

The main result is the following. Let F be a family of k-subsets of an n-set, containing no s+1 pairwise disjoint edges. Then for n>=(2s+1)k-s one has |F|=

Fifty years ago Erdos asked to determine the minimum number of k-cliques in a graph on n vertices with independence number less than l. He conjectured that this minimum is achieved by the disjoint union of l-1 complete graphs of size nl-1. This conjecture was disproved by Nikiforov, who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size n2. In this paper we solve Erdos@? problem for (k,l)=(3,4) and (k,l)=(4,3). Using stability arguments we also characterize the precise structure of extremal examples, confirming Erdos@? conjecture for (k,l)=(3,4) and showing that a blow-up of a 5-cycle gives the minimum for (k,l)=(4,3).

The Erdős-Sós Conjecture states that if ?$G$? is a simple graph of order ?$n$? with average degree more than ?$k-2$?, then ?$G$? contains every tree of order ?$k$?. In this paper, we prove that Erdős-Sós Conjecture is true for ?$n=k+4$?. Erdős-Sósova domneva pravi, da če je ?$G$? enostaven graf reda ?$n$? s povprečno stopnjo večjo od ?$k-2$?, potem ?$G$? vsebuje vsako drevo reda ?$k$?. V tem članku pokaževa, da je Erdős-Sósova domneva resnična za ?$n=k+4$?.

International audience; In the context of a conjecture of Erdős and Gyárfás, we consider, for any $q ≥ 2$, the existence of q-power cycles (i.e. with length a power of q) in cubic graphs. We exhibit constructions showing that, for every $q ≥ 3$, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case $q = 2$ (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose only 2-power cycles have length 4 only, or 8 only.

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.

We prove that a Kueker theory with infinite dcl(∅) does not have the strict order property and that strongly minimal types are dense: any non-algebraic formula is contained in a strongly minimal type.

The Ramsey number r ( G ) of a graph G is the minimum N such that every red–blue coloring of the edges of the complete graph on N vertices contains a monochromatic copy of G . Determining or estimating these numbers is one of the central problems in combinatorics. One of the oldest results in Ramsey Theory, proved by Erdős and Szekeres in 1935, asserts that the Ramsey number of the complete graph with m edges is at most 2 O ( m ) . Motivated by this estimate Erdős conjectured, more than a quarter century ago, that there is an absolute constant c such that r ( G ) ⩽ 2 c m for any graph G with m edges and no isolated vertices. In this short note we prove this conjecture.

Properties of the Erdős measure and the invariant Erdős measure for the golden ratio and all values of the Bernoulli parameter are studied. It is proved that a shift on the two-sided Fibonacci compact set with invariant Erdős measure is isomorphic to the integral automorphism for a Bernoulli shift with countable alphabet. An effective algorithm for calculating the entropy of an invariant Erdős measure is proposed. It is shown that, for certain values of the Bernoulli parameter, this algorithm gives the Hausdorff dimension of an Erdős measure to 15 decimal places.

Let σA(n)=∣{(a,a′)∈A2:a+a′=n}∣, where $n\in \mathbb {N}$ and A is a subset of $\mathbb {N}$. Erdös and Turán conjectured that, for any basis A of $\mathbb {N}$, σA(n) is unbounded. In 1990, Ruzsa constructed a basis $A\subset \mathbb {N}$ for which σA(n) is bounded in the square mean. In this paper, based on Ruzsa’s method, we show that there exists a basis A of $\mathbb {N}$ satisfying $\sum _{n\leq N}\sigma _A(n)^2\leq 1\,449\,757\,928N$ for large enough N.

During the last years both Erdős space and complete Erdős space were topologically characterized by Dijkstra and van Mill. Applications include results about Erdős type spaces in l p -spaces as well as results about Polishable ideals on ω . We present an unifying theorem in terms of sets with a reflexive relation that among other things contains these apparently dissimilar results as special cases.

It is conjectured by Erdős, Graham and Spencer that if 1 ⩽ a 1 ⩽ a 2 ⩽ ⋯ ⩽ a s with ∑ i = 1 s 1 / a i n − 1 / 30 , then this sum can be decomposed into n parts so that all partial sums are ⩽1. This is not true for ∑ i = 1 s 1 / a i = n − 1 / 30 as shown by a 1 = 2 , a 2 = a 3 = 3 , a 4 = ⋯ = a 5 n − 3 = 5 . In 1997, Sandor proved that Erdős–Graham–Spencer conjecture is true for ∑ i = 1 s 1 / a i ⩽ n − 1 / 2 . In this paper, we reduce Erdős–Graham–Spencer conjecture to finite calculations and prove that Erdős–Graham–Spencer conjecture is true for ∑ i = 1 s 1 / a i ⩽ n − 1 / 3 . Furthermore, it is proved that Erdős–Graham–Spencer conjecture is true if ∑ i = 1 s 1 / a i n − 1 / ( log n + log log n − 2 ) and no partial sum (certainly not a single term) is the inverse of an positive integer.

Montgomery and Vaughan improved a theorem of Erdős and Fuchs for an arbitrary sequence. Sarkozy extended this theorem of Erdős and Fuchs for two arbitrary sequences which are "near" in a certain sense. Using the idea of Jurkat (differentiation of the generating function), we will extend similarly the result of Montgomery and Vaughan for "sufficiently near" sequences.

Erdős and Pach (1983) asked if there is some constant C > 0 such that for any graph G on Ck ln ⁡ k vertices either G or its complement G ¯ has an induced subgraph on k vertices with minimum degree at least 1 2 ( k − 1 ) . They showed that the above statement holds with Ck 2 in place of Ck ln ⁡ k but that it does not hold with C k ln ⁡ k / ln ⁡ ln ⁡ k . We show that it holds with Ck ln 2 ⁡ k , answering their question up to a ln ⁡ k factor.

The Erdős number (EN) for collaborative papers among mathematicians was defined as indicating the topological distance in the graph depicting the co-authorship relations, i. e., EN = 1 for all co-authors of Paul Erdős; EN = 2 for their co-authors who did not publish jointly with Erdős; etc. A refinement of this notion uses resistance distances leading to rational Erdős numbers (REN), which (as indicated by their name) are rational numbers. For acyclic graphs, EN = REN, but for graphs with circuits these numbers differ. Further refinements are possible using weighted edges in the co-authorship graph according to the number of jointly authored papers.

To better understand the distribution of gaps between k-free numbers, Erdős posed the problem of establishing an asymptotic formula for the sum of the powers of the lengths of the gaps between k-free numbers. This paper generalizes the problem of Erdős by considering moments of gaps between positive integers m for which f(m) is k-free. Here, f(x) denotes an irreducible polynomial with integer coeficients with some necessary conditions imposed on it. Some results in this general setting are obtained that are analogous to those that have been obtained for the original problem of Erdős.

In connection with a characterization ofc logn within the class of additive arithmetic functions, i.e. such thatf (mn)=f(m)+f(n), which has been conjectured by P. Erdős in 1946 and is still unproved, we outline some subsequent researches involving various tools and standpoints, and we report some expressive results either lying close to that conjecture or revealing a similar spirit.

Let \(G_{n}(p_{n}) = ([n],E_{n}(p_{n}))\) denote the Erdős–Renyi graph of size n which was introduced in Chap. 9. As in Chap. 9, the generic notation P for probability and E for expectation will be used in this chapter.