[2604.02264] Random Turán Problems for Graphs with a Vertex Complete to One Part
Abstract: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.
View PDF HTML (experimental) Abstract: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…
saved by
related reading
- Exact Stability for Turan's Theoremarxiv.org
- rainbow-turan-full-version.pdfpeople.maths.ox.ac.uk
- Rainbow Turán Problemspeople.math.ethz.ch
- Helly Theorems for Generalized Turán Problemsarxiv.org
- balogh containersarxiv.org
- rainbow treesarxiv.org
- [2305.02725] Two-round Ramsey games on random graphsarxiv.org
- random subgraphs rainbowarxiv.org
- nullstellensatzweb.math.princeton.edu
- piercing intervals - gyarfasarxiv.org
- 02_GyarfasLehel_AHellyTypeProblemInTrees.pdfusers.renyi.hu
- parity edge coloringmilans.us