Source author record

Rudini Menezes Sampaio

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

ResearcherUnclaimed source record

Computational Complexity math.CO math.PR Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Edge-colorings of graphs avoiding complete graphs with a prescribed coloring

Given a graph $F$ and an integer $r \ge 2$ , a partition $\widehat{F}$ of the edge set of $F$ into at most $r$ classes, and a graph $G$ , define $c_{r, \widehat{F}}(G)$ as the number of $r$ -colorings of the edges of $G$ that do not contain a copy of $F$ such that the edge partition induced by the coloring is isomorphic to the one of $F$ . We think of $\widehat{F}$ as the pattern of coloring that should be avoided. The main question is, for a large enough $n$ , to find the (extremal) graph $G$ on $n$ vertices which maximizes $c_{r, \widehat{F}}(G)$ . This problem generalizes a question of Erd{\H o}s and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where $F$ is a clique and the partition $\widehat{F}$ contains a single class). We use Hölder's Inequality together with Zykov's Symmetrization to prove that, for any $r \geq 2$ , $k \geq 3$ and any pattern $\widehat{K_k}$ of the clique $K_k$ , there exists a complete multipartite graph that is extremal. Furthermore, if the pattern $\widehat{K_k}$ has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that $r=3$ and $\widehat{F}$ is a rainbow triangle (that is, where $F=K_3$ and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for $r=3$ , we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.

preprint2015arXiv

The maximum time of 2-neighbor bootstrap percolation: complexity results

In 2-neighborhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time t(G) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved \cite{eurocomb13} that deciding whether $t(G)\geq k$ is polynomial time solvable for k=2, but is NP-Complete for k=4 and, if the problem is restricted to bipartite graphs, it is NP-Complete for k=7. In this paper, we solve the open questions. We obtain an $O(mn^5)$ -time algorithm to decide whether $t(G)\geq 3$ . For bipartite graphs, we obtain an $O(mn^3)$ -time algorithm to decide whether $t(G)\geq 3$ , an $O(m^2n^9)$ -time algorithm to decide whether $t(G)\geq 4$ and we prove that $t(G)\geq 5$ is NP-Complete.

preprint2015arXiv

The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results

In 2-neighborhood bootstrap percolation on a graph $G$ , an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least two already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved by Benevides et al \cite{eurocomb13} that $t(G)$ is NP-hard for planar graphs and that deciding whether $t(G)\geq k$ is polynomial time solvable for $k\leq 2$ , but is NP-complete for $k\geq 4$ . They left two open problems about the complexity for $k=3$ and for planar bipartite graphs. In 2014, we solved the first problem\cite{wg2014}. In this paper, we solve the second one by proving that $t(G)$ is NP-complete even in grid graphs with maximum degree 3. We also prove that $t(G)$ is polynomial time solvable for solid grid graphs with maximum degree 3. Moreover, we prove that the percolation time problem is W[1]-hard on the treewidth of the graph, but it is fixed parameter tractable with parameters treewidth $+k$ and maxdegree $+k$ .

preprint2012arXiv

Limits of permutation sequences

A permutation sequence is said to be convergent if the density of occurrences of every fixed permutation in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function $Z:[0,1]^2 \to [0,1]$ with the additional properties that, for every fixed $x \in [0,1]$ , the restriction $Z(x,\cdot)$ is a cumulative distribution function and, for every $y \in [0,1]$ , the restriction $Z(\cdot,y)$ satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An ingredient in the proofs is a new model of random permutations, which generalizes previous models and might be interesting for its own sake.

preprint2011arXiv

Fixed parameter algorithms for restricted coloring problems

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$ -tidy graphs and $(q,q-4)$ -graphs, for every fixed $q$ . These classes include cographs, $P_4$ -sparse and $P_4$ -lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$ , which is the minimum $q$ such that $G$ is a $(q,q-4)$ -graph. We also prove that every connected $(q,q-4)$ -graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.

preprint2011arXiv

Limits of permutation sequences through permutation regularity

A permutation sequence $(σ_n)_{n \in \mathbb{N}}$ is said to be convergent if, for every fixed permutation $τ$ , the density of occurrences of $τ$ in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function $Z:[0,1]^2 \to [0,1]$ with the additional properties that, for every fixed $x \in [0,1]$ , the restriction $Z(x,\cdot)$ is a cumulative distribution function and, for every $y \in [0,1]$ , the restriction $Z(\cdot,y)$ satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An important ingredient in the proofs is a new model of random permutations, which generalizes previous models and is interesting for its own sake.

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.