My Publications

3) Dellamonica and Yoshiharu Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings, The Electronic Journal of Combinatorics, vol 15(1), R127.

Abstract: An $(n, d)$-expander is a graph $G = (V , E)$ such that for every $X \subseteq V$ with $|X| \leq 2n - 2$ we have $|\Gamma_G(X)| \geq (d + 1)|X|$. A tree $T$ is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any $(n, d)$-expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs $G$ of $(N, D, \lambda)$-graphs $\Lambda$, as long as $G$ contains a positive fraction of the edges of $\Lambda$ and $\lambda/D$ is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the $(n, d)$-expander G is a subgraph of an $(N, D, \lambda)$-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem.
Our approach is based on a reduction of the tree embedding problem to a certain online matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

2) Dellamonica, Martin Marciniszyn, Yoshiharu Kohayakawa and Angelika Steger, The resilience of long cycles in random graphs, The Electronic Journal of Combinatorics, vol 15(1), R32.

Abstract: In this paper, we deal with the following two notions: global resilience and local resilience. In the former, we are interested in properties of random graphs that are inherited by any subgraph with at least some fraction $\alpha$ of the edges of the original graph. In the latter, the subgraphs considered are such that every vertex in the subgraph have at least some fraction $\alpha$ of the edges of the random graph.
Let $G = G_{n, p}$ be a random graph with $p \gg n^{-1}$. We prove that, with high probability, any subgraph of $G$ having a fraction $(1 - w(\alpha)) (\alpha + w(\alpha)) + o(1)$ of the edges of $G$, where $w(a) = 1 - (1 - \alpha) \lfloor (1 - \alpha)^{-1} \rfloor$, contains a cycle of length $(1-\alpha) n$. As for the local resilience, we have, for any $0 < \alpha < 1/2$, with high probability, the following: if $G' \subset G$ is such that $d_{G'}(v) > \Big( \frac{1}{2} + o(1) \Big) d_G(v)$ for all $v \in V(G)$ then $G'$ contains a cycle of length $(1 - \alpha) n$.

1) Dellamonica, Paulo J. S. Silva, Carlos Humes Jr, Nina S. T. Hirata and Junior Barrera, An Exact Algorithm for Optimal MAE Stack Filter Design, IEEE Transactions on Image Processing, vol. 16, issue 2, pages 453-462, 2007

Also presented at the International Symposium on Mathematical Programming, Rio de Janeiro, 2006

Abstract: We propose a new algorithm for optimal MAE stack filter design. It is based on three main ingredients. First, we show that the dual of the integer programming formulation of the filter design problem is a minimum cost network flow problem. Next, we present a decomposition principle that can be used to break this dual problem into smaller subproblems. Finally, we propose a specialization of the network Simplex algorithm based on column generation to solve these smaller subproblems. Using our method, we were able to efficiently solve instances of the filter problem with window size up to 25 pixels. To the best of our knowledge, this is the largest dimension for which this problem was ever solved exactly

Conference Proceedings

Dellamonica and Vojtech Rödl, Hereditary quasirandom properties of hypergraphs, Electronic notes in Discrete Mathematics Vol. 34, p. 495-499, click here

A full version of the paper is listed below.

Dellamonica, An asymmetric condenser, presented at LATIN 2008. Published proceedings on Lecture Notes on Computer Science, Vol. 4957, pp. 664-675, Springer, 2008.

PDF download

Abstract: Condensers are functions which receive two inputs—a random string of bits chosen according to some unknown distribution and an independent uniform (short) seed—and output a string of bits which somehow preserves the randomness of the input. The parameters of interest here are the seed length, output length and how much randomness is preserved.

Here we present explicit algorithms for condensers which have constant seed size. Our constructions improve on previous constant-seed condensers of Barak et al(2003). When the input distribution has high min-entropy, we provide a condenser having optimal rate and seed chosen from $\{1, 2, 3\}$. The analysis of this construction is considerably simpler than those of previous constructions. For the low min-entropy regime, we provide a different construction which can be viewed as a pseudorandom coloring of hypergraphs. The analysis of this condenser involves a generalization of the celebrated Balog-Szemerédi-Gowers Theorem. As an example of the simplicity of the ideas behind this generalization, we give a simpler alternative proof of the Bourgain-Katz-Tao sum-product estimates.

Dellamonica, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Universality of random graphs

PDF download

Abstract: For any $d \in \mathbb{N}$, with high probability, the random graph $G_{n, p}$, with $p = C(d) n^{-\frac{1}{2d}} \log^{\frac{1}{d}} n}$, contains all graphs on $n$ vertices with maximum degree at most $d$. In other words, $G_{n, p}$ is almost surely universal with respect to $n$-vertex graphs of bounded (constant) degree.

This paper was presented at SODA 2008.

Domingos Dellamonica Jr and Yoshiharu Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (Extended Abstract) on SODA - Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithms, Miami, 2006

A journal version of this paper which fixes an error in the extended abstract is listed above

Preprints

Dellamonica and Vojtech Rödl, Hereditary quasirandom properties of hypergraphs

Abstract: Thomason and Chung, Graham and Wilson were the first to investigate systematically properties of quasirandom graphs. They have stated several quite disparate graph properties---such as having uniform edge distribution or containing a prescribed number of certain subgraphs---and proved that these properties are equivalent in a deterministic sense.

Simonovits and Sós introduced a hereditary property (which we call S) stating the following: for a small fixed graph $L$, a graph $G$ on $n$ vertices is said to have the property S if for every set $X \subseteq V(G)$, the number of labeled copies of $L$ in $G[X]$ (the subgraph of $G$ induced by the vertices of $X$) is given by $2^{-e(L)} |X|^{v(L)} + o(n^{v(L)})$. They have shown that S is equivalent to the other quasirandom properties.

In this paper we give a natural extension of the result of Simonovits and Sós to $k$-uniform hypergraphs, answering a question of Conlon et al. Our approach yields an alternative, and perhaps simpler, proof of their theorem.

Download the technical report.

Submitted

Dellamonica, The size-Ramsey number of trees

Abstract: Given a graph $G$, the size-Ramsey number $\hat{r}(G)$ is the minimum number $m$ for which there exists a graph $F$ on $m$ edges such that any two-coloring of the edges of $F$ admits a monochromatic copy of $G$.

In 1983, J. Beck introduced an invariant $\beta(\cdot)$ for trees and showed that $\hat{r}(T) = \Omega(\beta(T))$. Moreover he conjectured that $\hat{r}(T) = \Theta(\beta(T))$. We settle this conjecture by providing a family of graphs and an embedding scheme for trees.

Download the technical report.

Submitted

Dellamonica, Spanning trees of small degree

Abstract: In this paper we show that pseudo-random graphs contain spanning trees of maximum degree $3$. More specifically, $(n, d, \lambda)$-graphs with sufficiently large spectral gap contain such spanning trees.

Download the technical report.

Co-authors