On problems in extremal multigraph theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918080625508352 |
|---|---|
| author | Falgas-Ravry, Victor Mond, Adva Sarkar, Rik Souza, Victor |
| author_facet | Falgas-Ravry, Victor Mond, Adva Sarkar, Rik Souza, Victor |
| contents | A multigraph G is said to be an (s,q)-graph if every s-set of vertices in G supports at most q edges (counting multiplicities). In this paper we consider the maximal sum and product of edge multiplicities in an (s,q)-graph on n vertices. These are multigraph analogues of a problem of Erdős raised by Füredi and Kündgen and Mubayi and Terry respectively, with applications to counting problems and extremal hypergraph theory.
We make major progress, settling conjectures of Day, Falgas-Ravry and Treglown and of Falgas-Ravry, establishing intricate behaviour for both the sum and the product problems, and providing both a general picture and evidence that the problems may prove computationally intractable in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14281 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On problems in extremal multigraph theory Falgas-Ravry, Victor Mond, Adva Sarkar, Rik Souza, Victor Combinatorics 05C35, 05C30, 05D99 G.2.1; G.2.2 A multigraph G is said to be an (s,q)-graph if every s-set of vertices in G supports at most q edges (counting multiplicities). In this paper we consider the maximal sum and product of edge multiplicities in an (s,q)-graph on n vertices. These are multigraph analogues of a problem of Erdős raised by Füredi and Kündgen and Mubayi and Terry respectively, with applications to counting problems and extremal hypergraph theory. We make major progress, settling conjectures of Day, Falgas-Ravry and Treglown and of Falgas-Ravry, establishing intricate behaviour for both the sum and the product problems, and providing both a general picture and evidence that the problems may prove computationally intractable in general. |
| title | On problems in extremal multigraph theory |
| topic | Combinatorics 05C35, 05C30, 05D99 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2505.14281 |