Source author record

Alexander Moreira

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the Rank, Kernel, and Core of Sparse Random Graphs

We study the rank of the adjacency matrix $A$ of a random Erdos Renyi graph $G\sim \mathbb{G}(n,p)$ . It is well known that when $p = (\log(n) - ω(1))/n$ , with high probability, $A$ is singular. We prove that when $p = ω(1/n)$ , with high probability, the corank of $A$ is equal to the number of isolated vertices remaining in $G$ after the Karp-Sipser leaf-removal process, which removes vertices of degree one and their unique neighbor. We prove a similar result for the random matrix $B$ , where all entries are independent Bernoulli random variables with parameter $p$ . Namely, we show that if $H$ is the bipartite graph with bi-adjacency matrix $B$ , then the corank of $B$ is with high probability equal to the max of the number of left isolated vertices and the number of right isolated vertices remaining after the Karp-Sipser leaf-removal process on $H$ . Additionally, we show that with high probability, the $k$ -core of $\mathbb{G}(n, p)$ is full rank for any $k \geq 3$ and $p = ω(1/n)$ . This partially resolves a conjecture of Van Vu for $p = ω(1/n)$ . Finally, we give an application of the techniques in this paper to gradient coding, a problem in distributed computing.

preprint2020arXiv

On the subgraph query problem

Given a fixed graph $H$ , a real number $p\in(0,1)$ , and an infinite Erdős-Rényi graph $G\sim G(\infty,p)$ , how many adjacency queries do we have to make to find a copy of $H$ inside $G$ with probability $1/2$ ? Determining this number $f(H,p)$ is a variant of the {\it subgraph query problem} introduced by Ferber, Krivelevich, Sudakov, and Vieira. For every graph $H$ , we improve the trivial upper bound of $f(H,p) = O(p^{-d})$ , where $d$ is the degeneracy of $H$ , by exhibiting an algorithm that finds a copy of $H$ in time $o(p^{-d})$ as $p$ goes to $0$ . Furthermore, we prove that there are $2$ -degenerate graphs which require $p^{-2+o(1)}$ queries, showing for the first time that there exist graphs $H$ for which $f(H,p)$ does not grow like a constant power of $p^{-1}$ as $p$ goes to $0$ . Finally, we answer a question of Feige, Gamarnik, Neeman, Rácz, and Tetali by showing that for any $δ< 2$ , there exists $α< 2$ such that one cannot find a clique of order $α\log_2 n$ in $G(n,1/2)$ in $n^δ$ queries.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.