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.
Czech Academy of Sciences.
Department of Theoretical Computer Science
Dalhousie University, Canada.
Department of Mathematics and Statistics
Technische Universität Chemnitz, Germany. Fakultät für Mathematik
Ph.D. in Applied mathematics
Universidade Federal do Rio Grande do Sul, Brazil
M.Sc. in Applied mathematics
Universidade Federal do Rio Grande do Sul, Brazil
Bachelor in Mathematics
Universidade Federal do Rio Grande do Sul, Brazil
Differential and Integral Calculus I
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.
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.
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.
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.
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 <
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.
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.
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.
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$.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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\}$.
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.
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.
Differential and Integral Calculus I
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.
Israel Rocha
Institute of Computer Science, Czech Academy of Sciences
Pod Vodarenskou vezi 271/2
182 07 Praha 8, Czech Republic
Office: 211