The Erdös–Hajnal Conjecture—A Survey

The Erdös–Hajnal conjecture states that for every graph H, there exists a constant such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least . This article is a survey of some of the known results on this conjecture.     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

Excluding pairs of tournaments

The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H₁ and H₂, there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H, there exists a constant such that every ‐free tournament T, where stands for the complement of H, has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.     

Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement

Erd?s and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^?(H) for some ?(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Extending the Erdős–Ko–Rado theorem

Let be a k‐uniform hypergraph on n vertices. Suppose that holds for all . We prove that the size of is at most if satisfies and n is sufficiently large. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs

The Loebl–Komlós–Sós conjecture states that for any integers k and n, if a graph G on n vertices has at least n/2 vertices of degree at least k, then G contains as subgraphs all trees on k+1 vertices. We prove this conjecture in the case when k is linear in n, and n is sufficiently large.     

The Erdős–Pósa Property for Long Circuits

For an integer ? at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ?, then there is a set X of at most vertices that intersects all circuits of length at least ?. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erd?s–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ? vertices always suffice.     

Tree embeddings

We give a general theorem on embedding trees in graphs with certain expanding properties. As an application, we show that for r = ⌊t/18⌋, any graph with average degree greater than t − 1 that does not contain a copy of K_2,r contains every tree with t edges as a subgraph. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 121–130, 2001     

Modified ‐expansion method for finding exact wave solutions of the coupled Klein–Gordon–Schrödinger equation

The coupled Klein–Gordon–Schrödinger equation is reduced to a nonlinear ordinary differential equation (ODE) by using Lie classical symmetries, and various solutions of the nonlinear ODE are obtained by the modified ‐expansion method proposed recently. With the aid of solutions of the nonlinear ODE, more explicit traveling wave solutions of the coupled Klein–Gordon–Schrödinger equation are found out. The traveling wave solutions are expressed by the hyperbolic functions, trigonometric functions, and rational functions. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

Efficient approximation algorithm for the Schrödinger–Possion system

In this article, we study an efficient approximation algorithm for the Schrödinger–Possion system arising in the resonant tunneling diode (RTD) structure. By following the classical Gummel iterative procedure, we first decouple this nonlinear system and prove the convergence of the iteration method. Then via introducing a novel spatial discrete method, we solve efficiently the decoupled Schrödinger and Possion equations with discontinuous coefficients on no‐uniform meshes at each iterative step, respectively. Compared with the traditional ones, the algorithm considered here not only has a less restriction on the discrete mesh, but also is more accurate. Finally, some numerical experiments are shown to confirm the efficiency of the proposed algorithm.     

A conservative compact difference scheme for the coupled Klein–Gordon–Schrödinger equation

In this article, a conservative compact difference scheme is presented for the periodic initial‐value problem of Klein–Gordon–Schrödinger equation. On the basis of some inequalities about norms and the priori estimates, convergence of the difference solution is proved with order O(h⁴ +τ ²) in maximum norm. Numerical experiments demonstrate the accuracy and efficiency of the compact scheme. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

On 1–dimensional dissipative Schrödinger–type operators their dilations and eigenfunction expansions

In the present paper we characterize the spectrum of small transverse vibrations of an inhomogeneous string with the left end fixed and the right one moving with damping in the direction orthogonal to the equilibrium position of the string. The density of the string is supposed to be smooth and strictly positive everywhere except of an interval of zero density at the right end. Sufficient (close to the necessary) conditions are given for a sequence of complex numbers to be the spectrum of such a string. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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     

Exact travelling wave solutions for the generalized nonlinear Schrödinger (GNLS) equation with a source by Extended tanh–coth, sine–cosine and Exp-Function methods

The capability of Extended tanh–coth, sine–cosine and Exp-Function methods as alternative approaches to obtain the analytic solution of different types of applied differential equations in engineering mathematics has been revealed. In this study, the generalized nonlinear Schrödinger (GNLS) equation is solved by three different methods. To obtain the single-soliton solutions for the equation, the Extended tanh–coth and sine–cosine methods are used. Furthermore, for this nonlinear evolution equation the Exp-Function method is applied to derive various travelling wave solution. Results show that while the first two procedures easily provide a concise solution, the Exp-Function method provides a powerful mathematical means for solving nonlinear evolution equations in mathematical physics.     

Existence of ground state solutions for asymptotically linear Schrödinger–Poisson systems

In this paper, we study the following Schrödinger–Poisson system: where λ > 0 is a parameter, with 2≤p≤+∞, and the function f(x,s) may not be superlinear in s near zero and is asymptotically linear with respect to s at infinity. Under certain assumptions on V, K, and f, we give the existence and nonexistence results via variational methods. More precisely, when p∈[2,+∞), we obtain that system (SP) has a positive ground state solution for λ small; when p =+ ∞, we prove that system (SP) has a positive solution for λ small and has no any nontrivial solution for λ large. Copyright © 2015 John Wiley & Sons, Ltd.     

Positive ground states for asymptotically periodic Schrödinger–Poisson systems

In this paper, we establish the existence of positive ground states for asymptotically periodic Schrödinger–Poisson systems with general nonlinearities by the method of Nehari manifold. Copyright © 2012 John Wiley & Sons, Ltd.