ON AN EXTREMAL PROBLEM IN GRAPH THEORY

ON AN EXTREMAL PROBLEM IN GRAPH THEORY

1965 | P. ERDŐS (BUDAPEST)
This paper addresses an extremal problem in graph theory, focusing on the minimum number of edges required in a graph to guarantee the presence of a complete subgraph or a bipartite subgraph. Erdős introduces notation for graphs and discusses known results, such as Turán's theorem, which determines the minimum number of edges in a graph that ensures the presence of a complete subgraph. He also discusses results by Dirac and himself regarding the structure of such graphs. The paper then presents a problem regarding the minimum number of edges in a graph to ensure the presence of a complete bipartite subgraph $ K(p,p) $. Erdős notes that this problem is challenging and cites previous results by Klein and himself, as well as Reiman, who provided bounds on the growth rate of this minimum number. Erdős proves two theorems. The first, Theorem 1, states that for a sufficiently large constant $ \gamma_p $, any graph with $ [\gamma_p n^{2-1/p}] $ edges contains a complete bipartite subgraph $ K(p+1, p+1) $ missing one edge. The second, Theorem 2, provides a stronger result, showing that for any integer $ l > p $, there exists a constant $ \gamma_{p,l} $ such that any graph with $ [\gamma_{p,l} n^{2-1/p}] $ edges contains a specific subgraph $ H(p,l,l) $, which is a complete bipartite graph missing edges where both indices exceed $ p $. The proofs rely on lemmas that establish the existence of subgraphs with certain properties. The paper concludes with a detailed proof of Theorem 2, demonstrating the existence of the required subgraph through a series of logical steps and combinatorial arguments. The results contribute to the understanding of extremal graph theory, particularly in the context of complete and bipartite subgraphs.This paper addresses an extremal problem in graph theory, focusing on the minimum number of edges required in a graph to guarantee the presence of a complete subgraph or a bipartite subgraph. Erdős introduces notation for graphs and discusses known results, such as Turán's theorem, which determines the minimum number of edges in a graph that ensures the presence of a complete subgraph. He also discusses results by Dirac and himself regarding the structure of such graphs. The paper then presents a problem regarding the minimum number of edges in a graph to ensure the presence of a complete bipartite subgraph $ K(p,p) $. Erdős notes that this problem is challenging and cites previous results by Klein and himself, as well as Reiman, who provided bounds on the growth rate of this minimum number. Erdős proves two theorems. The first, Theorem 1, states that for a sufficiently large constant $ \gamma_p $, any graph with $ [\gamma_p n^{2-1/p}] $ edges contains a complete bipartite subgraph $ K(p+1, p+1) $ missing one edge. The second, Theorem 2, provides a stronger result, showing that for any integer $ l > p $, there exists a constant $ \gamma_{p,l} $ such that any graph with $ [\gamma_{p,l} n^{2-1/p}] $ edges contains a specific subgraph $ H(p,l,l) $, which is a complete bipartite graph missing edges where both indices exceed $ p $. The proofs rely on lemmas that establish the existence of subgraphs with certain properties. The paper concludes with a detailed proof of Theorem 2, demonstrating the existence of the required subgraph through a series of logical steps and combinatorial arguments. The results contribute to the understanding of extremal graph theory, particularly in the context of complete and bipartite subgraphs.
Reach us at info@study.space