Source author record

Taísa Martins

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

A lower bound for set-colouring Ramsey numbers

The set-colouring Ramsey number $R_{r,s}(k)$ is defined to be the minimum $n$ such that if each edge of the complete graph $K_n$ is assigned a set of $s$ colours from $\{1,\ldots,r\}$ , then one of the colours contains a monochromatic clique of size $k$ . The case $s = 1$ is the usual $r$ -colour Ramsey number, and the case $s = r - 1$ was studied by Erdős, Hajnal and Rado in 1965, and by Erdős and Szemerédi in 1972. The first significant results for general $s$ were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstraëte, who showed that $R_{r,s}(k) = 2^{Θ(kr)}$ if $s/r$ is bounded away from $0$ and $1$ . In the range $s = r - o(r)$ , however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) colouring, and use it to determine $R_{r,s}(k)$ up to polylogarithmic factors in the exponent for essentially all $r$ , $s$ and $k$ .

preprint2022arXiv

On the anti-Ramsey threshold for non-balanced graphs

For graphs $G$ and $H$ , we write $G \overset{\mathrm{rb}}{\longrightarrow} H$ if any proper edge-coloring of $G$ contains a rainbow copy of $H$ , i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow}H$ is at most $n^{-1/m_2(H)}$ . Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$ . In this paper, we devise a framework that provides a richer and more complex family of such graphs that includes all the previously known examples.

preprint2022arXiv

Weak saturation numbers of complete bipartite graphs in the clique

The notion of weak saturation was introduced by Bollobás in 1968. Let $F$ and $H$ be graphs. A spanning subgraph $G \subseteq F$ is weakly $(F,H)$ -saturated if it contains no copy of $H$ but there exists an ordering $e_1,\ldots,e_t$ of $E(F)\setminus E(G)$ such that for each $i \in [t]$ , the graph $G \cup \{e_1,\ldots,e_i\}$ contains a copy $H'$ of $H$ such that $e_i \in H'$ . Define $wsat(F,H)$ to be the minimum number of edges in a weakly $(F,H)$ -saturated graph. In this paper, we prove for all $t \ge 2$ and $n \ge 3t-3$ , that $wsat(K_n,K_{t,t}) = (t-1)(n + 1 - t/2)$ , and we determine the value of $wsat(K_n,K_{t-1,t})$ as well. For fixed $2 \le s < t$ , we also obtain bounds on $wsat(K_n,K_{s,t})$ that are asymptotically tight.

preprint2019arXiv

The size-Ramsey number of powers of bounded degree trees

Given a positive integer $s$ , the $s$ -colour size-Ramsey number of a graph $H$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that, in any colouring of $E(G)$ with $s$ colours, there is a monochromatic copy of $H$ . We prove that, for any positive integers $k$ and $s$ , the $s$ -colour size-Ramsey number of the $k$ th power of any $n$ -vertex bounded degree tree is linear in $n$ . As a corollary we obtain that the $s$ -colour size-Ramsey number of $n$ -vertex graphs with bounded treewidth and bounded degree is linear in $n$ , which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan [The size Ramsey number of graphs with bounded treewidth, arXiv:1906.09185 (2019)].

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.