### Education

• Ph.D. 2015

Ph.D. in Applied mathematics

Universidade Federal do Rio Grande do Sul, Brazil

• M.Sc.2012

M.Sc. in Applied mathematics

Universidade Federal do Rio Grande do Sul, Brazil

• B.Sc.2010

Bachelor in Mathematics

Universidade Federal do Rio Grande do Sul, Brazil

•   Current

### Filter by type:

Sort by year:

#### A graphon perspective for fractional isomorphism

Jan Grebík and Israel Rocha
Conference paperActa Mathematica Universitatis Comenianae, 88(3), 759-765, 2019.

#### Abstract

Fractional isomorphism of graphs plays an important role in practical applications of graph isomorphism test by means of the color refinement algorithm. We introduce a suitable generalization to the space of graphons in terms of Markov opertors on a Hilbert space, provide characterizations in terms of a push-forward of the graphon to a quotient space and also in terms of measurable partitions of the underlying space. Our proofs use a weak version of the mean ergodic theorem, and correspondences between objects such as Markov projections, sub-$\sigma$-algebras, measurable decompositions, etc. That also provides an alternative proof for the characterizations of fractional isomorphism of graphs without the use of Birkhoff\textendash von Neumann Theorem.

#### Brouwer's conjecture holds asymptotically almost surely

Israel Rocha
Preprints Selected Publication

#### Abstract

We show that for a sequence of random graphs Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity. Surprisingly, it was found that a similar statement holds true for weighted graphs with possible negative weights as well. For graphs with a fixed number of vertices, the result implies that there are constants $C>0$ and $n_{0}$ such that if $n\geq n_{0}$ then among all $2^{{n \choose 2}}$ graphs with $n$ vertices, at least $\left(1-\exp\left(-Cn\right)\right)2^{{n \choose 2}}$ graphs satisfy Brouwer's conjecture.

#### Cut distance identifying graphon parameters over weak* limits

Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň
Preprints Selected Publication

#### Abstract

The theory of graphons comes with the so-called cut distance. The cut distance is finer than the weak* topology. Doležal and Hladký [arXiv:1705.09160] showed, that given a sequence of graphons, a cut distance accumulation graphon can be pinpointed in the set of weak* accumulation points as minimizers of the entropy. Motivated by this, we study graphon parameters with the property that their minimizers or maximizers identify cut distance accumulation points over the set of weak* accumulation points. We call such parameters cut distance identifying. Of particular importance are cut distance identifying parameters coming from subgraph densities, $t(H,.)$. It turns out that this concept is closely related to graph norms. In particular, we prove that a connected graph H is step Sidorenko (a concept very similar to $t(H,.)$ being cut distance identifying) if and only if it is weakly norming. This answers a question of Král', Martins, Pach and Wrochna [arXiv:1802.05007]. Further, we study convexity properties of cut distance identifying graphon parameters, and find a way to identify cut distance limits using spectra of graphons.

#### Relating the cut distance and the weak* topology for graphons

Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň
Preprints

#### Abstract

The theory of graphons is ultimately connected with the so-called cut norm. In this paper, we approach the cut norm topology via the weak{*} topology (when considering a predual of $L^{1}$-functions). We prove that a sequence $W_{1},W_{2},W_{3},\ldots$ of graphons converges in the cut distance if and only if we have equality of the sets of weak{*} accumulation points and of weak{*} limit points of all sequences of graphons $W_{1}',W_{2}',W_{3}',\ldots$ that are weakly isomorphic to $W_{1},W_{2},W_{3},\ldots$. We further give a short descriptive set theoretic argument that each sequence of graphons contains a subsequence with the property above. This in particular provides an alternative proof of the theorem of Lovász and Szegedy about compactness of the space of graphons. We connect these results to <> characterization of cut distance convergence from [Ann. of Math. (2) 176 (2012), no. 1, 151-219] These results are more naturally phrased in the Vietoris hyperspace $K$ over graphons with the weak{*} topology. We show that graphons with the cut distance topology are homeomorphic to a closed subset of $K$, and deduce several consequences of this fact. From these concepts a new order on the space of graphons emerges. This order allows to compare how structured two graphons are. We establish basic properties of this structurdness order.

#### Independent sets, cliques, and colorings in graphons

