Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T04:01:12.312Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Degrees and Codegrees of Ramsey-Minimal 3-Uniform Hypergraphs* †

Part of: Extremal combinatorics

Published online by Cambridge University Press:  20 January 2016

DENNIS CLEMENS  and
YURY PERSON
DENNIS CLEMENS
Affiliation:
Technische Universität Hamburg–Harburg, Institut für Mathematik, Am Schwarzenberg-Campus 3, 21073 Hamburg, Germany (e-mail: dennis.clemens@tuhh.de)
YURY PERSON
Affiliation:
Goethe-Universität, Institut für Mathematik, Robert-Mayer-Straß e 10, 60325 Frankfurt am Main, Germany (e-mail: person@math.uni-frankfurt.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A uniform hypergraph H is called k-Ramsey for a hypergraph F if, no matter how one colours the edges of H with k colours, there is always a monochromatic copy of F. We say that H is k-Ramsey-minimal for F if H is k-Ramsey for F but every proper subhypergraph of H is not. Burr, Erdős and Lovasz studied various parameters of Ramsey-minimal graphs. In this paper we initiate the study of minimum degrees and codegrees of Ramsey-minimal 3-uniform hypergraphs. We show that the smallest minimum vertex degree over all k-Ramsey-minimal 3-uniform hypergraphs for Kt (3) is exponential in some polynomial in k and t. We also study the smallest possible minimum codegree over 2-Ramsey-minimal 3-uniform hypergraphs.

MSC classification

Primary: 05D10: Ramsey theory
Secondary: 05D40: Probabilistic methods

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 6 , November 2016 , pp. 850 - 869
Copyright
Copyright © Cambridge University Press 2016 

Footnotes

*

After this paper was accepted and processed, we managed to obtain BEL-gadgets for uniformities r ⩾ 4. This work will appear elsewhere.

†

An extended abstract of this paper appears in the proceedings of EuroComb 2015 [3].

References

[1] Burr, S. A., Erdős, P. and Lovász, L. (1976) On graphs of Ramsey type. Ars Combin. 1 167–190.Google Scholar
[2] Burr, S. A., Nešetřil, J. and Rödl, V. (1985) On the use of senders in generalized Ramsey theory for graphs. Discrete Math. 54 1–13.Google Scholar
[3] Clemens, D. and Person, Y. (2015) Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs. In Eighth European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), Electron. Notes in Discrete Math., Elsevier, pp. 23–30.Google Scholar
[4] Conlon, D. (2009) A new upper bound for diagonal Ramsey numbers. Ann. of Math. (2) 170 941–960.Google Scholar
[5] Conlon, D., Fox, J. and Sudakov, B. (2015) Recent developments in graph Ramsey theory. In Surveys in Combinatorics 2015, Cambridge University Press, pp. 49–118.CrossRefGoogle Scholar
[6] Dudek, A., La Fleur, S., Mubayi, D. and Rödl, V. On the size-Ramsey number of hypergraphs. Submitted.Google Scholar
[7] Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H. (1978) The size Ramsey number. Period. Math. Hungar. 9 145–161.CrossRefGoogle Scholar
[8] Erdős, P. and Hajnal, A. (1966) On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. 17 61–99.Google Scholar
[9] Fox, J., Grinshpun, A., Liebenau, A., Person, Y. and Szabó, T. (2014) What is Ramsey-equivalent to a clique? J. Combin. Theory Ser. B 109 120–133.Google Scholar
[10] Fox, J., Grinshpun, A., Liebenau, A., Person, Y. and Szabó, T. On the minimum degree of minimal Ramsey graphs for multiple colours. J. Combin. Theory Ser. B, accepted.Google Scholar
[11] Fox, J. and Lin, K. (2006) The minimum degree of Ramsey-minimal graphs. J. Graph Theory 54 167–177.Google Scholar
[12] Graham, R. L., Rothschild, B. L. and Spencer, J. H. (1990) Ramsey Theory, second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.Google Scholar
[13] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[14] Ramsey, F. P. (1930) On a problem in formal logic. Proc. Lond. Math. Soc. 30 264–286.Google Scholar
[15] Rödl, V. and Siggers, M. (2008) On Ramsey minimal graphs. SIAM J. Discrete Math. 22 467–488.Google Scholar
[16] Spencer, J. (1975) Ramsey's theorem: A new lower bound. J. Combin. Theory Ser. A 18 108–115.Google Scholar
[17] Szabó, T., Zumstein, P. and Zürcher, S. (2010) On the minimum degree of minimal Ramsey graphs. J. Graph Theory 64 150–164.Google Scholar