On a Conjecture of Erdős,Gallai, and Tuza

Erd?s, Gallai, and Tuza posed the following problem: given an n‐vertex graph G, let denote the smallest size of a set of edges whose deletion makes G triangle‐free, and let denote the largest size of a set of edges containing at most one edge from each triangle of G. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erd?s–Gallai–Tuza conjecture. We also show that always , where m is the number of edges in G; this bound is sharp in several notable cases.     

On a generalization of a theorem of Erdős and Fuchs

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by r_k(A,n) the number of solutions of a_i1+a_i2++a_ik≤n. Montgomery and Vaughan proved that r₂(A,n)=cn+o(n^1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2.     

On an anti‐Ramsey problem of Burr,Erdős,Graham, and T. Sós

Given a graph L, in this article we investigate the anti‐Ramsey number χ_S(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC). In 7 among many other interesting results and problems, Burr, Erd?s, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On a problem of Duke–Erdős–Rödl on cycle-connected subgraphs

In this short note, we prove that for β<1/5 every graph G with n vertices and n^2−β edges contains a subgraph G^′ with at least cn^2−2β edges such that every pair of edges in G^′ lie together on a cycle of length at most 8. Moreover edges in G^′ which share a vertex lie together on a cycle of length at most 6. This result is best possible up to the constant factor and settles a conjecture of Duke, Erdős, and Rödl.     

Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

Let be an integer, be the set of vertices of degree at least 2k in a graph G , and be the set of vertices of degree at most in G . In 1963, Dirac and Erd?s proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles.     

Generalization of a theorem of Erdős and Rényi on Sidon sequences

Erd?s and Rényi claimed and Vu proved that for all h ≥ 2 and for all ? > 0, there exists g = g_h(?) and a sequence of integers A such that the number of ordered representations of any number as a sum of h elements of A is bounded by g, and such that |A ∩ [1,x]| ? x^1/h‐?. We give two new proofs of this result. The first one consists of an explicit construction of such a sequence. The second one is probabilistic and shows the existence of such a g that satisfies g_h(?) ? ?^?1, improving the bound g_h(?) ? ?^?h+1 obtained by Vu. Finally we use the “alteration method” to get a better bound for g₃(?), obtaining a more precise estimate for the growth of B₃[g] sequences. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Two Questions of Erdős on Hypergraphs above the Turán Threshold

For ordinary graphs it is known that any graph G with more edges than the Turán number of must contain several copies of , and a copy of , the complete graph on vertices with one missing edge. Erd?s asked if the same result is true for , the complete 3‐uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for . For the second property, that of containing a , we show that for the answer is negative for all large n as well, by proving that the Turán density of is greater than that of .     

The Erdős‐Sós Conjecture for trees of diameter four

The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005     

An extension of the Erdős‐Tetali theorem

Given a sequence , let r_??,h(n) denote the number of ways n can be written as the sum of h elements of ??. Fixing h ≥ 2, we show that if f is a suitable real function (namely: locally integrable, O‐regularly varying and of positive increase) satisfying then there must exist with for which r_{??,h + ?}(n) = Θ(f(n)^{h + ?}/n) for all ? ≥ 0. Furthermore, for h = 2 this condition can be weakened to . The proof is somewhat technical and the methods rely on ideas from regular variation theory, which are presented in an appendix with a view towards the general theory of additive bases. We also mention an application of these ideas to Schnirelmann's method.     

On a problem of cyclic permutations of integers

We consider a problem of cyclic permutations of integers arising in the field of memory technologies for computer systems, and we solve it in the more general case of reals.     

On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs

Given a graph Γ_n=(V,E) on n vertices and m edges, we define the Erd?s‐Rényi graph process with host Γ_n as follows. A permutation e₁,…,e_m of E is chosen uniformly at random, and for t ≤ m we let Γ_n,t=(V,{e₁,…,e_t}). Suppose the minimum degree of Γ_n is δ(Γ_n) ≥ (1/2+ε)n for some constant ε>0. Then with high probability (An event holds with high probability (whp) if as n→∞.), Γ_n,t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γ_n,p be the Erd?s‐Rényi subgraph of Γ_n, obtained by retaining each edge independently with probability p. When δ(Γ_n) ≥ (1/2+ε)n, we provide a threshold for Hamiltonicity in Γ_n,p.     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007     

On a transport problem and monoids of non-negative integers

A problem about how to transport profitably a group of cars leads us to studying the set T formed by the integers n such that the system of inequalities, with non-negative integer coefficients,

$$\begin{aligned} a_1x_1 +\cdots + a_px_p + \alpha \le n \le b_1x_1 +\cdots + b_px_p - \beta \end{aligned}$$

has at least one solution in \({\mathbb N}^p\). We prove that \(T\cup \{0\}\) is a submonoid of \(({\mathbb N},+)\) and, moreover, we give algorithmic processes to compute T.

     

A Relaxed Version of the Erdős–Lovász Tihany Conjecture

The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G ₁ and G ₂ such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G ₁ and G ₂ of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G .     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

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 with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

On the exponential sum—product problem

Let g be an element of order T over a finite field Fp of p elements, where p is a prime. We show that for a very wide class of sets A, B ∈ {1, . . . , T} at least one of the sets

{gab:a∈A,b∈B}and{ga+gb:a∈A,b∈B}     

On integers which are the sum of a power of 2 and a polynomial value

Here, we show that if f (x) ∈ ?[x] has degree at least 2 then the set of integers which are of the form 2 ^k + f (m) for some integers k ≥ 0 and m is of asymptotic density 0. We also make some conjectures and prove some results about integers not of the form |2 ^k ± m ^a (m ? 1)|.     

Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles

According to the classical Erd?s–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd?s–Pósa theorem.