TL;DR
This paper proves that for any graph with a "balanced" density (not too sparse or too dense), it must contain a large number of distinct sizes for its induced $k$-vertex subgraphs. This result improves a known bound and has implications for understanding the structure of Ramsey graphs.
What Problem Does This Paper Address?
The paper tackles a question about the diversity of induced subgraphs within a larger graph. Specifically, it focuses on the number of different possible "sizes" (number of edges) that induced subgraphs of a fixed size $k$ can have. The authors are motivated by a conjecture by Erdős, Faudree, and Sós concerning $c$-Ramsey graphs. A $c$-Ramsey graph is one where any induced subgraph of size $n$ must contain either a clique or an independent set of size at least $c \log n$. The conjecture suggests that such graphs should have a large number of distinct pairs of $(|V(H)|, |E(H)|)$ for their induced subgraphs $H$. This paper provides a step towards this conjecture by showing that even graphs that are not necessarily $c$-Ramsey, but have densities bounded away from 0 and 1, exhibit significant diversity in the sizes of their induced $k$-vertex subgraphs.
Methods
The core of the paper's contribution lies in a constructive proof that establishes a lower bound on the number of distinct sizes of $k$-vertex induced subgraphs. The proof involves a careful analysis of "gaps" between consecutive subgraph sizes.
Key techniques include:
- Deviation: The concept of "deviation" is introduced to measure how the number of edges in a subgraph differs from what would be expected based on the overall graph density. This is a crucial tool for analyzing local structure.
- W-typical vertices: Vertices are classified as "W-typical" with respect to a subset $W$ if their number of neighbors within $W$ is close to the expected value. This classification allows for controlled manipulation of subgraphs.
- Swapping vertices: The proof relies on a strategy of swapping vertices between a chosen subgraph and the rest of the graph. By carefully selecting W-typical vertices, the authors show that these swaps can be performed in a way that creates new subgraphs with distinct sizes, while controlling the change in the number of edges.
- Gap analysis: The paper analyzes the "gaps" between consecutive sizes of $k$-vertex induced subgraphs. By showing that large gaps can be broken down into smaller, manageable steps, they establish a lower bound on the total number of distinct sizes.
- Leveraging existing results: The proof utilizes results from previous work, such as Theorem 3 (Erdős, Goldberg, Pach, and Spencer) on the deviation of subgraphs and Theorem 10 (Axenovich and Balogh) concerning homomorphic properties of graphs with few distinct subgraph sizes.
Datasets
Not discussed in the paper. The paper deals with theoretical graph properties and does not rely on specific datasets.
Key Insights and Ideas
- Density matters: The paper highlights that graphs with densities bounded away from 0 and 1 (i.e., not too sparse or too dense) inherently possess a rich structure in terms of their induced subgraphs.
- Controlled edge changes: The concept of "W-typical" vertices is a powerful tool for understanding how edge counts change when vertices are added or removed from subgraphs. This allows for precise control over the creation of new subgraph sizes.
- Breaking down large gaps: The strategy of analyzing and breaking down large "gaps" between consecutive subgraph sizes is key to establishing a lower bound on the total number of distinct sizes. This suggests a hierarchical structure in the distribution of subgraph sizes.
- Connection to Ramsey theory: The work provides a stepping stone towards understanding the structure of Ramsey graphs, suggesting that the diversity of induced subgraphs is a fundamental property related to Ramsey-type theorems.
Key Results
The main result is Theorem 2: For every $0 < \epsilon < 1/2$, there exists an $n_0(\epsilon)$ such that for any $n > n_0$ and any $n$-vertex graph $G$ with density $\epsilon < \alpha(G) < 1 - \epsilon$, the number of distinct sizes of $k$-vertex induced subgraphs, denoted by $\psi(k, G)$, satisfies $\psi(k, G) \ge 10^{-7}k$ for every $k < n/6$.
This result implies that for any fixed $\epsilon > 0$, graphs with densities in $[\epsilon, 1-\epsilon]$ have at least $\Omega(n^2)$ distinct pairs of $(|V(H)|, |E(H)|)$ for their induced subgraphs $H$.
Limitations and Future Work
- Constant factors: The paper acknowledges that the constant factors (like $10^{-7}$) are not optimized and could likely be improved.
- Ramsey property not fully utilized: The proof of the main result only uses the property that the graph density is bounded away from 0 and 1. It does not fully leverage the stronger $c$-Ramsey property. The authors suggest that applying the $c$-Ramsey assumption more directly could lead to improved estimates.
- Conjecture 1: The paper is a step towards Conjecture 1, but a full solution likely requires new ideas beyond the techniques used here.
- Weighted subgraphs: A weighted version of the main result is mentioned as a possible extension, where vertices have weights and subgraph "sizes" are defined by a weighted sum of edges and vertex weights.
- Random graphs: The paper briefly discusses the behavior of induced subgraph sizes in random graphs, suggesting that similar diversity exists asymptotically almost surely.
Summary updated