Search

Given two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any coloring of the edges of K N in red or blue yields a red G or a blue H. Let χ (G) be the chromatic number of G, and s(G) denote the chromatic surplus of G, the cardinality of a minimum color class taken over all proper colorings of G with χ (G) colors. A connected graph G is called H-good if R (G , H) = (v (G) - 1) (χ (H) - 1) + s (H) . Chvátal (J. Graph Theory 1:93, 1977) showed that any tree is K m -good for m ≥ 2 , where K m denotes a complete graph with m vertices. Let tH denote the union of t disjoint copies of graph H. Sudarsana et al. (Comput. Sci. 6196, Springer, Berlin, 2010) proved that the n-vertex path P n is 2 K m -good for n ≥ 3 and m ≥ 2 , and conjectured that any n-vertex tree T n is 2 K m -good. In this paper, we confirm this conjecture and prove that T n is 2 K m -good for n ≥ 3 and m ≥ 2 . We also prove a conclusion which yields that T n is (K m ∪ K l) -good, where K m ∪ K l is the disjoint union of K m and K l , m > l ≥ 2 . Furthermore, we extend the Ramsey goodness of connected graphs to disconnected graphs and study the relation between the Ramsey number of the components of a disconnected graph F versus a graph H. We show that if each component of a graph F is H-good, then F is H-good. Our result implies the exact value of R (F , K m ∪ K l) , where F is a forest and m , l ≥ 2 . [ABSTRACT FROM AUTHOR]

For a fixed positive integer n and an r-uniform hypergraph H, the Turán number ex(n, H) is the maximum number of edges in an H-free r-uniform hypergraph on n vertices, and the Lagrangian density of H is defined as π λ (H) = sup { r ! λ (G) : G is an H -free r -uniform hypergraph } , where λ (G) = max { ∑ e ∈ G ∏ i ∈ e x i : x i ≥ 0 and ∑ i ∈ V (G) x i = 1 } is the Lagrangian of G. For an r-uniform hypergraph H on t vertices, it is clear that π λ (H) ≥ r ! λ (K t - 1 r) . Let us say that an r-uniform hypergraph H on t vertices is λ -perfect if π λ (H) = r ! λ (K t - 1 r) . A result of Motzkin and Straus implies that all graphs are λ -perfect. It is interesting to explore what kind of hypergraphs are λ -perfect. A conjecture in [22] proposes that every sufficiently large r-uniform linear hypergraph is λ -perfect. In this paper, we investigate whether the conjecture holds for linear 3-uniform paths. Let P t = { e 1 , e 2 , ⋯ , e t } be the linear 3-uniform path of length t, that is, | e i | = 3 , | e i ∩ e i + 1 | = 1 and e i ∩ e j = ∅ if | i - j | ≥ 2 . We show that P 3 and P 4 are λ -perfect. Applying the results on Lagrangian densities, we determine the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

A real number α∈[0,1) is a jump for an integer r≥2 if there exists a constant c>0 such that any number in (α,α+c] cannot be the Turán density of a family of r-uniform graphs. Erdős and Stone showed that every number in [0,1) is a jump for r=2. Erdős asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing the existence of non-jumps for r≥3. Recently, Baber and Talbot showed that every number in [0.2299,0.2316)⋃[0.2871,827) is a jump for r=3 using Razborov’s flag algebra method. Pikhurko showed that the set of non-jumps for every r≥3 has cardinality of the continuum. But, there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we show that 1+r-1lr-1-rlr-2 is a non-jump for r≥4 and l≥3 which generalizes some earlier results. We do not know whether the same result holds for r=3. In fact, when r=3 and l=3, 1+r-1lr-1-rlr-2=29, and determining whether 29 is a jump or not for r=3 is perhaps the most important unknown question regarding this subject. Erdős offered $500 for answering this question. [ABSTRACT FROM AUTHOR]

Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in []. They showed that if G is a 2-graph in which a largest clique has order l then $${\lambda(G)=\lambda(K^{(2)}_l),}$$ where λ( G) denotes the Lagrangian of G. It is interesting to study a generalization of the Motzkin-Straus Theorem to hypergraphs. In this note, we give a Motzkin-Straus type result. We show that if m and l are positive integers satisfying $${{l-1 \choose 3} \le m \le {l-1 \choose 3} + {l-2 \choose 2}}$$ and G is a 3-uniform graph with m edges and G contains a $${K_{l-1}^{(3)}}$$, a clique of order l−1, then $${\lambda(G) = \lambda(K_{l-1}^{(3)})}$$. Furthermore, the upper bound $${{l-1 \choose 3} + {l-2 \choose 2}}$$ is the best possible. [ABSTRACT FROM AUTHOR]

Let G = ( V, E) be a graph and $${R\subseteq E}$$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser's conjecture. [ABSTRACT FROM AUTHOR]

A number $${\alpha\in [0, 1)}$$ is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family $${{\mathcal F}}$$ of r-uniform graphs, if the Turán density of $${{\mathcal F}}$$ is greater than α, then the Turán density of $${{\mathcal F}}$$ is at least α + c. A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in [0, 1) is a jump for r = 2. Erdős also showed that every number in [0, r!/ r r) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if $${c\cdot{\frac{r!}{r^r}}}$$ is a non-jump for r ≥ 3, then for every p ≥ r, $${c\cdot{\frac{p!}{p^p}}}$$ is a non-jump for p. [ABSTRACT FROM AUTHOR]