0
$\begingroup$

Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?

  1. $G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\big|\leq\varepsilon|U||W|$ for any $X\subseteq U, Y\subseteq W$ with $|X|>\varepsilon|U|,|Y|>\varepsilon|W|$

  2. Let $G'$ be the random bipartite graph with bipartition $(U,W)$ and edge density $d$, the cut distance of $G$ and $G'$ (can be considered as cut norm of $G-G'$) satisfied: $d_\square(G,G')\leq\varepsilon.$

And if not equal, when $\varepsilon=0$ does these two statement equal?

Moreover "1" can be considered as one definition of "quasirandom", could "2" be considered as a definition of "quasirandom"?

$\endgroup$

0

You must log in to answer this question.