Monochromatic tree covers and Ramsey numbers for set-coloured graphs

We consider a generalisation of the classical Ramsey theory setting to a setting where each of the edges of the underlying host graph is coloured with a set of colours (instead of just one colour). We give bounds for monochromatic tree covers in this setting, both for an underlying complete graph, and an underlying complete bipartite graph. We also discuss a generalisation of Ramsey numbers to our setting and propose some other new directions.Our results for tree covers in complete graphs imply that a stronger version of Ryser’s conjecture holds for $k$-intersecting $r$-partite $r$-uniform hypergraphs: they have a transversal of size at most $r?k$. (Similar results have been obtained by Király et al., see below.) However, we also show that the bound $r?k$ is not best possible in general.     

A note on Ramsey numbers

Upper bounds are found for the Ramsey function. We prove $\text{R(3, x) <}\text{cx}{}^2\text{ln}\text{x}$ and, for each k ? 3, $\text{R(k, x) <}\text{c}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k\; ?\; 1}}\text{(}\text{ln}\text{x)}{}^{\mathrm{k\; ?\; 2}}$ asymptotically in x.     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

A note on Ramsey numbers for books

The book with n pages B_n is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B_m,B_n) is the smallest integer r such that either B_m ? G or B_n ? G for every graph G of order r. We prove that there exists a positive constant c such that r(B_m,B_n) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On induced Ramsey numbers for k‐uniform hypergraphs

Let denote the complete k‐uniform k‐partite hypergraph with classes of size t and the complete k‐uniform hypergraph of order s. One can show that the Ramsey number for and satisfies when t = s^o(1) as s →∞. The main part of this paper gives an analogous result for induced Ramsey numbers: Let be an arbitrary k‐partite k‐uniform hypergraph with classes of size t and an arbitrary k‐graph of order s. We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph such that any red/blue coloring of yields either an induced red copy of or an induced blue copy of ) satisfies . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016     

A note on the monotonicity of mixed Ramsey numbers

For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of K_n is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge.     

On Ramsey numbers of uniform hypergraphs with given maximum degree

For every ?>0 and every positive integers Δ and r, there exists C=C(?,Δ,r) such that the Ramsey number, R(H,H) of any r-uniform hypergraph H with maximum degree at most Δ is at most C|V(H)|^1+?.     

Generalised Ramsey numbers for small graphs

