Testing Properties of Edge Distributions
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918406108741632 |
|---|---|
| author | Fei, Yumou |
| author_facet | Fei, Yumou |
| contents | We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of ``edge-distribution-free'' graph property testing. The main results of this paper are nearly-tight bounds on testing bipartiteness, triangle-freeness and square-freeness of edge distributions, whose sample complexities are shown to scale as $Θ(n)$, $n^{4/3\pm o(1)}$ and $n^{9/8\pm o(1)}$, respectively.
The technical core of our paper lies in the proof of the upper bound for testing square-freeness, wherein we develop new techniques based on certain birthday-paradox-type lemmas that may be of independent interest. We will discuss how our techniques fit into the general framework of distribution-free property testing. We will also discuss how our results are conceptually connected with Turán problems and subgraph removal lemmas in extremal combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22702 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Testing Properties of Edge Distributions Fei, Yumou Data Structures and Algorithms Computational Complexity We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of ``edge-distribution-free'' graph property testing. The main results of this paper are nearly-tight bounds on testing bipartiteness, triangle-freeness and square-freeness of edge distributions, whose sample complexities are shown to scale as $Θ(n)$, $n^{4/3\pm o(1)}$ and $n^{9/8\pm o(1)}$, respectively. The technical core of our paper lies in the proof of the upper bound for testing square-freeness, wherein we develop new techniques based on certain birthday-paradox-type lemmas that may be of independent interest. We will discuss how our techniques fit into the general framework of distribution-free property testing. We will also discuss how our results are conceptually connected with Turán problems and subgraph removal lemmas in extremal combinatorics. |
| title | Testing Properties of Edge Distributions |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2603.22702 |