PreprintCC BY 4.0arXiv
Negative edge correlation in complete bipartite graphs
Abstract
We prove strict pairwise negative correlation under both the uniform forest measure and the uniform connected-subgraph measure on the complete bipartite graph Km,n for all m,n≥2. Under the connected-subgraph measure, any two distinct edges of a fixed copy of K2,2 remain strictly negatively correlated after conditioning on the subgraph induced by the remaining vertices.
Related
- Edge complexity of complete bipartite and complete multipartite graphs
- Almost Gorenstein edge rings of bipartite graphs and their h-vectors
- Maximal Linear Arrangement is NP complete on Bipartite Graphs
- Wild number for spanning trees in complete and complete bipartite graphs
- Counting linear extensions of incidence posets of bipartite graphs is #P-complete
BibTeX
@misc{cao2026negative,
title = {{Negative edge correlation in complete bipartite graphs}},
author = {Ying Cao and Houshan Fu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36749},
eprint = {2610.36749},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36749},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Negative edge correlation in complete bipartite graphs
AU - Ying Cao
AU - Houshan Fu
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36749
UR - https://arxiv.org/abs/2610.36749
AB - We prove strict pairwise negative correlation under both the uniform forest measure and the uniform connected-subgraph measure on the complete bipartite graph K_m,n for all m,n≥2. Under the connected-subgraph measure, any two distinct edges of a fixed copy of K_2,2 remain strictly negatively correlated after conditioning on the subgraph induced by the remaining vertices.
ER -