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 January 1, 2026
Density of monochromatic infinite subgraphs II
Abstract In 1967, Gerencsér and Gyárfás [16] proved a result which is considered the starting point of graph-Ramsey theory: In every 2-coloring of$$K_n$$, there is a monochromatic path on$$\lceil (2n+1)/3\rceil $$vertices, and this is best possible. There have since been hundreds of papers on graph-Ramsey theory with some of the most important results being motivated by a series of conjectures of Burr and Erdős [2, 3] regarding the Ramsey numbers of trees (settled in [31]), graphs with bounded maximum degree (settled in [5]), and graphs with bounded degeneracy (settled in [23]). In 1993, Erdős and Galvin [13] began the investigation of a countably infinite analogue of the Gerencsér and Gyárfás result: What is the largestdsuch that in every$$2$$-coloring of$$K_{\mathbb {N}}$$there is a monochromatic infinite path with upper density at leastd? Erdős and Galvin showed that$$2/3\leq d\leq 8/9$$, and after a series of recent improvements, this problem was finally solved in [7] where it was shown that$$d={(12+\sqrt {8})}/{17}$$. This paper begins a systematic study of quantitative countably infinite graph-Ramsey theory, focusing on infinite analogues of the Burr-Erdős conjectures. We obtain some results which are analogous to what is known in finite case, and other (unexpected) results which have no analogue in the finite case.
more »
« less
- Award ID(s):
- 1954170
- PAR ID:
- 10626496
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 13
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A$$(p,q)$$-colouring of a graph$$G$$is an edge-colouring of$$G$$which assigns at least$$q$$colours to each$$p$$-clique. The problem of determining the minimum number of colours,$$f(n,p,q)$$, needed to give a$$(p,q)$$-colouring of the complete graph$$K_n$$is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers$$r_k(p)$$. The best-known general upper bound on$$f(n,p,q)$$was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$$p=q$$have been obtained only for$$p\in \{4,5\}$$, each of which was proved by giving a deterministic construction which combined a$$(p,p-1)$$-colouring using few colours with an algebraic colouring. In this paper, we provide a framework for proving new upper bounds on$$f(n,p,p)$$in the style of these earlier constructions. We characterize all colourings of$$p$$-cliques with$$p-1$$colours which can appear in our modified version of the$$(p,p-1)$$-colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying$$(p,p)$$-colourings, which would otherwise make this problem intractable for large values of$$p$$. In addition, we generalize our algebraic colouring from the$$p=5$$setting and use this to give improved upper bounds on$$f(n,6,6)$$and$$f(n,8,8)$$.more » « less
-
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 What proportion of integers$$n \leq N$$may be expressed as$$x^2 + dy^2$$for some$$d \leq \Delta $$, with$$x,y$$integers? Writing$$\Delta = (\log N)^{\log 2} 2^{\alpha \sqrt {\log \log N}}$$for some$$\alpha \in (-\infty , \infty )$$, we show that the answer is$$\Phi (\alpha ) + o(1)$$, where$$\Phi $$is the Gaussian distribution function$$\Phi (\alpha ) = \frac {1}{\sqrt {2\pi }} \int ^{\alpha }_{-\infty } e^{-x^2/2} dx$$. A consequence of this is a phase transition: Almost none of the integers$$n \leq N$$can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 - \varepsilon }$$, but almost all of them can be represented by$$x^2 + dy^2$$with$$d \leq (\log N)^{\log 2 + \varepsilon}\kern-1.5pt$$.more » « less
-
Abstract Given a family$$\mathcal{F}$$of bipartite graphs, theZarankiewicz number$$z(m,n,\mathcal{F})$$is the maximum number of edges in an$$m$$by$$n$$bipartite graph$$G$$that does not contain any member of$$\mathcal{F}$$as a subgraph (such$$G$$is called$$\mathcal{F}$$-free). For$$1\leq \beta \lt \alpha \lt 2$$, a family$$\mathcal{F}$$of bipartite graphs is$$(\alpha,\beta )$$-smoothif for some$$\rho \gt 0$$and every$$m\leq n$$,$$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, Allen, Keevash, Sudakov and Verstraëte proved that for any$$(\alpha,\beta )$$-smooth family$$\mathcal{F}$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$$is bipartite. In this paper, we strengthen their result by showing that for every real$$\delta \gt 0$$, there exists$$k_0$$such that for all odd$$k\geq k_0$$and sufficiently large$$n$$, any$$n$$-vertex$$\mathcal{F}\cup \{C_k\}$$-free graph with minimum degree at least$$\delta n^{\alpha -1}$$is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families$$\mathcal{F}$$consisting of the single graph$$K_{s,t}$$when$$t\gg s$$. We also prove an analogous result for$$C_{2\ell }$$-free graphs for every$$\ell \geq 2$$, which complements a result of Keevash, Sudakov and Verstraëte.more » « less
