Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge Minors in Expanders
116
0
0.0
(
0
)
Added by
Rachit Nimavat
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function $f(n,alpha,d)$, such that every $n$-vertex $alpha$-expander with maximum vertex degree at most $d$ contains {bf every} graph $H$ with at most $f(n,alpha,d)$ edges and vertices as a minor? Our main result is that there is some universal constant $c$, such that $f(n,alpha,d)geq frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$. This bound achieves a tight dependence on $n$: it is well known that there are bounded-degree $n$-vertex expanders, that do not contain any grid with $Omega(n/log n)$ vertices and edges as a minor. The best previous result showed that $f(n,alpha,d) geq Omega(n/log^{kappa}n)$, where $kappa$ depends on both $alpha$ and $d$. Additionally, we provide a randomized algorithm, that, given an $n$-vertex $alpha$-expander with maximum vertex degree at most $d$, and another graph $H$ containing at most $frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$ vertices and edges, with high probability finds a model of $H$ in $G$, in time poly$(n)cdot (d/alpha)^{Oleft( log(d/alpha) right)}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,alpha,d)=Omega left(frac{nalpha^2}{d^2log n} right)$, and provide an efficient algorithm, that, given an $n$-vertex $alpha$-expander of maximum vertex degree at most $d$, and a graph $H$ with $Oleft( frac{nalpha^2}{d^2log n} right)$ vertices and edges, finds a model of $H$ in $G$. Finally, we observe that expanders are the `most minor-rich family of graphs in the following sense: for every $n$-vertex and $m$-edge graph $G$, there exists a graph $H$ with $O left( frac{n+m}{log n} right)$ vertices and edges, such that $H$ is not a minor of $G$.
rate research
Read More
We develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition, and as a step in the argument we give a graph partitioning algorithm with expansion and minimum degree conditions on the subgraphs induced by each part. These results extend previous work of Jenssen, Keevash, and Perkins (2019) on the Potts model and related problems in expander graphs, and of Oveis Gharan and Trevisan (2014) on partitioning into expanders.
We introduce a notion called entropic independence for distributions $mu$ defined on pure simplicial complexes, i.e., subsets of size $k$ of a ground set of elements. Informally, we call a background measure $mu$ entropically independent if for any (possibly randomly chosen) set $S$, the relative entropy of an element of $S$ drawn uniformly at random carries at most $O(1/k)$ fraction of the relative entropy of $S$, a constant multiple of its ``share of entropy. Entropic independence is the natural analog of spectral independence, another recently established notion, if one replaces variance by entropy. In our main result, we show that $mu$ is entropically independent exactly when a transformed version of the generating polynomial of $mu$ can be upper bounded by its linear tangent, a property implied by concavity of the said transformation. We further show that this concavity is equivalent to spectral independence under arbitrary external fields, an assumption that also goes by the name of fractional log-concavity. Our result can be seen as a new tool to establish entropy contraction from the much simpler variance contraction inequalities. A key differentiating feature of our result is that we make no assumptions on marginals of $mu$ or the degrees of the underlying graphical model when $mu$ is based on one. We leverage our results to derive tight modified log-Sobolev inequalities for multi-step down-up walks on fractionally log-concave distributions. As our main application, we establish the tight mixing time of $O(nlog n)$ for Glauber dynamics on Ising models with interaction matrix of operator norm smaller than $1$, improving upon the prior quadratic dependence on $n$.
Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are close to each other. We study the following question: Construct an an infinite sequence of expanders $G_0,G_1,dots$, such that for every two consecutive graphs $G_i$ and $G_{i+1}$, $G_{i+1}$ can be obtained from $G_i$ by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from $G_i$ to $G_{i+1}$. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of $d$-regular expanders with expansion cost at most $5d/2$, for any $dgeq 6$. Our construction leverages the notion of a 2-lift of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to interpolate between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the self-healing model.
A clique minor in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The Hadwiger number h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the Cartesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwigers Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwigers Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwigers Conjecture holds for G*H. On the other hand, we prove that Hadwigers Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and has no small separator. This answers a question of Pak [SODA, 2002]. As a corollary, it shows that sparse (constant degree) regular graphs with many well-mixing vertices have a long cycle, improving a result of Pak. Furthermore, such cycle can be found in polynomial time. Secondly, we show that if the random walks from a positive fraction of vertices are well-mixing, then the random walks from almost all vertices are well-mixing (with a slightly worse mixing time).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
