Partition Universality for Hypergraphs of Bounded Degeneracy and Degree

EUROCOMB’23

Peter Allen Julia Böttcher Domenico Mergoni Cecchelli

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-002

PDF
Abstract
We consider the following question. When is the random $k$-uniform hypergraph $\Gamma=G^{(k)}(N,p)$ likely to be $r$-partition universal for $k$-uniform hypergraphs of bounded degree and degeneracy? That is, for which $p$ can we guarantee asymptotically almost surely that in any $r$-colouring of $E(\Gamma)$ there exists a colour $\chi$ such that in $\Gamma$ there are $\chi$-monochromatic copies of all $k$-uniform hypergraphs of maximum vertex degree $\Delta$, degeneracy at most $D$, and $cN$ vertices for some constant $c=c(D,\Delta)>0$. We show that if $\mu>0$ is fixed, then $p\ge N^{-1/D+\mu}$ suffices for a positive answer if $N$ is large. On the other hand, for $p=o(N^{-1/D})$ we show that $G^{(k)}(N,p)$ is likely not to contain some graphs of maximum degree $\Delta$ and degeneracy $D$ on $cN$ vertices at all. This improves the best upper bounds on the minimum number of edges required for a $k$-uniform hypergraph to be partition universal (even for $k=2$) and also for the size-Ramsey problem for most $k$-uniform hypergraphs of bounded degree and degeneracy.

Pages:
12–18
References

Allen, Peter, and Julia Böttcher. 2022. "Partition Universality for Graphs of Bounded Degeneracy and Degree." arXiv Preprint arXiv:2211.15819.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-002

Allen, Peter, Julia Böttcher, Ewan Davies, Eng Keat Hng, and Jozef Skokan. n.d. "A Sparse Hypergraph Blow-up Lemma."

Allen, Peter, Julia Böttcher, and Domenico Mergoni Cecchelli. n.d. "Partition Universality for Hypergraphs of Bounded Degeneracy and Degree." To Appear.

Allen, Peter, Olaf Parczyk, and Vincent Pfenninger. 2021. "Resilience for Tight Hamiltonicity." arXiv Preprint arXiv:2105.04513.

Beck, József. 1983. "On Size Ramsey Number of Paths, Trees, and Circuits. I." J. Graph Theory 7 (1): 115-29.
https://doi.org/10.1002/jgt.3190070115

Berger, Sören, Yoshiharu Kohayakawa, Giulia Satiko Maesaka, Taı́sa Martins, Walner Mendonça, Guilherme Oliveira Mota, and Olaf Parczyk. 2021. "The Size-Ramsey Number of Powers of Bounded Degree Trees." J. Lond. Math. Soc. (2) 103 (4): 1314-32.
https://doi.org/10.1112/jlms.12408

Clemens, Dennis, Matthew Jenssen, Yoshiharu Kohayakawa, Natasha Morrison, Guilherme Oliveira Mota, Damian Reding, and Barnaby Roberts. 2019. "The Size-Ramsey Number of Powers of Paths." J. Graph Theory 91 (3): 290-99.
https://doi.org/10.1002/jgt.22432

Conlon, David, Rajko Nenadov, and Miloš Trujić. n.d. "The Size-Ramsey Number of Cubic Graphs."

Conlon, D., W. T. Gowers, W. Samotij, and M. Schacht. 2014. "On the KŁR Conjecture in Random Graphs." Israel J. Math. 203 (1): 535-80.
https://doi.org/10.1007/s11856-014-1120-1

Cooley, Oliver, Nikolaos Fountoulakis, Daniela Kühn, and Deryk Osthus. 2009. "Embeddings and Ramsey Numbers of Sparse -Uniform Hypergraphs." Combinatorica 29 (3): 263-97.
https://doi.org/10.1007/s00493-009-2356-y

Draganić, Nemanja, and Kalina Petrova. n.d. "Size-Ramsey Numbers of Graphs with Maximum Degree Three."

