English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a graph $G=(V,E)$, an integer $k$, and a function $f_G:V^k \times V^k\to {0,1}$, the $k^{th}$ graph product of $G$ w.r.t $f_G$ is the graph withvertex set $V^k$, and an edge between two vertices $x=(x_1,...,x_k)$ and$y=(y_1,...,y_k)$ iff $f_G(x,y)=1$. Graph products are a basic combinatorialobject, widely studied and used in different areas such as hardness ofapproximation, information theory, etc. We study graph products for functions$f_G$ of the form $f_G(x,y)=1$ iff there are at least $t$ indices $i \in [k]$s.t. $(x_i,y_i)\in E$, where $t \in [k]$ is a fixed parameter in $f_G$. Thisframework generalizes the well-known graph tensor-product (obtained for $t=k$)and the graph or-product (obtained for $t=1$). The property that interests usis the edge distribution in such graphs. We show that if $G$ has a spectralgap, then the number of edges connecting "large-enough" sets in $G^k$ is"well-behaved", namely, it is close to the expected value, had the sets beenrandom. We extend our results to bi-partite graph products as well. For abi-partite graph $G=(X,Y,E)$, the $k^{th}$ bi-partite graph product of $G$w.r.t $f_G$ is the bi-partite graph with vertex sets $X^k$ and $Y^k$ and edgesbetween $x \in X^k$ and $y \in Y^k$ iff $f_G(x,y)=1$. Finally, for both typesof graph products, optimality is asserted using the "Converse to the ExpanderMixing Lemma" obtained by Bilu and Linial in 2006. A byproduct of our prooftechnique is a new explicit construction of a family of co-spectral graphs.

Edge distribution in generalized graph products