Sharp Bounds for Edge Mappings of Graphs
Abstract
The study of extremal problems for set mappings was initiated by Erdős and Hajnal in 1958. Alon and Caro, and later Caro, Patkós, Tuza and Vizer, studied related problems for edge mappings of graphs. For a graph G with n vertices and m edges, let g0(G) be the minimum integer N such that every mapping f:E(KN)→ E(KN) satisfying f(e)∩ e=∅ for every e∈ E(KN) admits a copy G* of G in KN with f(e)∉ E(G*) for every e∈ E(G*). Gishboliner, Jin and Sudakov conjectured that g0(G)=O(n+m/√n). In this paper, we disprove this conjecture by constructing a family of graphs. We then prove that g0(G)=O(n+m3/4). Furthermore, for every n≥2 and m satisfying ⌈ n/2 ⌉≤ m≤ binomn2, there exists a graph G* with n vertices, m edges and no isolated vertices satisfying g0(G*)=Ω(n+m3/4). Thus the upper bound is best possible in terms of n and m.
Related
- Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing
- Sharp Bounds for Kulli-Basava Indices of Graphs
- Sharp Lovasz-Theta Bounds on Random Graphs
- Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
- Sharp Bounds on Torsional Rigidity of Metric Graphs with Signed Delta-Vertex Strengths
BibTeX
@misc{yang2026sharp,
title = {{Sharp Bounds for Edge Mappings of Graphs}},
author = {Zhanping Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01577},
eprint = {2611.01577},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01577},
}
RIS
TY - UNPB
TI - Sharp Bounds for Edge Mappings of Graphs
AU - Zhanping Yang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01577
UR - https://arxiv.org/abs/2611.01577
AB - The study of extremal problems for set mappings was initiated by Erdős and Hajnal in 1958. Alon and Caro, and later Caro, Patkós, Tuza and Vizer, studied related problems for edge mappings of graphs. For a graph G with n vertices and m edges, let g_0(G) be the minimum integer N such that every mapping f:E(K_N)→ E(K_N) satisfying f(e)∩ e=∅ for every e∈ E(K_N) admits a copy G^* of G in K_N with f(e)∉ E(G^*) for every e∈ E(G^*). Gishboliner, Jin and Sudakov conjectured that g_0(G)=O(n+m/√n). In this paper, we disprove this conjecture by constructing a family of graphs. We then prove that g_0(G)=O(n+m^3/4). Furthermore, for every n≥2 and m satisfying ⌈ n/2 ⌉≤ m≤ binomn2, there exists a graph G_* with n vertices, m edges and no isolated vertices satisfying g_0(G_*)=Ω(n+m^3/4). Thus the upper bound is best possible in terms of n and m.
ER -