Topic: Toric ideals on Expected value of Structure Functions in Random Graphs
Goal: to understand the toric ideal where the exponents $h_i$ and $s_j$ are st-vertex-cuts of a digraph

\begin{equation} f_{ij}(p)\in \prod_i x_i^{h_i} -\prod_i x_j^{s_j}. \end{equation}


\begin{equation} f_{ij}(p) = \mathbb E\left[(\phi(G')\mid j\not\in V(G')\right] - \mathbb E\left[\phi(G')\mid i\not\in V(G')\right]. \end{equation}


  • $G'=(V,A)$ is a random digraph

  • $f_{ij}(p)$ is a polynomial where $p$ is a probability and each of $i,j$ refer to a vertex of $G'$

  • $\mathbb E$ is expected value

  • $\phi$ is the structure function of $G'$

  • vertex-cut is a vertex partition $V_{\text{outside cut}}\cup V_{\text{cut}}=V$

  • st-vertex-cut is a vertex cut where vertices $s$ and $t$ are not connected by any path in $G'-V_{\text{cut}}$ where $-$ refers to vertex deletion


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.