Geodesic
On Berge-Ramsey problems
Dániel Gerbner1
1Alfred Renyi Institute of Mathematics
The electronic journal of combinatorics, Tome 27 (2020) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a graph $G$, a hypergraph $\mathcal{H}$ is a Berge copy of $F$ if $V(G)\subset V(\mathcal{H})$ and there is a bijection $f:E(G)\rightarrow E(\mathcal{H})$ such that for any edge $e$ of $G$ we have $e\subset f(e)$. We study Ramsey problems for Berge copies of graphs, i.e. the smallest number of vertices of a complete $r$-uniform hypergraph, such that if we color the hyperedges with $c$ colors, there is a monochromatic Berge copy of $G$. We obtain a couple results regarding these problems. In particular, we determine for which $r$ and $c$ the Ramsey number can be super-linear. We also show a new way to obtain lower bounds, and improve the general lower bounds by a large margin. In the specific case $G=K_n$ and $r=2c-1$, we obtain an upper bound that is sharp besides a constant term, improving earlier results.
DOI : 10.37236/8775
Classification : 05D10
Mots-clés : Ramsey number, Berge copy

Dániel Gerbner  1

1 Alfred Renyi Institute of Mathematics 
@article{10_37236_8775,
     author = {D\'aniel Gerbner},
     title = {On {Berge-Ramsey} problems},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {2},
     doi = {10.37236/8775},
     zbl = {1441.05219},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8775/}
}
TY  - JOUR
AU  - Dániel Gerbner
TI  - On Berge-Ramsey problems
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8775/
DO  - 10.37236/8775
ID  - 10_37236_8775
ER  - 
%0 Journal Article
%A Dániel Gerbner
%T On Berge-Ramsey problems
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8775/
%R 10.37236/8775
%F 10_37236_8775
Dániel Gerbner. On Berge-Ramsey problems. The electronic journal of combinatorics, Tome 27 (2020) no. 2. doi: 10.37236/8775

Cité par Sources :