Hostname: page-component-7bb8b95d7b-2h6rp Total loading time: 0 Render date: 2024-09-22T01:46:51.364Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Ramsey numbers of daisies I

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  18 September 2024

Pavel Pudlák ,
Vojtech Rödl  and
Marcelo Sales Open the ORCID record for Marcelo Sales [Opens in a new window]
Pavel Pudlák
Affiliation:
Institute of Mathematics, CAS, Prague, Czech Republic
Vojtech Rödl
Affiliation:
Department of Mathematics, Emory University, Atlanta, GA, USA
Marcelo Sales*
Affiliation:
Department of Mathematics, University of California, Irvine, CA, USA
*
Corresponding author: Marcelo Sales; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Daisies are a special type of hypergraph introduced by Bollobás, Leader and Malvenuto. An $r$-daisy determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P\,{:}\, P\in M^{(r)}\}$. Bollobás, Leader and Malvenuto initiated the study of Turán type density problems for daisies. This paper deals with Ramsey numbers of daisies, which are natural generalisations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of $r$-daisies and also for special cases where the size of the kernel is bounded.

Keywords

Ramsey theoryhypergraphs

MSC classification

Primary: 05D10: Ramsey theory
Secondary: 05C65: Hypergraphs
Type
Paper
Information
Combinatorics, Probability and Computing , First View , pp. 1 - 12
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alon, N. and Spencer, J. H. (2016) The Probabilistic Method, Fourth Edition, Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc.Google Scholar
Bollobás, B., Leader, I. and Malvenuto, C. (2011) Daisies and other Turán problems. Combin. Probab. Comput. 20(5) 743–747.CrossRefGoogle Scholar
Cohen, G. and Shinkar, I. (2015) Zero-fixing Extractors for Sub-logarithmic Entropy, Automata, Languages, and Programming. Part I, pp. 343–354.Google Scholar
Conlon, D., Fox, J. and Sudakov, B. (2013) An improved bound for the stepping-up lemma. Discrete Appl. Math. 161(9) 1191–1196.CrossRefGoogle Scholar
Duffus, D., Lefmann, H. and Rödl, V. (1995) Shift graphs and lower bounds on Ramsey numbers $r_{k}(l;r)$ . Discrete Math. 137(1-3) 177–187.CrossRefGoogle Scholar
Ellis, D., Ivan, M.-R. and Leader, I. (2024) Turán densities for daisies and hypercubes.Google Scholar
Ellis, D. and King, D. (2023) Lower bounds for the Turán densities of daisies. Electron. J. Combin. 30(4, Paper No. 4.4) 11.CrossRefGoogle Scholar
Erdős, P., Hajnal, A. and Rado, R. (1965) Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. 16 93–196.CrossRefGoogle Scholar
Erdős, P. and Lovász, L. (1975) Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions, Infinite á and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdos on his 60th Birthday), Vol. II, pp. 609–627, Colloq. Math. Soc. János Bolyai, Vol. 10.Google Scholar
Graham, R. L., Rothschild, B. L. and Spencer, J. H. (1990) Ramsey theory, Second, Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication. John Wiley & Sons, Inc.Google Scholar
Pudlák, P. and Rödl, V. (2022) Extractors for small zero-fixing sources. Combinatorica 42(4) 587–616.CrossRefGoogle Scholar
Pudlák, P. and Rödl, V. (2024) Colorings of k-sets with low discrepancy on small sets, arXiv:2402.05286.Google Scholar
Sales, M. (2022) On the ramsey number of daisies II, arXiv:2211.10385.Google Scholar
Shaltiel, R. (2011) An Introduction to Randomness Extractors, Automata, Languages and Programming. Part II, pp. 21–41.Google Scholar