Journal PaperTo appear in European Journal of Combinatorics (special issue EUROCOMB'17).

#### Abstract

We study graphon counterparts of the chromatic and the clique number, the fractional chromatic number, the b-chromatic number, and the fractional clique number. We establish some basic properties of the independence set polytope in the graphon setting, and duality properties between the fractional chromatic number and the fractional clique number. We present a notion of perfect graphons and characterize them in terms of induced densities of odd cycles and its complements.

#### Layout of random circulant graphs

Richter, Sebastian and Rocha, Israel.
Journal PaperSelected PublicationLinear Algebra and its Applications. Volume 559, 15 December 2018, Pages 95-113.

#### Abstract

A circulant graph $G$ is a graph on $n$ vertices that can be numbered from $0$ to $n-1$ in such a way that, if two vertices $x$ and $(x+d)\text{ mod }n$ are adjacent, then every two vertices $z$ and $(z+d)\text{ mod }n$ are adjacent. We call layout of the circulant graph any numbering that witness this definition. A random circulant graph results from deleting each edge of $G$ uniformly with probability $1-p$. We address the problem of finding the layout of a random circulant graph. We provide a polynomial time algorithm that approximates the solution and we bound the error of the approximation with high probability.

#### Recovering the Structure of Random Linear Graphs.

Rocha, Israel; Israel Rocha; Janssen, Jeannette and Kalyaniwalla, Nauzer.
Journal PaperLinear Algebra and its Applications. Volume 557, 15 November 2018, Pages 234-264.

#### Abstract

In a random linear graph vertices are points in a line connected with some probability if they are close together. We are concerned with large amounts of vertices n, where they are connected with some probability if their distance is at most n/2. Our problem is to reconstruct its linear embedding by recovering the natural order in which vertices are placed. We show a simple algorithm that successfully retrieve the structure of vertices that are randomly distributed. Besides, we show that this order is correct with high probability, and we quantify how many vertices are misplaced. That is the first time one fully recovers the structure of random linear graphs using this method and it serves as a proof of concept. In a forthcoming work we will deal with different models using the same technique.

#### A generalization of Erdős' matching conjecture

Christos Pelekis, Israel Rocha
Journal PaperElectronic Journal of Combinatorics. Volume 25, Issue 2, 2018.

#### Abstract

Let $\mathcal{H}=(V,\mathcal{E})$ be an $r$-uniform hypergraph on $n$ vertices and fix a positive integer $k$ such that $1\le k\le r$. A $k$-matching of $\mathcal{H}$ is a collection of edges $\mathcal{M}\subset \mathcal{E}$ such that every subset of $V$ whose cardinality equals $k$ is contained in at most one element of $\mathcal{M}$. The $k$-matching number of $\mathcal{H}$ is the maximum cardinality of a $k$-matching. A well-known problem, posed by Erdős, asks for the maximum number of edges in an $r$-uniform hypergraph under constraints on its $1$-matching number. In this article we investigate the more general problem of determining the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices subject to the constraint that its $k$-matching number is strictly less than $a$. The problem can also be seen as a generalization of the, well-known, $k$-intersection problem. We propose candidate hypergraphs for the solution of this problem, and show that the extremal hypergraph is among this candidate set when $n\ge 4r\binom{r}{k}^2\cdot a$.

#### Spectral Bisection with Two Eigenvectors

Rocha, Israel.
Conference paperElectronic Notes in Discrete Mathematics. Volume 61, Pages 1019-1025, 2017.

#### Abstract

We show a spectral bisection algorithm which makes use of the second and third eigenvector of the Laplacian matrix. This algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. To this end, we investigate combinatorial properties of certain configurations of a graph partition. These properties, that we call organized partitions, are shown to be related to the minimality and maximality of a cut. We show that organized partitions are related to the third eigenvector of the Laplacian matrix and give bounds on the minimum cut in terms of organized partitions and eigenvalues.

Rocha, Israel.
Preprints

#### Abstract

We investigate combinatorial properties of certain configurations of a graph partition which are related to the minimality of a cut. We show that such configurations are related to the third eigenvector of the Laplacian matrix. It is well known that the second eigenvector encodes structural information, and that can be used to approximate a minimum bisection. In this paper, we show that the third eigenvector carries structural information as well. We then provide a new spectral bisection algorithm using both eigenvectors. The new algorithm is guaranteed to return a cut that is smaller or equal to the one returned by the classic spectral bisection. Also, we provide a spectral algorithm that can refine a given partition and produce a smaller cut.

#### A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs.

Helmberg, Christoph; Rocha, Israel and Schwerdtfeger, Uwe.
Journal PaperSIAM Journal of Discrete Mathematics. 31(2), 1196–1216, 2017.

#### Abstract

We provide strongly polynomial time combinatorial algorithms to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph and the weighted signless Laplacian of an arbitrary graph by redistributing weights among the edges. This is accomplished by solving graph embedding problems which arise as dual programs of a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.

#### Eternal Picaria

Journal PaperRecreational Mathematics Magazine. Volume 4, Issue 7, May 2017, Pages 119–133.

#### Abstract

Picaria is a traditional board game, played by the Zuni tribe of the American Southwest and other parts of the world, such as a rural Southwest region in Sweden. It is related to the popular children's game of Tic-tac-toe, but the 2 players have only 3 stones each, and in the second phase of the game, pieces are slided, along specified move edges, in attempts to create the three-in-a-row. We provide a rigorous solution, and prove that the game is a draw; moreover our solution gives insights to strategies that players can use.

#### Absolute algebraic connectivity of double brooms and trees

Richter, Sebastian and Rocha, Israel.
Journal PaperDiscrete Applied Mathematics. Volume 201, 11 March 2016, Pages 213–221.

#### Abstract

We use a geometric technique based on embeddings of graphs to provide an explicit formula for the absolute algebraic connectivity and its eigenvectors of double brooms. Besides, we give a polynomial time combinatorial algorithm that computes the absolute algebraic connectivity of a given tree.

#### Algebraic connectivity of k-connected graphs

Kirkland, Steve; Rocha, Israel and Trevisan, Vilmar
Journal PaperCzechoslovak Mathematical Journal. v. 65, p. 219-236, 2015.

#### Abstract

Let G be a k-connected graph with k ⩾ 2. A hinge is a subset of k vertices whose deletion from G yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fielder vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (1975), and Kirkland and Fallat’s paper Perron Components and Algebraic Connectivity for Weighted Graphs (1998).

#### A Fiedler-like theory for the perturbed Laplacian.

Rocha, Israel and Trevisan, Vilmar.
Journal PaperSelected PublicationCzechoslovak Mathematical Journal. September 2016, Volume 66, Issue 3, pp 717–735

#### Abstract

The perturbed Laplacian matrix of a graph $G$ is defined as $L^D=D-A$, where $D$ is any diagonal matrix and $A$ is a weighted adjacency matrix of $G$. In this paper we develop a Fiedler-like theory for this matrix, leading to results that are of the same type obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use the notion of Perron component for the perturbed Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition.

Rocha, Israel
Preprints

#### Abstract

In this paper we show a monotonicity theorem for the harmonic eigenfunction of $\lambda_{1}$ of the normalized Laplacian over the points of articulation of a graph. We introduce the definition of Perron component for the normalized Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition.

#### Bounding the sum of the largest Laplacian eigenvalues of graphs

Rocha, Israel and Trevisan, Vilmar.
Journal PaperDiscrete Applied Mathematics. v.170, p.95 - 103, 2014.

#### Abstract

We prove that Brouwer’s conjecture holds for certain classes of graphs. We also give upper bounds for the sum of the largest Laplacian eigenvalues for graphs satisfying certain properties: those that contain a path or a cycle of a given size, graphs with a given matching number and graphs with a given maximum degree. Then we provide conditions for which these upper bounds are better than the previous known results.

#### Characterizing trees with large Laplacian energy

Fritscher, Eliseu; Hoppen, Carlos; Rocha, Israel and Trevisan, Vilmar.
Journal PaperLinear Algebra and its Applications. v.442, p.20 - 49, 2014.

#### Abstract

We investigate the problem of ordering trees according to their Laplacian energy. More precisely, given a positive integer n, we find a class of cardinality approximately $\sqrt n$ whose elements are the $n$-vertex trees with largest Laplacian energy. The main tool for establishing this result is a new upper bound on the sum $S_k(T)$ of the k largest Laplacian eigenvalues of an n-vertex tree $T$ with diameter at least four, where $k \in \{1,...,n\}$.

#### On the sum of the Laplacian eigenvalues of a tree

Fritscher, Eliseu; Hoppen, Carlos; Rocha, Israel and Trevisan, Vilmar.
Journal PaperSelected PublicationLinear Algebra and its Applications. v.435, p.371 - 399, 2011.

#### Abstract

Given an n-vertex graph $G=(V,E)$, the Laplacian spectrum of $G$ is the set of eigenvalues of the Laplacian matrix $L=D-A$, where $D$ and $A$ denote the diagonal matrix of vertex-degrees and the adjacency matrix of $G$, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where $k\in \{1,...,n\}$. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenković and Gutman.

#### Algebraic connectivity on a subclass of caterpillars

Rojo, Oscar; Rocha, Israel and Trevisan, Vilmar.
Journal PaperElectronic Notes in Discrete Mathematics. v.37, p.153-158, 2011.

#### Abstract

We study a subfamily - which we call $A_q$ - of the family of trees known as caterpillars. We show that all but one tree in $A_q$ is a type II tree. We give bounds for the algebraic connectivity in $A_q$ and exhibit the tree attaining the bounds. Finally we give a total order in $A_q$ by algebraic connectivity.