Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908753575542784 |
|---|---|
| author | Greenhill, Catherine Hasheminezhad, Mahdieh Iliffe, Isaiah McKay, Brendan D. |
| author_facet | Greenhill, Catherine Hasheminezhad, Mahdieh Iliffe, Isaiah McKay, Brendan D. |
| contents | In the sufficiently sparse case, we find the probability that a uniformly random bipartite graph with given degree sequence contains no edge from a specified set of edges. This enables us to enumerate loop-free digraphs and oriented graphs with given in-degree and out-degree sequences, and obtain subgraph probabilities. Our theorems are not restricted to the near-regular case. As an application, we determine the expected permanent of sparse or very dense random matrices with given row and column sums; in the regular case, our formula holds over all densities. We also draw conclusions about the degrees of a random orientation of a random undirected graph with given degrees, including its number of Eulerian orientations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04822 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence Greenhill, Catherine Hasheminezhad, Mahdieh Iliffe, Isaiah McKay, Brendan D. Combinatorics 05A16, 05C80, 15A15 In the sufficiently sparse case, we find the probability that a uniformly random bipartite graph with given degree sequence contains no edge from a specified set of edges. This enables us to enumerate loop-free digraphs and oriented graphs with given in-degree and out-degree sequences, and obtain subgraph probabilities. Our theorems are not restricted to the near-regular case. As an application, we determine the expected permanent of sparse or very dense random matrices with given row and column sums; in the regular case, our formula holds over all densities. We also draw conclusions about the degrees of a random orientation of a random undirected graph with given degrees, including its number of Eulerian orientations. |
| title | Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence |
| topic | Combinatorics 05A16, 05C80, 15A15 |
| url | https://arxiv.org/abs/2601.04822 |