B. P. Cavalar

activity

20192022

collaborators

5 papers

math.CO2022

Directed graphs with lower orientation Ramsey thresholds

Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa +2

We investigate the threshold $p_{H} = p_{H} (n)$ for the Ramsey-type property $G (n, p) \to H$ , where $G (n, p)$ is the binomial random graph and $G \to H$ indicates that…

cs.CC2021

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

Bruno P. Cavalar, Zhenjian Lu

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite…

math.CO2020

Orientation Ramsey thresholds for cycles and cliques

Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa +1

If $G$ is a graph and $H$ is an oriented graph, we write $G \to H$ to say that every orientation of the edges of $G$ contains $H$ as a subdigraph. We consider the cas…

math.CO2020

Anti-Ramsey threshold of cycles

Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Guilherme Oliveira Mota +1

For graphs $G$ and $H$ , let $G ⟶ rb H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$ . Exte…

math.CO2019

Ramsey-type problems in orientations of graphs

Bruno Pasqualotto Cavalar

Given an acyclic oriented graph $H$ and a graph $G$ , we write $G \to H$ if every orientation of $G$ has an oriented copy of $H$ . We define $R (H)$ as t…