An official website of the United States government
Abstract Theq-colour Ramsey number of ak-uniform hypergraphHis the minimum integerNsuch that anyq-colouring of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofH. The study of these numbers is one of the central topics in Combinatorics. In 1973, Erdős and Graham asked to maximise the Ramsey number of a graph as a function of the number of its edges. Motivated by this problem, we study the analogous question for hypergaphs. For fixed$$k \ge 3$$and$$q \ge 2$$we prove that the largest possibleq-colour Ramsey number of ak-uniform hypergraph withmedges is at most$$\mathrm{tw}_k(O(\sqrt{m})),$$where tw denotes the tower function. We also present a construction showing that this bound is tight for$$q \ge 4$$. This resolves a problem by Conlon, Fox and Sudakov. They previously proved the upper bound for$$k \geq 4$$and the lower bound for$$k=3$$. Although in the graph case the tightness follows simply by considering a clique of appropriate size, for higher uniformities the construction is rather involved and is obtained by using paths in expander graphs.
more »
« less
This content will become publicly available on November 1, 2025
On the Ramsey numbers of daisies I
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.
more »
« less
- Award ID(s):
- 2300347
- PAR ID:
- 10584371
- Publisher / Repository:
- Cambridge Univ. Press
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 33
- Issue:
- 6
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 795 to 806
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary$$r$$-colouring of the complete$$k$$-uniform hypergraph$$K_n^k$$when$$k\geq 2$$and$$k\in \{r-1,r\}$$. We prove a result which says that if one replaces$$K_n^k$$in Gyárfás’ theorem by any ‘expansive’$$k$$-uniform hypergraph on$$n$$vertices (that is, a$$k$$-uniform hypergraph$$G$$on$$n$$vertices in which$$e(V_1, \ldots, V_k)\gt 0$$for all disjoint sets$$V_1, \ldots, V_k\subseteq V(G)$$with$$|V_i|\gt \alpha$$for all$$i\in [k]$$), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on$$r$$and$$\alpha$$). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary$$r$$-partite$$r$$-uniform hypergraph$$H$$with$$n$$edges in which every set of$$k$$edges has a common intersection. In this language, our result says that if one replaces the condition that every set of$$k$$edges has a common intersection with the condition that for every collection of$$k$$disjoint sets$$E_1, \ldots, E_k\subseteq E(H)$$with$$|E_i|\gt \alpha$$, there exists$$(e_1, \ldots, e_k)\in E_1\times \cdots \times E_k$$such that$$e_1\cap \cdots \cap e_k\neq \emptyset$$, then the smallest possible maximum degree of$$H$$is essentially the same (within a small error term depending on$$r$$and$$\alpha$$). We prove our results in this dual setting.more » « less
-
Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.more » « less
-
Let$$X$$be a smooth geometrically connected projective curve over the field of fractions of a discrete valuation ring$$R$$, and$$\mathfrak {m}$$a modulus on$$X$$, given by a closed subscheme of$$X$$which is geometrically reduced. The generalized Jacobian$$J_\mathfrak {m}$$of$$X$$with respect to$$\mathfrak {m}$$is then an extension of the Jacobian of$$X$$by a torus. We describe its Néron model, together with the character and component groups of the special fibre, in terms of a regular model of$$X$$over$$R$$. This generalizes Raynaud's well-known description for the usual Jacobian. We also give some computations for generalized Jacobians of modular curves$$X_0(N)$$with moduli supported on the cusps.more » « less
-
Abstract Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$$\omega $$,$$\zeta $$, and$$\eta $$denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$$\omega $$. If$$\mathcal {L}$$is a computable copy of$$\omega $$that is computably isomorphic to the usual presentation of$$\omega $$, then every cohesive power of$$\mathcal {L}$$has order-type$$\omega + \zeta \eta $$. However, there are computable copies of$$\omega $$, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$$\omega + \zeta \eta $$. For example, we show that there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \eta $$. Our most general result is that if$$X \subseteq \mathbb {N} \setminus \{0\}$$is a Boolean combination of$$\Sigma _2$$sets, thought of as a set of finite order-types, then there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$$, where$$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$$denotes the shuffle of the order-types inXand the order-type$$\omega + \zeta \eta + \omega ^*$$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \boldsymbol {\sigma }(X)$$.more » « less
