Random Turán Problems for Graphs with a Vertex Complete to One Part
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918425728647168 |
|---|---|
| author | Longbrake, Sean Spiro, Sam |
| author_facet | Longbrake, Sean Spiro, Sam |
| contents | Given a graph $F$, the random Turán problem asks to determine the maximum number of edges in an $F$-free subgraph of $G_{n,p}$. Prior to this work, the only bipartite graphs $F$ with known tight bounds included certain classes of complete bipartite graphs and theta graphs. We greatly expand upon these examples by proving tight bounds for a number of bipartite graphs which have a vertex complete to one part. We also prove new general upper bounds for this problem which in many cases do significantly better than the only previous known general upper bound due to Jiang and Longbrake. Our proofs utilize dependent random choice together with the recent technique of balanced vertex supersaturation in conjunction with hypergraph containers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02264 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Random Turán Problems for Graphs with a Vertex Complete to One Part Longbrake, Sean Spiro, Sam Combinatorics 05C35, 05C80 Given a graph $F$, the random Turán problem asks to determine the maximum number of edges in an $F$-free subgraph of $G_{n,p}$. Prior to this work, the only bipartite graphs $F$ with known tight bounds included certain classes of complete bipartite graphs and theta graphs. We greatly expand upon these examples by proving tight bounds for a number of bipartite graphs which have a vertex complete to one part. We also prove new general upper bounds for this problem which in many cases do significantly better than the only previous known general upper bound due to Jiang and Longbrake. Our proofs utilize dependent random choice together with the recent technique of balanced vertex supersaturation in conjunction with hypergraph containers. |
| title | Random Turán Problems for Graphs with a Vertex Complete to One Part |
| topic | Combinatorics 05C35, 05C80 |
| url | https://arxiv.org/abs/2604.02264 |