Dudek, Andrzej, Steven La Fleur, Dhruv Mubayi, and Vojtech Rödl. 2017. "On the Size-Ramsey Number of Hypergraphs." Journal of Graph Theory 86 (1): 104-21.
https://doi.org/10.1002/jgt.22115

Erdős, Paul, Ralph J Faudree, Cecil C Rousseau, and Richard H Schelp. 1978. "The Size Ramsey Number." Periodica Mathematica Hungarica 9 (1-2): 145-61.
https://doi.org/10.1007/BF02018930

Friedman, J., and N. Pippenger. 1987. "Expanding Graphs Contain All Small Trees." Combinatorica 7 (1): 71-76.
https://doi.org/10.1007/BF02579202

Han, Jie, Matthew Jenssen, Yoshiharu Kohayakawa, Guilherme Oliveira Mota, and Barnaby Roberts. 2020. "The Multicolour Size-Ramsey Number of Powers of Paths." J. Combin. Theory Ser. B 145: 359-75.
https://doi.org/10.1016/j.jctb.2020.06.004

Han, Jie, Yoshiharu Kohayakawa, Shoham Letzter, Guilherme Oliveira Mota, and Olaf Parczyk. 2021. "The Size-Ramsey Number of 3-Uniform Tight Paths." Adv. Comb., Paper No. 5, 12.
https://doi.org/10.19086/aic.24581

Haxell, P. E., Y. Kohayakawa, and T. Łuczak. 1995. "The Induced Size-Ramsey Number of Cycles." Combin. Probab. Comput. 4 (3): 217-39.
https://doi.org/10.1017/S0963548300001619

Kamcev, Nina, Anita Liebenau, David R. Wood, and Liana Yepremyan. 2021. "The Size Ramsey Number of Graphs with Bounded Treewidth." SIAM J. Discrete Math. 35 (1): 281-93.
https://doi.org/10.1137/20M1335790

Kim, Jeong Han, and Van H. Vu. 2000. "Concentration of Multivariate Polynomials and Its Applications." Combinatorica 20 (3): 417-34. https://doi.org/10.1007/s004930070014.
https://doi.org/10.1007/s004930070014

Kohayakawa, Y. 1997. "Szemerédi's Regularity Lemma for Sparse Graphs." In Foundations of Computational Mathematics (Rio de Janeiro, 1997), 216-30. Springer, Berlin.
https://doi.org/10.1007/978-3-642-60539-0_16

Kohayakawa, Y., V. Rödl, M. Schacht, and E. Szemerédi. 2011. "Sparse Partition Universal Graphs for Graphs of Bounded Degree." Advances in Mathematics 226 (6): 5041-65.
https://doi.org/10.1016/j.aim.2011.01.004

Letzter, Shoham, Alexey Pokrovskiy, and Liana Yepremyan. 2021. "Size-Ramsey Numbers of Powers of Hypergraph Trees and Long Subdivisions." arXiv Preprint arXiv:2103.01942.

Nenadov, Rajko. 2016. "Ramsey and Universality Properties of Random Graphs." PhD thesis, ETH Zürich.

Ramsey, F. P. 1930. "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30 (1): 264-86. https://doi.org/10.1112/plms/s2-30.1.264.
https://doi.org/10.1112/plms/s2-30.1.264

Rodl, Vojtech, and Endre Szemerédi. 2000. "On Size Ramsey Numbers of Graphs with Bounded Degree." Combinatorica 20 (2): 257-62.
https://doi.org/10.1007/s004930070024

Spencer, Joel. 1990. "Counting Extensions." J. Combin. Theory Ser. A 55 (2): 247-55.
https://doi.org/10.1016/0097-3165(90)90070-D

Tikhomirov, Konstantin. n.d. "On Bounded Degree Graphs with Large Size-Ramsey Numbers."

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Peter Allen, Julia Böttcher, Domenico Mergoni Cecchelli

PDF