Postdoctoral Fellow
Czech Academy of Sciences.
Department of Theoretical Computer Science
At the moment, my research involves theory of graph limits. This is a new and trendy direction of research linking analysis, graph theory, and probability, with applications in statistical physics and computer science. My research interest includes spectral graph theory focusing on partitioning, clustering and connectivity problems.
I am based in Prague, in the Institute of Computer Science of the Czech Academy of Sciences. Please refer to the Extremal Graph Theory group webpage for more details about our project.
Positions
-
Current 2017
-
2017 2015
Postdoctoral Fellow
Dalhousie University, Canada.
Department of Mathematics and Statistics -
2015 2014
Research Assistant
Technische Universität Chemnitz, Germany. Fakultät für Mathematik
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
-
2016 Summer
-
2016 Winter
-
2015 Fall
MATH 1000
Differential and Integral Calculus I
Research Summary
Most of my research is in the area of Graph Theory. Graphs are mathematical structures used to model pairwise relations between objects. Such models appear in different fields of sciences such as processes in physical, biological, social and information systems.
At the moment, my research involves theory of graph limits. This is a new and trendy direction of research linking analysis, graph theory, and probability, with applications in statistical physics and computer science, for example the graphs of social networks which are huge.
A good part of my work before and after my PhD is in Spectral Graph Theory, where matrices are used to investigate graphs. There, I am interested in understanding how eigenvectors portray the structure of networks, such as community formation, connectivity, partitioning, etc.
Spectral techniques have been used for decades to successfully reveal the underlying properties of graphs. From graphs with a specific design to random graphs, and from finite to infinite graphs, I have been applying optimization, probability theory, and matrix theory to expose such properties.
Topics of Interest
- Graphs and Networks
- Matrix Theory
- Limit of dense graphs
- Clustering and Partitioning on Graphs
- Combinatorial Algorithms
Publications
Filter by type:
Sort by year:
A graphon perspective for fractional isomorphism
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.
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.
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.
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 <
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
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.
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
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
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.
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.
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
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
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.
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.
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
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
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
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
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.
Teaching
Past courses
-
2016 Summer
-
2016 Winter
-
2015 Fall
MATH 1000
Differential and Integral Calculus I
Gallery
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Contact & Meet Me
Israel Rocha
Institute of Computer Science, Czech Academy of Sciences
Pod Vodarenskou vezi 271/2
182 07 Praha 8, Czech Republic
Office: 211
- Phone: +420 266 053 830
- rocha at cs .cas .cz
-
ResearchGate
-
Lattes