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

Teaching

  •   Current

    No teaching this semester

Filter by type:

Sort by year:

SelectedCut distance identifying graphon parameters over weak* limits

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

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.

SelectedRelating 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. We prove that a sequence W_1,W_2,W_3,... 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',... that are weakly isomorphic to W_1,W_2,W_3,.... 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 graphons. These results are more naturally phrased in the Vietoris hyperspace K(W) over graphons with the weak* topology. We show that graphons with the cut distance topology are homeomorphic to a closed subset of K(W), and deduce several consequences of this fact. From these concept 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 <>.

Independent sets, cliques, and colorings in graphons

Jan Hladký, Israel Rocha
Preprints

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.

SelectedLayout of random circulant graphs

Richter, Sebastian and Rocha, Israel.
Journal PaperLinear 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) mod n are adjacent, then every two vertices z and (z+d) 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$-\emph{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\H{o}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.

Improvements on Spectral Bisection

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 give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph G=(W∪B, E). This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time O(|W∪B|^3).

Eternal Picaria

Larsson, Urban and Rocha, Israel.
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).

SelectedA Fiedler-like theory for the perturbed Laplacian.

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

Abstract

The perturbed Laplacian matrix of a graph G is defined as DL = D−A, where D is any diagonal matrix and A is a weighted adjacency matrix of G. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those 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.

Characterizing the second smallest eigenvalue of the normalized Laplacian of a tree

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 Sk(T) of the k largest Laplacian eigenvalues of an n-vertex tree T with diameter at least four, where k is in {1,...,n}.

SelectedOn the sum of the Laplacian eigenvalues of a tree

Fritscher, Eliseu; Hoppen, Carlos; Rocha, Israel and Trevisan, Vilmar.
Journal PaperLinear 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 is 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 Aq - of the family of trees known as caterpillars. We show that all but one tree in Aq is a type II tree. We give bounds for the algebraic connectivity in Aq and exhibit the tree attaining the bounds. Finally we give a total order in Aq by algebraic connectivity.