The generalised Ramsey number R(G₁, G₂,..., G_k) is defined as the smallest integer n such that, if the edges of K_n, the complete graph on n vertices, are coloured using k colours C₁, C₂,..., C_k, then for some i(1≤i≤k) there is a subgraph G_i of K_n with all of its edges colour C_i. When G₁=G₂=...,G_k=G, we use the more compact notation R_k(G).The generalised Ramsey numbers R_k(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2.     

Bounds for the Graham–Pollak theorem for hypergraphs

Let $f_r\left(n\right)$ represent the minimum number of complete $r$-partite $r$-graphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham–Pollak theorem states that $f_2\left(n\right)=n?1$. An upper bound of $(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ for even $r\ge 4$. A bound of $\left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{\frac{r}{4}}+o\left(1\right)\right](1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was also proved recently. Let $c_r$ be the limit of $\frac{f_r\left(n\right)}{\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)}$ as $n\to \infty$. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r\left(n\right)$, for small values of even $r$.     

An upper bound for the restricted online Ramsey number

The restricted $(m,n;N)$-online Ramsey game is a game played between two players, Builder and Painter. The game starts with $N$ isolated vertices. Each turn Builder picks an edge to build and Painter chooses whether that edge is red or blue, and Builder aims to create a red $K_m$ or blue $K_n$ in as few turns as possible. The restricted online Ramsey number $\stackrel{?}{r}(m,n;N)$ is the minimum number of turns that Builder needs to guarantee her win in the restricted $(m,n;N)$-online Ramsey game. We show that if $N=r(n,n)$, $\stackrel{?}{r}(n,n;N)\le \left(\genfrac{}{}{0ex}{}{N}{2}\right)?\Omega (NlogN),$motivated by a question posed by Conlon, Fox, Grinshpun and He. The equivalent game played on infinitely many vertices is called the online Ramsey game. As almost all known Builder strategies in the online Ramsey game end up reducing to the restricted setting, we expect further progress on the restricted online Ramsey game to have applications in the general case.     

Saturation of Berge hypergraphs

Given a graph $F$, a hypergraph is a Berge- $F$ if it can be obtained by expanding each edge in $F$ to a hyperedge containing it. A hypergraph $H$ is Berge-$F$-saturated if $H$ does not contain a subhypergraph that is a Berge-$F$, but for any edge $e\in E\left(\overline{H}\right)$, $H+e$ does. The $k$-uniform saturation number of Berge-$F$ is the minimum number of edges in a $k$-uniform Berge-$F$-saturated hypergraph on $n$ vertices. For $k=2$ this definition coincides with the classical definition of saturation for graphs. In this paper we study the saturation numbers for Berge triangles, paths, cycles, stars and matchings in $k$-uniform hypergraphs.     

A note on Ramsey multiplicity

If G₁ and G₂ are graphs and the Ramsey number r(G₁, G₂) = p, then the fewest number of G₁ in G and G₂ in ? (G complement) that occur in a graph G on p points is called the Ramsey multiplicity and denoted R(G₁, G₂). In [2, 3] the diagonal (i.e. G₁ = G₂) Ramsey multiplicities are derived for graphs on 3 and 4 points, with the exception of K₄. In this note an upper bound is established for R(K_s, K₁). Specifically, we show that R(K₄, K₄) ? 12.     

A symplectic perspective on constrained eigenvalue problems

The Maslov index is a powerful tool for computing spectra of selfadjoint, elliptic boundary value problems. This is done by counting intersections of a fixed Lagrangian subspace, which designates the boundary conditions, with the set of Cauchy data for the differential operator. We apply this methodology to constrained eigenvalue problems, in which the operator is restricted to a (not necessarily invariant) subspace. The Maslov index is defined and used to compute the Morse index of the constrained operator. We then prove a constrained Morse index theorem, which says that the Morse index of the constrained problem equals the number of constrained conjugate points, counted with multiplicity, and give an application to the nonlinear Schrödinger equation.     

A Bismut type formula for the Hessian of heat semigroups

We obtain an intrinsic version of a Bismut type formula for the Hessian of heat semigroups, resp. harmonic functions, by computing second order directional derivatives of families of martingales, along with filtering of redundant noise. As applications we provide a Hessian estimate in the general case as well as a slightly improved one in the radially symmetric situation. To cite this article: M. Arnaudon et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Matching in 3-uniform hypergraphs

A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. We use $E_3(2d?1,n?2d+1)$ to denote the 3-uniform hypergraph whose vertex set can be partitioned into two vertex classes $V_1$ and $V_2$ of size $2d?1$ and $n?2d+1$, respectively, and whose edge set consists of all the triples containing at least two vertices of $V_1$. Let $H$ be a 3-uniform hypergraph of order $n\ge 13d$ with no isolated vertex and $\text{deg}\left(u\right)+\text{deg}\left(v\right)>2\left(\left(\genfrac{}{}{0ex}{}{n?1}{2}\right)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)\right)$ for any two adjacent vertices $u,v\in V\left(H\right)$. In this paper, we show that $H$ contains a matching of size $d$ if and only if $H$ is not a subgraph of $E_3(2d?1,n?2d+1)$. This result improves our previous one in Zhang and Lu (2018).     

Ramsey numbers for triples

Some recurrence inequalities for Ramsey numbers for triples are established by means of explicit constructions.     

A note on the Ramsey property

An elementary setting of the classical Ramsey property is given, which leads to simple proofs of the relevant theorems of Galvin-Prikry and Silver.