We consider the following matching-based routing problem. Initially, each vertex
v
of a connected graph
G
is occupied by a pebble which has a unique destination
π
(
v
)
. In each round the pebbles ...across the edges of a selected matching in
G
are swapped, and the goal is to route each pebble to its destination vertex in as few rounds as possible. We show that if
G
is a sufficiently strong
d
-regular spectral expander then any permutation
π
can be achieved in
O
(
log
n
)
rounds. This is optimal for constant
d
and resolves a problem of Alon et al. (SIAM J Discret Math 7:516–530, 1994).
Matchings in Benjamini--Schramm convergent graph sequences Abért, Miklós; Csikvári, Péter; Frenkel, Péter ...
Transactions of the American Mathematical Society,
June 1, 2016, 20160601, 2016-6-00, Volume:
368, Issue:
6
Journal Article
Peer reviewed
Open access
matching measure of a finite graph as the uniform distribution on the roots of the matching polynomial of the graph. We analyze the asymptotic behavior of the matching measure for graph sequences ...with bounded degree.
Expander ℓ0-decoding Mendoza-Smith, Rodrigo; Tanner, Jared
Applied and computational harmonic analysis,
November 2018, 2018-11-00, Volume:
45, Issue:
3
Journal Article
Peer reviewed
We introduce two new algorithms, Serial-ℓ0 and Parallel-ℓ0 for solving a large underdetermined linear system of equations y=Ax∈Rm when it is known that x∈Rn has at most k<m nonzero entries and that A ...is the adjacency matrix of an unbalanced left d-regular expander graph. The matrices in this class are sparse and allow a highly efficient implementation. A number of algorithms have been designed to work exclusively under this setting, composing the branch of combinatorial compressed-sensing (CCS).
Serial-ℓ0 and Parallel-ℓ0 iteratively minimise ‖y−Axˆ‖0 by successfully combining two desirable features of previous CCS algorithms: the coordinate selection strategy of ER1 for updating xˆ, and the parallel updating mechanism of SMP2. We are able to link these elements and guarantee convergence in O(dnlogk) operations by introducing a randomised scaling of columns in A, with scaling chosen independent of the measured vector. We also empirically observe that the recovery properties of Serial-ℓ0 and Parallel-ℓ0 degrade gracefully as the signal is allowed to have its non-zero values chosen adversarially.
Moreover, we observe Serial-ℓ0 and Parallel-ℓ0 to be able to solve large scale problems with a larger fraction of nonzeros than other algorithms when the number of measurements is substantially less than the signal length; in particular, they are able to reliably solve for a k-sparse vector x∈Rn from m expander measurements with n/m=103 and k/m up to four times greater than what is achievable by ℓ1-regularisation from dense Gaussian measurements. Additionally, due to their low computational complexity, Serial-ℓ0 and Parallel-ℓ0 are observed to be able to solve large problems sizes in substantially less time than other algorithms for compressed sensing. In particular, Parallel-ℓ0 is structured to take advantage of massively parallel architectures.
We prove that in all regular robust expanders G$$ G $$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching M$$ M $$. We also show that given any fixed ...matching or spanning regular graph N$$ N $$ in G$$ G $$, the random variable |M∩E(N)|$$ \mid M\cap E(N)\mid $$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.
Given an n‐vertex pseudorandom graph G and an n‐vertex graph H with maximum degree at most two, we wish to find a copy of H in G, that is, an embedding φ:V(H)→V(G) so that φ(u)φ(v)∈E(G) for all ...uv∈E(H). Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in G. Here, we provide a deterministic polynomial time algorithm that finds a given H in any suitably pseudorandom graph G. The pseudorandom graphs we consider are (p,λ)‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, Ω(pn). A (p,λ)‐bijumbled graph is characterised through the discrepancy property: |e(A,B)−p|A||B||<λ|A||B| for any two sets of vertices A and B. Our condition λ=O(p2n/logn) on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.
In a lossless compression system with target lengths, a compressor maps an integer m and a binary string x to an m-bit code p, and if m is sufficiently large, a decompressor reconstructs x from p. We ...call a pair (m,x) achievable for ( , ) if this reconstruction is successful. We introduce the notion of an optimal compressor opt by the following universality property: For any compressor-decompressor pair ( , ), there exists a decompressor ′ such that if (m,x) is achievable for ( , ), then (m + Δ , x) is achievable for ( opt, ′), where Δ is some small value called the overhead. We show that there exists an optimal compressor that has only polylogarithmic overhead and works in probabilistic polynomial time. Differently said, for any pair ( , ), no matter how slow is, or even if is non-computable, opt is a fixed compressor that in polynomial time produces codes almost as short as those of . The cost is that the corresponding decompressor is slower. We also show that each such optimal compressor can be used for distributed compression, in which case it can achieve optimal compression rates as given in the Slepian–Wolf theorem and even for the Kolmogorov complexity variant of this theorem.
Let G=(V(G),E(G)) be a graph with vertex set V(G) and edge set E(G). The subdivision graph S(G) of a graph G is the graph obtained by inserting a new vertex into every edge of G. Let G1 and G2 be two ...vertex disjoint graphs. The subdivision-vertex neighbourhood corona of G1 and G2, denoted by G1G2, is the graph obtained from S(G1) and |V(G1)| copies of G2, all vertex disjoint, and joining the neighbours of the ith vertex of V(G1) to every vertex in the ith copy of G2. The subdivision-edge neighbourhood corona of G1 and G2, denoted by G1⊟G2, is the graph obtained from S(G1) and |I(G1)| copies of G2, all vertex disjoint, and joining the neighbours of the ith vertex of I(G1) to every vertex in the ith copy of G2, where I(G1) is the set of inserted vertices of S(G1). In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of G1G2 (respectively, G1⊟G2) in terms of the corresponding spectra of G1 and G2. As applications, these results enable us to construct infinitely many pairs of cospectral graphs, and using the results on the Laplacian spectra of subdivision-vertex neighbourhood coronae, new families of expander graphs are constructed from known ones.
It was shown in previous work that a vector <inline-formula><tex-math notation="LaTeX">\mathbf{x} \in \mathbb {R}^n</tex-math></inline-formula> with at most <inline-formula><tex-math ...notation="LaTeX">k < n</tex-math> </inline-formula> nonzeros can be recovered from an expander sketch <inline-formula><tex-math notation="LaTeX"> \mathbf{A}\mathbf{x}</tex-math></inline-formula> in <inline-formula><tex-math notation="LaTeX"> \mathcal{O}(\text{nnz}(\mathbf{A})\log k)</tex-math></inline-formula> operations via the parallel-<inline-formula> <tex-math notation="LaTeX">\ell _0</tex-math></inline-formula> decoding algorithm, where <inline-formula> <tex-math notation="LaTeX">\text{nnz}(\mathbf{A})</tex-math></inline-formula> denotes the number of nonzero entries in <inline-formula><tex-math notation="LaTeX">\mathbf{A} \in \mathbb {R}^{m \times n}</tex-math></inline-formula>. In this paper, we present the robust-<inline-formula><tex-math notation="LaTeX">\ell _0</tex-math></inline-formula> decoding algorithm, which robustifies parallel-<inline-formula><tex-math notation="LaTeX">\ell _0</tex-math> </inline-formula> when the sketch <inline-formula><tex-math notation="LaTeX">\mathbf{A}\mathbf{x}</tex-math> </inline-formula> is corrupted by additive noise. This robustness is achieved by approximating the asymptotic posterior distribution of values in the sketch given its corrupted measurements. We provide analytic expressions that approximate these posteriors under the assumptions that the nonzero entries in the signal and the noise are drawn from continuous distributions. Numerical experiments presented show that robust-<inline-formula><tex-math notation="LaTeX"> \ell _0</tex-math></inline-formula> is superior to existing greedy and combinatorial compressed sensing algorithms in the presence of small to moderate signal-to-noise ratios in the setting of Gaussian signals and Gaussian additive noise.
PDF
