Given positive integers k and ℓ we write G → (K k , K ℓ ) if every 2-colouring of the edges of G yields a red copy of K k or a blue copy of K ℓ . We prove that for every integer k ≥ 3, there exists a graph G such that G→(K k ,K k ) while G → (K k+1 , K k-1 ). This result can be viewed as a variation of a classical theorem of Nešetřil and Rödl [11], who proved that for every k ≥ 2 there is a graph G such that K k ⊆ G and G → K k-1 . Our construction combines probabilistic methods and hypergraph container techniques to produce graphs exhibiting this Ramsey behavior.

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of Kn gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of Kn. Our main result here pins down this threshold when we focus on colourings that are constrained by some prefixed lists. This result is applied in an accompanying work of the authors on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle.

We study the emergence of loose Hamilton cycles in subgraphs of random hypergraphs. Our main result states that the minimum d-degree threshold for loose Hamiltonicity relative to the random k-uniform hypergraph Hk(n, p) coincides with its dense analogue whenever p ≥ n−(k-1)/2+o(1). The value of p is approximately tight for d > (k + 1)/2. This is particularly interesting because the dense threshold itself is not known beyond the cases when d ≥ k - 2.

For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, Škorić and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.

Let Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k ≥ 4 where n ≥ 5 or k ≥ 5, we prove that Sk(n) = 2tk - 1(n), where tk-1(n) is the number of edges of the n-vertex (k - 1)-partite Turán graph Tk-1(n). Moreover, we prove that Tk-1(n) is the only graph having 2tk-1(n) orientations with no strongly connected copies of Kk.

Given graphs G, H1 and H2, let G→mr(H1, H2) denote the property that in every edge-colouring of G there is a monochromatic copy of H1 or a rainbow copy of H2. The constrained Ramsey number, defined as the minimum n such that Kn→mr(H1, H2), exists if and only if H1 is a star or H2 is a forest. We determine the threshold for the property G(n,p) →mr(H1, H2) when H2 is a forest.

A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $\mathcal{D}$ of $G$ such that every subgraph $H \in \mathcal{D}$ is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs.

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-colored random graph. More precisely, we show that for $p\gg n^{-1/6}{(\ln n)}^{1/6}$, in any $3$-edge coloring of the random graph $G(n,p)$ we can find three monochromatic trees such that their union covers all vertices. This improves, for three colors, a result of Bucić, Korándi, and Sudakov.

We estimate the 3-color bipartite Ramsey number for balanced bipartite graphs $H$ with small bandwidth and bounded maximum degree. More precisely, we show that the minimum value of $N$ such that in any 3-edge coloring of $K_{N,N}$ there is a monochromatic copy of $H$ is at most $\big(3/2+o(1)\big)|V(H)|$. In particular, we determine asymptotically the $3$-color bipartite Ramsey number for grid graphs.

We prove that for all $k\geq 4$ and $1\leq\ell

Many methods have been published to prioritize genes using network theory. By using protein-protein interaction (PPI) data, it is possible to use mathematical features to rank and prioritize genes products in the network. Taking into account that genes related to the same diseases tend to connect, in the network structure, the prioritization methods search for candidate genes in the neighborhood of other genes already known to be related to a specific phenotype. Unfortunately, some existing algorithms can not deal well with highly connected genes, and some of them end up being related by chance to the disease being studied. We propose a pure method, with no need of adjustments, based on the hitting time of a random walk in PPI networks. This method captures information of the whole network and can equally prioritize genes regardless of its degree. We tested the efficiency of our method prioritizing candidate genes for Attention-Deficit/Hyperactivity Disorder (ADHD). The proposed method was able to give a good rank to genes that have genetic association with ADHD and was able to prioritize a large proportion of genes prioritized by other random-walk-based methods.