Constructing graphs with limited resources
Danial Dervovic Avinash Mocherla Simone Severini






Dissipative quantum mechanics beyond Bloch-Redfield: A consistent
  weak-coupling expansion of the ohmic spin boson model at arbitrary bias
    Danial DervovicDepartment of Computer Science, University College London, Gower Street, London WC1E 6BT, United Kingdom. Avinash MocherlaImperial College London, Kensington, London SW7 2AZ, United Kingdom. [1] Simone Severini[1] Shanghai Jiao Tong University, 1954 Huashan Rd, JiaoTong DaXue, Xuhui Qu, Shanghai Shi, China, 200000.
    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================




We discuss the amount of physical resources required to construct a given graph, where vertices are added sequentially. We naturally identify information – distinct into instructions and memory – and randomness as resources. Not surprisingly, we show that, in this framework, threshold graphs are the simplest possible graphs, since the construction of threshold graphs requires a single bit of instructions for each vertex and no use of memory. Large instructions without memory do not bring any advantage. With one bit of instructions and one bit of memory for each vertex, we can construct a family of perfect graphs that strictly includes threshold graphs. We consider the case in which memory lasts for a single time step, and show that as well as the standard threshold graphs, linear forests are also producible. We show further that the number of random bits (with no memory or instructions) needed to construct any graph is asymptotically the same as required for the Erdős-Rényi random graph. We also briefly consider constructing trees in this scheme. The problem of defining a hierarchy of graphs in the proposed framework is fully open.


Correspondence address: mailto:d.dervovic@cs.ucl.ac.uk.


§ INTRODUCTION


Alice () and Bob () work together to construct a graph. At
each time step t∈ℕ,  sends instructions to 
. Then,  constructs a graph G_t=(V(G_t),E(G_t)) according to
the instructions, by adding vertices and edges to the graph G_t-1. We
will try to work in the simplest possible setting. It will be convenient to assume that G_t is on t vertices, 1,2,…,t, and that
vertex t is added at time t. Thus, the neighbours of vertex t at time t are vertices of G_t-1. In
addition to instructions, i.e., information,  may
have access to a memory and a source of randomness (e.g.
,  can flip a coin). Of course, memory is also information, but it
seems useful to distinguish between information received at time t from
information received at time t^'<t. These three quantities will be
called resources. Notice that we do not consider potential loss of
information. In other words, when we say “ sends
instructions to ”, we do not mean that there is
an information-theoretic (noisy) channel between and .

Instructions and memory consist of bit strings – more generally, we could
use the symbols of an alphabet. We assume that memory is not required to
remember the effect of each instruction. For instance, if the instruction 1011 at time t is associated to a certain action, say a, then 1011 is
associated to a at every time t^'>t, but there is no need to
store 1011. Obviously, but importantly, no action can be performed without
the relevant resources – e.g., adding an edge between a specific
pair of vertices, making a random choice, etc. Since (t^2-t)/2
bits are needed to specify G_t exactly, it is intuitive that 
requires Θ(t^2) coin flips to construct G_t with randomness
only, whenever instructions are unavailable – see Section <ref> for a thorough description of this point. The process introduced in <cit.>, which was
originally studied in the context of graph limits, aimed at defining a
notion of likelihood for a graph G_t constructed exactly in the
way described above.

Here, we take a different perspective and look at the amount of instructions,
memory, and randomness needed by  and  for constructing
graphs. We mostly focus on the role of . The proposed framework
has clearly many variations. We skim over the basic ones. The central
question is: what graphs can  construct with the use of limited
resources?  has full freedom of interpreting instructions, but no
computational power (e.g.,  cannot count). A setting in
which graphs are seen as constructed/defined by computationally bounded
distributed agents is proposed by Arora et al. <cit.>.

We will need some standard notation. Given graphs G and H, the 
disjoint union is the graph G⊎ H such that V(G⊎ H) = V(G)⊎ V(H) and {i,j}∈ E(G⊎ H) if and only if {i,j}∈
E(G) or {i,j}∈ E(H). We denote by P_n, C_n, K_n, E_n,
and K_l,m, the n-path, the n-cycle, the complete graph on n
vertices, the empty graph on n vertices, and the complete bipartite graph
on l+m vertices, respectively. (See <cit.> for the elementary graph
theory that we use.)

Let us denote by A(G) the adjacency matrix of G. The (i,j)-th entry of A(G) is [A(G)]_i,j=1 if {i,j}∈ E(G) and [A(G)]_i,j=0,
otherwise. The following fact is obvious, but worth a mention for the sake
of completeness:


Every graph can be constructed by adding vertices sequentially.



Given a graph G on n vertices, (when G is undirected) the entries in
the triangle above the main diagonal are the significant part of A(G). Label the vertices of G by 1,2,…,n, where vertex 1 corresponds to
the n-th line of A(G), vertex 2 to the (n-1)-th line, etc. –
a line is a row or a column. Let us assume that at time t we add
vertex t=1,2,…,n. The proof follows by observing that in G_t the
neighbours of vertex t∈ V(G_t) correspond to lines t-i, with i=2,…,t-1, of A(G), and that these lines have been already completed
when adding each vertex i.




We note that threshold graphs occur frequently in this model. It is worth providing a proper description of what such a graph is.  A threshold graph is a graph which can be constructed from K_1 by a sequence of two
operations: add an isolated vertex or add a dominating vertex. Recall that a
vertex of a graph G is isolated if it has degree zero and 
dominating if it is adjacent to all other vertices of G. The family of
threshold graphs is denoted by 𝒯. We make use of the forbidden subgraphs
characterization of 𝒯 when classifying a graph as being threshold. This may also be taken as a definition  
<cit.>: a graph G is a threshold graph if G does not contain P_4, C_4 and K_2⊎ K_2 as induced subgraphs. Threshold
graphs are unigraphs (that is, completely specified by their degree sequence
up to isomorphism) and easy to recognise. Many hard computational problems
are efficiently solvable when threshold graphs are taken as instances.

In the following sections, we consider the graphs that can be constructed by adding vertices sequentially when  has access to different combinations of resources. First, we will study the simplest case, where  receives one bit instructions from . With no other information, we show that  is limited to constructing threshold graphs. In fact, these graphs prove to be constructible with any combination of resources. In the next case,  is also given access to one bit of memory, which is the ability to label each vertex with either 0 or 1 as it is placed, and thus differentiate the vertex set into two groups. We see that  is now able to give instructions which are directed at only one group of vertices, and this  extends the family of constructible graphs beyond threshold graphs, including non-threshold graphs such as bipartite and split graphs. Memory, as it turns out, has further uses when its use is modified. Specifically, we explore two variations of memory available to : fading and modifiable. In the first variation, fading memory only lasts one time step, which means that  can only remember the label of the last two placed vertices. This allows the formation of a linear forest of path graphs, among other non-threshold graphs. In the second case - modifiable memory - memory can be used to modify the edges between previously placed vertices. Despite offering a new construction mechanism for , it is shown that this does not extend the number of unique graphs beyond normal memory. 
We then consider randomness as the only resource available to , and show that the resources required to construct any graph G_n and the Erdős-Rényi random graph are equivalent in the asymptotic limit.
In the penultimate section, we modify the procedure for constructing graphs and construct trees using the resources considered previously.
The final section concludes with open questions.

To start, we consider one bit of instruction and no memory, as described above. The main result of this section is the following statement: 


Let  send to  one bit
instructions at each time step t. Furthermore, assume that  has no
memory and no randomness. Then, G_t is a threshold graph.



Let us consider the simplest possible case, which is, arguably, one bit of instruction per
vertex.  can not distinguish vertices of G_t-1, by reading their
labels, since  has no memory.  can not distinguish vertices
of G_t-1, by picking them at random, since  has no randomness. Hence, , without further information, is restricted to either placing a dominating or isolated vertex for each instruction. 
We list in a table all unique interpretations of a one bit instruction from A that are compatible with these conditions: 


    ( 0→∅) ,( 1→∅)   (0→ E),( 1→∅)
       (0→ E),( 1→ E)
         .


The notation is straightforward:




  * “0→ E" or “1→ E" means “construct {t,i}∈ E(G_t) for every i∈ V(G_t-1) when receiving instruction 0 or 1 at time t", that is, t is a dominating vertex;


  * “0→∅" or “1→∅" means “construct {t,i}∉ E(G_t)
for every i∈ V(G_t-1) when receiving instruction 0 or 1 at time t", that is, t is an isolated vertex.







The cases ( 0→∅) ,(
1→∅) and (0→ E),( 1→
E) give G_t=E_t and G_t=K_t, respectively. These are
both threshold graphs. It follows directly from the definition of a
threshold graph that the case (0→ E),( 1→∅) gives a threshold graph, since (0→ E)
introduces a dominating vertex and ( 1→∅)
introduces an isolated vertex. It is clear that instructions of
arbitrary length will not change the above table, because the number of
possible interpretations of the instructions does not increase. In summary, the families of graphs constructed by the given instructions are:

    ( 0→∅) ,( 1→∅)   (0→ E),( 1→∅)
    E_l⊎ E_m   𝒯
       (0→ E),( 1→ E)
       K_l+m
    
         .

We specify with l and m the number of vertices associated with
instruction 0 and 1 respectively.






§ ONE BIT OF INSTRUCTION AND ONE BIT OF MEMORY


Let us now consider families of graphs that  can construct with the use of an extra resource: memory. The construction method is as before. One bit instructions are sent from  to . For each instruction,  adds a vertex, and then carries out the instruction specified by said vertex. Unlike in the previous case, where all vertices were considered the same, the addition of one bit of memory  allows  to label each vertex with the instruction 0 or 1, as it is placed. Hence  can differentiate between two different groups of vertices.  is now able to send instructions which are directed at one particular group of vertices, and this increases the number of graphs that can be constructed.  For consistency, we assert that no other edge can be added to G_t-1 at
time t, meaning that, at time t^'≥ t,  is not allowed to
add an edge of the form {i,j} with both i and j in G_t-1 (The effects of removing this restriction will be studied in section 3). 
In other words: for all t' < t, G_t' is an induced subgraph of G_t on the vertices {1, …, t'}.
 
For the following analysis, we must define the standard join operation. Given graphs G and H, their join, G+H, is the graph constructed by taking the disjoint union of G and H, then connecting every vertex of G with every vertex of H.
For example, E_m + E_n = K_m,n and K_m + K_n = K_m+n.

Define the labelling function, ℓ: V(G) →{0, 1} that returns the label of a given vertex.
Unless stated otherwise, we will assume the bit string of instructions x sent by , has l vertices labelled `0' and m vertices labelled `1', that is {i ∈ V(G_t) |  ℓ(i) = 0 } = l and {i ∈ V(G_t) |  ℓ(i) = 1 } = m.
 


We also define the graphs E_(x), K_(x) and K_(x).
First, x = x_1x_2… x_n ∈{0,1}^n is a bitstring of length n. 
E_(x) is the complete bipartite graph K_l,m, where the bipartition classes are vertices labelled `0' and `1', minus edges of the form {t, t'} when x_t=0, x_t' = 1 and t < t'.
Similarly, K_(x) is the complete split graph K_l+ E_m  minus edges of the form {t, t'} when x_t=0, x_t' = 1 and t>t'.
The graph K_(x) is the graph K_l⊎ K_m plus edges of the form {t, t'} when x_t=0, x_t' = 1 and t < t'.
Our analysis results in the following proposition: 




Let  send to  one bit of instruction at
each time step t. Let us assume that  has no randomness.
Moreover, let us assume that  can assign one bit of memory for each vertex. Then, G_t is
either a threshold graph or one of the following graphs (not necessarily
threshold): 

    E_l⊎ E_m,   E_(x),   K_l⊎ E_m,   K_l,m,K_(x),   K_l+
    E_m,   K_l⊎ K_m,  K_(x),   K_l+m.




 can distinguish vertices of G_t by reading their labels, since 
 has one bit of memory for each vertex. However, the amount of
memory is only sufficient to divide V(G_t) into two classes: 0 or 1. 
cannot distinguish vertices of G_t, by picking them at random, since 
 has no randomness. As in the proof of Proposition <ref>
, we list in a table all unique interpretations of a one bit instruction from A that are
compatible with these conditions: 

    ( 0→∅) ,( 1→∅)   1|c(0→1),( 1→∅)   1|c|(0→0),( 1→∅)   (0→ E),( 1→∅)
       1|c(0→1),(1→0)   1|c|(0→0),(1→0)   (0→
    E),(1→0)
    2-32-4      1|c|(0→0),( 1→1)   (0→ E),( 1→1)
    3-4         (0→ E),( 1→ E)
      .

Here, the notation is as follows: 



  * “0→ 1" or “1→ 1" means “construct {t,i}∈ E(G_t) for every i∈ V(G_t-1) if ℓ(i) = 1 when receiving instruction 0 or 1 at time t";


  * “0→ 0" or “1→ 0" means “construct {t,i}∈ E(G_t)
for every i∈ V(G_t-1) if ℓ(i) = 0 when receiving instruction 0 or 1 at time t".




 We proceed with a case by case analysis:




  ( 0→∅),  ( 1→∅): G_t=E_l⊎ E_m and G_t∈𝒯.


  (0→ 0), ( 1→∅): G_t=K_l⊎ E_m and G_t∈𝒯.


  (0→ E), ( 1→∅): we obtain 𝒯, since this is the case of Proposition <ref>.


  (0→ 0), ( 1→ 1): G_t=K_l⊎
K_m and G_t∉𝒯 if l,m≥2.


  (0→ E), ( 1→ E): G_t=K_l+m and G_t∈𝒯


  (0→ 1), ( 1→∅): G_t = E_(x). From the instruction set, we have the edges {i, j} if and only if ℓ(i)=0 and ℓ(j)=1, j < i.
This is the definition of E_(x).


  (0→ 1), (1→ 0): G_t = K_l,m. Note that G_t ∉𝒯 for t ≥ 2.


  (0→ 0), (1→ 0): G_t = K_(x). The instructions enforce that we have edges {i, j} if and only if either: ℓ(i) = ℓ(j) = 0 for i ≠ j, or ℓ(i) = 0, ℓ(j) = 1 for j > i.
This is readily seen to be K_(x). 


  (0→ E), (1→ 0): G_t = K_l + E_m. The instructions give us all edges of the form {i, j} when either: ℓ(i) = ℓ(j) = 0 for i ≠ j or ℓ(i) =0, ℓ(j) = 1.
These edges realise the complete split graph K_l + E_m.


  (0→ E), ( 1→ 1): G_t = K_(x).
From the instruction set, we have the edges {i, j} if and only if either: ℓ(i)= ℓ(j), or ℓ(i) = 0, ℓ(j) = 1, j < i.
This graph is K_(x).



The table summarises the families: 

    ( 0→∅) ( 1→∅)   1|c(0→1)( 1→∅)   1|c|(0→0)( 1→∅)   (0→ E)( 1→∅)
    E_l⊎ E_m   1|cE_(x)   1|c|K_l⊎ E_m   𝒯
       1|c(0→1)(1→0)   1|c|(0→0)(1→0)   (0→
    E)(1→0)
       1|cK_l,m   1|c|K_(x)   K_l+ E_m
    2-4      1|c|(0→0)( 1→1)   (0→ E)( 1→1)
          1|c|K_l⊎ K_m   K_(x)
    3-4         (0→ E)( 1→ E)
             K_l+m
        .







§ USING MEMORY TO MODIFY G_T-1
 
In earlier sections,  had the restriction that no other edge could be added to G_t-1 at time t – meaning that, at time t^'≥ t,  was not allowed to add an edge of the form {i,j} with both i and j in G_t-1. We can say that graphs produced in this way have the property that G_t-1 is always an induced subgraph of G_t. In this section, we relax this restriction, meaning that , using memory, is now able to construct edges within G_t-1. We will refer to graphs constructed in this manner as being memory modifiable. 

To further illustrate this, let us consider the memory modifiable graph M_00010 constructed from the instructions (0→ 1)(1→∅). As  receives the first four bits from , an empty graph E_4 is constructed. This corresponds to M_t-1. As  has memory, the labels 0 or 1 of each of the four vertices can be distinguished.
Hence, when  receives the last instruction bit, which corresponds to joining vertex 0_5 to 1 vertices,  can instead choose to construct the edges (0_1,1_4),(0_2,1_4),(0_3,1_4), (0_5,1_4), as all vertices labeled 0 are indistinguishable without the above restriction.
The resultant graph M_t is a complete bipartite graph, K_1,4. We notice that if vertex 0_5 was removed, then the remaining induced subgraph is K_1,3. This is clearly not E_4. We can now give a definition of a memory modifiable graph: A memory modifiable graph, M_t, is a graph with the property that its induced subgraph constructed by the removal of vertex t is not isomorphic to M_t-1.
If  had chosen not to use memory to add edges in M_t-1, then we construct the equivalent graph listed in Proposition <ref>, which for (0→ 1)(1→∅) is the closely related E_(00010) (see Proposition <ref> and Figure <ref>).  We can conjecture that for each instruction there exists a memory modifiable graph. Given that the construction method is different the natural question to ask is the following: is the family of memory modifiable graphs the same as the graphs listed in Proposition <ref>? 






All possible memory modifiable graphs, M_t, are of the form: 


    K_l + E_m ,  K_l,m , K_l+m.

which are all graphs proven to be constructible in Proposition <ref>. 




Let us assume that  still has access to one bit of memory and instruction per vertex. Let us also remove the restriction that edges cannot be constructed in G_t-1. Then, from the ten unique instructions identified, only four can produce memory modifiable graphs. For those four, the new graph types are listed. We find that none of these graphs are unique, as they can all be constructed by the method used in Proposition <ref>. Below, we assume the following definition for a memory modifiable graph: A memory modifiable graph M_t is a graph such that its induced subgraph formed by the removal of vertex t is not isomorphic to M_t-1. We use this definition to determine whether an instruction can construct memory modifiable graphs. We also note that if a memory modifiable graph has not been formed for a particular instruction set at time  t, then the graph G_t must be of the form listed in Proposition <ref>.




  * (0→∅)(1→∅): Trivially, this instruction set cannot construct a memory modifiable graph as there are no edges. 


  * (0→ E)(1→ E):
This instruction always forms a complete graph, K_t, so cannot form memory modifiable graphs.
  

  * (0→ 0)(1→ 1): 
Consider G_t-1 on t-1 vertices. This is K_l⊎ K_m. Let us add vertex t. If vertex t is 0, then we produce    K_l+1⊎ K_m. If vertex t is 1, then we produce K_l⊎ K_m+1. Now, if vertex t was removed, in either case, we are left with K_l⊎ K_m. Clearly, G_t-1 is the same as the induced subgraph formed when vertex t is removed.
In fact, we can conclude the same about any set of instructions where the two groups of 0 and 1 vertices don't interact, because any graph formed from only one type of vertex, as shown in Proposition <ref> can only form K_l or E_l. Neither of these are memory modifiable, as shown above. 


  * (0→ E)(1→ 0):
Consider G_t-1 on t-1 vertices. This is K_l + E_m. We note that all possible (1→ 0) edges must exist for this graph type. Let us add vertex t. If vertex t is 0, then we add a dominating vertex. If vertex t is 1, then we connect all existing vertices labelled 1 to those labelled 0. However, we see that since all previous (1→ 0) edges have already been constructed, only vertex t forms connections. In both cases,  if vertex t was removed, then the remaining induced subgraph would be K_l + K_m. Hence, this instruction can never produce memory modifiable graphs. 


  * (0→ 0)(1→∅):
This set of instructions is non-interacting. Hence, we can see that this cannot form a memory modifiable graph. 


  * (0→ 1)(1→ 0):
Consider G_t-1 on t-1 vertices. This is K_l,m. Let us add vertex t. If vertex t is 0, then we construct K_l+1,m. If vertex t is 1, then we construct K_l,m+1.
In both cases, vertex t connects to all vertices of the opposite type. However, t doesn't modify the edges of any other pair of vertices, as these have already been connected with previous instructions. If vertex t was removed, in either case, we are left with the original K_l,m. The induced subgraph is the same as G_t-1, so this cannot form memory modifiable graphs.


  * (0→ 0)(1→ 0):
M_t = K_l + E_m, where l and m  are the number of 0's and 1's respectively. This is in fact a complete split graph consisting of an independent empty set E_l to which every vertex of clique K_m is completely connected. This is same graph produced by (0→ 1)(1→ E) as in Proposition <ref>.  


  * (0→ 1)(1→∅): 
M_t = K_l,m, where l and m  are the number of 0's and 1's respectively. This is same graph produced by (0→1)(1→0) as in Proposition 3.

  * (0→ E)(1→ 1): M_t = K_l+m, where l and m  are the number of 0's and 1's respectively. This is a complete graph and is also a threshold graph. This is same graph produced by (0→ E)(1→ E) as in Proposition <ref>.


  * (0→ E)(1→∅):
 M_t = K_l + E_m. This is a complete split graph, which is also threshold graph. This is same graph produced by(0→ 1)(1→ E) as in Proposition <ref>.  



Hence, any graph G_t whose subgraph G_t-1 is altered with the addition of vertex t is not unique, and does not add further to the number of graphs constructible by B. 





 


Recall that a graph is H-free if it does not contain a graph H as
an induced subgraph. Let us consider (0→ 1)( 1→∅). The sequence of instructions x_5=1_10_20_31_40_5 gives the graph G_5 on five vertices 1_1,0_2,0_3,1_4,0_5 and edges {1_1,0_2},{1_1,0_3},
{1_1,0_5}, and {1_4,0_5}. The edges {1_1,0_3},
{1_1,0_5}, and {1_4,0_5} form P_4. Hence, we can
construct P_4 in G_t, meaning that G_t is not P_4
-free. We can notice, by direct inspection on the graphs in Eq. (<ref>
), that every time we attempt to construct C_k, with k≥ 5, we are
forced to include a chord. A chord is an edge between two vertices of
a cycle that is not itself an edge of the cycle. Thus, G_t is C_k
-free for k≥ 5. Same situation for P_k, with k≥ 5. The case of 
P_5 is easy. Consider P_4 and try to add a vertex – and an extra
edge – for obtaining P_5. In taking x_5=1_10_20_31_40_5,
we can only add 0_6 or 1_6. If we add 0_6, we then create a 4
-cycle 1_10_51_40_6. The vertex 1_6 is isolated. There are 32
binary strings of length 5. The rule (0→ 1)( 1→∅) can not give P_5. The rules ( 0→∅) ( 1→∅) and (0→
1)(1→ 0) are clearly unsuitable for P_5. The same happens for 
(0→ E)( 1→∅), (0→
0)( 1→∅), since threshold graphs are known
to be P_4-free. Further, (0→ 0)( 1→ 1)
gives only disjoint cliques. With (0→ 0)(1→ 0), we
form a clique of 0s whenever we add 0 and so we can not go beyond P_3
, which is given by the sequence 0_11_21_3. We always form a new
triangle or a pendant vertex attached to a clique when adding 1 with the
rule (0→ E)(1→ 0). For (0→ E)(
1→ 1), cliques are unavoidable. Finally, K_l+m is P_4-free. This discussion leads to a corollary of Proposition <ref>:







Let  send to  one bit of instructions at each time step t. Let us assume that  has no randomness. Moreover, let us assume
that  remembers all instructions of , i.e., one
bit of memory for each vertex. Then, G_t is not necessarily P_4-free
or C_4-free, but it is P_n-free and C_n-free, for each n≥ 5.






§ ONE BIT OF INSTRUCTIONS AND ONE BIT OF MEMORY FOR EACH VERTEX
(FADING MEMORY)



In this section, we consider the graphs produced when B  has `fading' memory. That is, a memory which lasts for an integer  number of time steps. Previously, we considered the cases where  = 1 (no memory) and  = t (perfect memory). Now we consider the graphs formed when  is a small integer. With such a time step, it is impossible to construct a memory modifiable graph.
For the following analysis, we define a linear forest - the disjoint union of path graphs P_r_1, P_r_2,…,P_r_n, each of size r_i for 0<i<n - to be a graph of the form _i=1^nP_r_i.
Note that an isolated vertex is the path P_1, so a linear forest can contain isolated vertices.

We also define the graphs K'_(x) and E'_(x), with respect to the instruction bit string x, as in Section <ref>.
The graph K'_(x) is K_m + E_l minus edges of the form {t, t'} for t'< t-1 when x_t=1 and x_t'=0. 
The graph E'_x is K_(x) minus edges of the form {t, t'} for t'< t-1 when x_t=1 and x_t'=1.
Furthermore, we use the notation ⊕ to represent exclusive `or'.



Let A send to B one bit of instruction at each time step t. Furthermore, let  have memory which lasts  = 2 number of time steps. Then, the families of graphs produced will either be a threshold graph, a linear forest, or one of the following graphs: 
 

    E'_(x) , K'_(x) , K_t , E_t.

  


 B can distinguish only the labels of vertices t and t-1. B cannot distinguish vertices of G_t by picking them at random, since B has no randomness.
As before, m and l are the number of 0's and 1's respectively in the instruction string x.    
The interpretations of a one bit instruction from  are the same as in Proposition <ref>. Given these constraints, we proceed with a case by case analysis. 



  ( 0→∅) ( 1→∅):  G_t = E_t. 

  (0→ E)( 1→ E): 
 G_t = K_t

  (0→ E)( 1→∅):
 G_t = 𝒯, again, as this is the case of Proposition <ref>. 

  (0→0)( 1→∅):
G_t = _r ∈ R(x)  P_r for R: {0, 1}^* →ℕ^*.
The string R(x) is the ordered sequence counting consecutive zeros that appear in a bit string x, for instance R(00110100010) = (2,1,3,1).



  (0→0)( 1→1): 
G_t = _r ∈ R(x)  P_r⊎_s ∈ S(x)  P_s, for R: {0, 1}^* →ℕ^* and S: {0, 1}^* →ℕ^*.
The strings R(x) and S(x) are the ordered sequences counting consecutive zeros and ones respectively that appear in a bit string x, e.g. R(00110100010) = (2,1,3,1), S(00110100010) = (2,1,1). 



  (0→1)( 1→∅): 
G_t = ^r_i=1 P_2 ⊎ E_t-2r, where r is the number of occurrences of the substring (10) in the instruction string x. 


  (0→1)(1→0): 
G_t = _q ∈ Q(x) P_q ⊎ E_t - ∑_q∈ Q(x) q, for  
Q: {0, 1}^* →ℕ^*.
The string Q(x) is the ordered sequence of the lengths of substrings of alternating bits appearing in a bit string x, for instance Q(00110100010) = (2,4,3), counting bits (x_2x_3), (x_4x_5x_6x_7) and (x_9x_10x_11).


  (0→0)(1→0): 
G_t = _a∈ A(x) P_a⊎ E_t - ∑_a∈ A(x) a, for A: {0, 1}^* →ℕ^*.
The string A(x) is the ordered sequence of the lengths of substrings of the form (0 ⋯ 01) appearing in a bit string x, for instance Q(00110100010) = (3,2,4), counting bits (x_1x_2x_3), (x_5x_6) and (x_7x_8x_9x_10).


  (0→ E)(1→0):
G_t = K'_(x).
We see this as the edge {i,j} exists in G_t if and only if: ℓ(i) = 0, i > j, or ℓ(i) = 0, ℓ(j) = 1, i+1 <j, which precisely agrees with the definition of K'_(x).



  (0→ E)( 1→1): 
G_t = E'_(x).
We see this as the edge {i,j} exists in G_t if and only if: ℓ(i) = 0, i > j, or ℓ(i) = ℓ(j) = 1, i+1 = j, which precisely agrees with the definition of E'_(x).









§ RANDOMNESS ONLY


Randomness is an indispensable resource in communication and computational
complexity, and in general is a fundamental tool in many areas of computer
science, statistical mechanics, etc. How can we use randomness to
construct G? Start with the empty graph on n vertices and insert each
edge with probability 1/2.
The outcome of this random process is the (uniform) random graph and it is denoted by G_n,1/2 (see <cit.>).
The probability that G_n,1/2≅ H is nonzero, but exponentially small; in fact, 2^-n2 if we do not keep into account the size of the isomorphism class.
It follows however that without instructions we can still construct G_n,1/2.
The randomness used amounts to flip C(n,2) coins, which corresponds to an equal number of random bits. 
The time required for the process consists of a single time-step, since we can
flip all the coins at once.
So, bits here quantify both randomness and information. A quick observation: when the length of the instructions is zero, we can construct G_n,1/2 (with nonzero probability) by the use of C(n,2) bits assigned to the random process; conversely, without randomness, we need C(n,2) bits of information to construct G (with probability one).
An important fact is that the random process is instantaneous.
Randomness is generated by unbiased coins that can be re-used as many times we need. 
On the other hand, if we include time, each random bit can be given by flipping
the same coin – to be discussed further.

Notice that even if we do not use any instructions, we still need to be able
to identify the dyads of vertices when flipping the coins.
Suppose we have n=4. We have C(4,2)=6 dyads.
When we flip the coin at time t=1, we need to choose two vertices.
Without such a choice, we will not be able to add an edge.
More precisely, we need labels on the vertices so that we can remember whether we have already flipped a coin for a given dyad. Suppose we flip a
coin for (1,2) at time t=1.
At time t=2, we need to choose another dyad, say (1,3).
The dyad can be chosen only if we remember that we have
already dealt with (1,2).
There are two immediate options: either we have a list of vertex labels, which is then information; or the dyads need to be
chosen at random at each time step. In the latter case we definitely need
more randomness, in terms of more coin flips, but we still can construct the
graph. In fact nothing really happens if a dyad is chosen twice. What if we
are allowed more than a single time-step? Time is in principle
another plausible resource. We consider a topological version of time, where
each time-step is simply a positive integer, t∈ℤ^≥1. Time
opens the way to construct G not all at once, but via a sequence of
operations. With time available we can distribute instructions over a number
of different time steps. Hence the amount of information needed at each time
step could be dosed. This is the direction that we will take. Therefore we
choose to look at time not as a resource but as a parameter which is
unmodifiable by resources. The clock will tick whenever we perform an action (
e.g., adding a vertex).

If we use randomness, time could be subdivided into three operations:adding vertices; flipping coins, adding edges. Of course, G_n,1/2 can be
constructed by flipping C(n,2) coins at the same time, or by flipping a
single coin C(n,2) times. In the second case, if we allow a single coin as
a physical resource to generate randomness, the time for constructing the
graph is t=C(n,2). As might be expected it does not make much sense to
talk about random random graphs, where the pairs of vertices are chosen at
random. In this case, a dyad has probability 1/n^2 to be picked. If we
wait long enough then we just obtain the random graph.

At time t=1, we have a graph G_1, at time t=2, G_2, and finally G_n, at time t=n. Notice that not every time-step t needs to
correspond to a graph on t vertices. However, we may assume without loss
of generality that a graph G_t^' has a number of vertices k^'≥ k, whenever t^'>t and G_t is on k vertices.
In this notation G_n=G at the end of the growth process. For the
moment, let us consider a basic case: we start with G_1=K_1, i.e.
, the empty graph with a single vertex, and add a new vertex at each
time-step. Moreover, suppose that our only available resource is randomness.
As a consequence of this fact, at each time step t we add a single vertex
and choose its neighbours at random. We end up with the following process
introduced in <cit.> and originally studied in the context of graph
limits (see also <cit.>). For each t, let ν_t be a probability
distribution on {1,2,…,t}. By denoting as D_i a random variable
drawn according to the distribution ν_i, we obtain G_i by adding a new vertex to G_i-1 and connecting it to a subset of size D_i in V(G_i-1)
distributed with respect to ν_i. When ν_i= Bi(i-1,p), with p∈0,1] and i≥2, we get the Erdős–Rényi random graph.
By modifying ν_i, we can end up with various other graph ensembles.

The above process needs randomness and no information at all. How much
randomness? 


Let G_n be constructed only with the use of randomness and no
information. Then, the amount of randomness needed to construct G_n,1/2and G_n are asymptotically equivalent.



We quantify randomness by the number of random bits needed to perform each
choice. The table below lists these bits for the graphs G_3,G_4, and G_5. Notation: y_i^j is the j-th bit used for choosing
neighbours of vertex i in G_i-1 and x_i^j is the j-th bit used
for choosing their number, both at time i. For G_3,G_4, and G_5,
we need 4,8,14 bits, respectively:

    G_3:   ( x_1^1) (
    (x_3^1x_3^2)(y_3^1)) ;
    G_4:   (G_3)(
    (x_4^1x_4^2)(y_4^1y_4^2)) ;
    G_5:   (G_4)(
    (x_5^1x_5^2x_5^3)(y_5^1y_5^2y_5^3)) .

We have denoted by (G_i) the random bits for G_i. The formula for
this integer sequence is a(1)=0, a(2)=1,  and for n≥ 3, we have (proof below)

    a(n)=a(n-1)+b_o(n)+⌊log _2(n-1)⌋ +1,

for n odd and 

    a(n)=a(n-1)+b_e(n)+⌊log _2(n-1)⌋ +1,

for n even, where

    b_e(n)=⌊log _2( n-1n/2-1)
    ⌋ +1    and    b_o(n)=⌊log _2( n-1
    (n-1)/2-1) ⌋ +1.

The integer ⌊log _2(n)⌋ +1 is the number of
bits in the binary expansion of n. For Eqs. <ref> and <ref>,
let us consider the growth process. At time t=1, G_1=K_1. At time t=2, we add a vertex 2. There are 2 possible cases: we flip a coin and
get either d_G_2(2)=0 or d_G_2(2)=1. (Recall that the degree d_G(i) is the number of neighbours of a vertex i∈ V(G).) Hence, a(2)=1. At time time t=3, we add a vertex 3. There are 3 possible
cases: d_G_3(3)=0,…,d_G_3(3)=2. It is evident that the
contribution from this term at time t=n is then ⌊log
_2(n-1)⌋ +1 because d_G_n(n)=0,…,d_G_n(n)=n-1.
Vertex 3 can choose among 2 vertices, and in general vertex n can
choose among n-1 vertices. What is the d_G_n(n) with the highest
randomness cost? Let us label as 1,2…,n-1, the n-1 vertices in G_n
potentially adjacent to vertex n. The answer is d_G_n(n-1)=n/2 for n even and d_G_n(n-1)=(n-1)/2 for n odd. These are the numbers
giving the largest binomial coefficient. Since the binary system starts
enumerating from 0, we take the number of bits in C(n-1,n/2)-1 and C(n-1,(n-1)/2)-1. Summing up everything, a formula for n≥ 4 is

    a(n)    =   ∑_i=3; even^n-1⌊log _2( i-1
    i/2-1) ⌋ +∑_i=3; odd^n-1⌊log
    _2( i-1(i-1)/2-1) ⌋
          +∑_i=2^n⌊log _2(i-1)⌋ +2n-3.

Let us look at the asymptotic behaviour of a(n). First, i-1i/2
≤ 2^i-1 and i-1(i-1)/2≤ 2^i-1. Also, there is a
constant c>0 such that n!≤ cn^n+1/2e^-n when n→∞. By combining these facts, one can see that the asymptotic efficiency
class of a(n) is Θ (n^2).
Notably the same happens for C(n,2), which is the number of random bits needed for the uniform random graph, G_n, 1/2.





Let consider again the process above, but where the probability distribution
is taken to be uniform – see <cit.>. We iteratively construct a graph 
G_t=(V,E), starting from G_1=K_1. The t-th step of the iteration
is divided into three substeps: (1) We select a number k∈{0,1,…,t-1} with equal probability. Assume that we have selected k. 
(2) We select k vertices of G_t-1 with equal probability.
Assume that we have selected the vertices v_1,v_2,…,v_k∈
V(G_t-1). (3) We add a new vertex t to G_t-1 and the edges {v_1,t},{v_2,t},…,{v_k,t}∈ E(G_t). For a graph G on t
vertices, the likelihood of G, denoted by ℒ(G), is
defined as the probability that G_t=G, where G_t is the graph given
by the above iteration: ℒ(G):=Pr[G_t=G]. For example, ℒ(K_t)=1/t! and ℒ(K_1,t-1)=t/(t!)^2
∑_i=0^t-1i!, where K_1,n-1 is a star on n vertices. An
important point is a link between the likelihood and the size of the
automorphism group of G. An automorphism of a graph G=(V,E) is a
permutation p:V(G)⟶ V(G) such that {v_i,v_j}∈ E(G)
if and only if {p(v_i),p(v_j)}∈ E(G). The set of all automorphisms
of G, with the operation of composition of permutations “∘”, is a subgroup of the permutation group denoted by Aut(G). It
is in fact possible to show that 

    1/|Aut(G)|∏_i=1^ti-1⌊
    (i-1)/2⌋≤ℒ(G)≤1/|Aut(G)|.

It is plausible to conjecture that the minimum likelihood is attained by the
complete bipartite graph on n vertices, K_p-1,p, when n=2p-1, and K_p,p, when n=2p. Numerical evidence is exhibited in <cit.>. These
complete bipartite graph have a relatively large automorphism group and by
Mantel's theorem are the triangle-free graphs with the largest number of
edges. The analogue conjecture for the maximum seems harder to state. The
computational complexity of the likelihood is an open problem. The original
motivation for introducing the likelihood was to measure how likely is that
a given graph is generated at random. The idea fits the context of
quasi-randomness, i.e., the study of how much a given graph resembles
a random one.



§ TREES BUILT FROM LIMITED RESOURCES


We can consider also building trees using the framework developed thus far. 
A tree is a graph without cycles.
We grow trees by adding vertices one-by-one. Given a tree T_n on n vertices, we can always identify a
vertex 1, called the root, and added at time t=1. The k
-th generation of the tree are the vertices at distance k from the root.
The leaves are pendant vertices, i.e. vertices of degree 1.
The vertex n is always a leaf. Also the root, in our definition, can be a
leaf. When we grow a tree by adding vertices one-by-one then we also add
edges one-by-one. In fact, the number of edges of a tree T_n is exactly n-1.



 §.§ Trees built with random bits


The process in Section <ref> can be used to grow trees if at each
time step it is restricted to add a single edge. Equivalently, the degree of
vertex i in T_i is 1. It can be done by bypassing the random choice
of the degree. If we keep the random choice of the adjacent vertex, we have
a model of a random tree. At each time step i we add a new vertex and a new
edge incident with that vertex. The neighbour of the vertex is chosen
randomly in T_i-1. This process is also called the uniform attachment
model and T_i is usually denoted by UA(i) <cit.>. The graph UA(i) can be also obtained by taking one of all the possible spanning trees
of K_n at random; the well-known Prüfer bijection guarantees that K_n contains all trees on n vertices. The process gives a sequence of
random recursive trees, where a tree on the vertices {1,2,..,n} is 
recursive if the vertex labels along the unique path form 1 to j
increase for every j∈{2,3,…,n}.

For a rooted tree T, let L(T) denote the set of its leaf vertices.
We also denote by P_T(l) the (unique) path from the root vertex to the leaf l ∈ L(T). 
For graphs G and H we denote by G ∪ H the graph union of G and H.
This is the graph (V(G) ∪ V(H), E(G) ∪ E(H)).
Also, let b(n):= ⌊log_2 n ⌋ + 1, the number of bits needed to represent the integer n as a binary string.



    Let T be any tree on n vertices and let T_n = UA(n) be the random tree, as constructed previously.
    Then, ℒ(T) > 0 where ℒ is the likelihood function defined in Section <ref>, that is, ℒ(T) = Pr(T = T_n).


    We can describe the tree T as the graph union of the paths to each of its leaves, that is, T = ⋃_l ∈ L(T) P_T(l).
    Each path P_T(l) takes the form (1, i_1, i_2, …, l), so any individual given path can be generated according to our random process, as there is always nonzero probability for the edge {i,j} for j > i.
    
    We now need to prove that our random process supports constructing the union of all paths in T.
    Choose any two leaves in T, l_1, l_2 ∈ L(T).
    The induced paths from the root of T to l_1 and l_2 respectively are P_T(l_1) = (1, i_1, i_2, …, l_1) and P_T(l_2) = (1, j_1, j_2, …, l_2).
    From the previous paragraph, there is nonzero probability that P_T(l_1) and P_T(l_2) are individually subgraphs of T_n.
    For these paths to have zero probability of simultaneously being in T_n, there must be a vertex i_r = j_s for some r,s such that there are edges { i_r, i_r'}, { j_s, j_s'} for i_r < i_r', j_s < j_s' and i_r'≠ j_s'.
    This is because every vertex t ∈{1, 2, …, n} has only one neighbour smaller than itself t' < t.
    Suppose the condition holds.
    Then, the vertices { 1, i_1, …, i_r', …, i_r, j_1, … , j_s', …, j_s } induce a cycle.
    However, T is a tree, so has no induced cycle and we have a contradiction.
    This means P_T(l_1) ∪ P_T(l_2) is a subgraph of T_n with nonzero probability. 
    
    Since the argument holds for any l_1, l_2 ∈ L(T), we have that there is nonzero probability that T = ⋃_l ∈ L(T) P_T(l) is a subgraph of T_n.
    Indeed, since both T and T_n are trees on n vertices, they both have n-1 edges and so T⊆ T_n implies that T=T_n and the result follows.




 §.§ Trees built with instructions and memory


We can also consider the model earlier in the text, where Alice () sends instructions to Bob (), and  has memory.
We can bound the size of the instructions and memory needed to construct an arbitrary tree T.


Let T_n be a tree on n vertices. Then T_n can be constructed
with the use of O(nlog n) bits of instructions and O(nlog n) bits of memory.


    Consider constructing tree T_t given that we have the tree T_t-1.
    Since T_t has t-1 edges and T_t-1 has t edges, we only add one edge, between vertex t and some other vertex t' < t.
    The instructions have to specify which vertex t' will be t's neighbour.
    This requires b(t-1) bits.
    We also require a label in memory for each vertex t', each of which requires b(t') bits.
    Summing up, for the graph T_n, we require ∑^n-1_t=1b(t) bits of memory for the vertex labels and ∑^n-1_t=1b(t) bits for the instructions.
    Finally,
    
    ∑^n-1_t=1b(t)    =  ∑^n-1_t=1(⌊log_2 n ⌋ +1 ) ≤∑^n-1_t=1log_2 n  + n-1 = log_2((n-1)!) + n-1 
       ≤ (n-1)( log_2(n-1) - log_2(e) + 1 ) +O(log_2(n-1)) = O(n log n).
    






§ CONCLUSIONS


In this work we have considered a scenario where two parties Alice () and Bob () construct a graph together, given limited communication, memory and randomness.
We enumerate the different classes of graphs that  and  can construct under different constraints on these resources.

A number of open questions remain: for instance, in Section <ref> we saw that giving Bob one bit of memory per vertex lifted the class of threshold graphs to a larger class.
Indeed, it is well known that computational problems such as graph isomorphism and maximum clique are easy when the instances are taken as threshold graphs.
Perhaps for this extended class of graphs such problems are also easy.
Indeed, it would be interesting to construct a hierarchy of graphs with an increasing number of bits of memory and at which point these problems increase in difficulty.
Maybe there there is some correspondence with some well-known class of graphs.

The case for fading memory where 2 < 𝖫 < t needs to be investigated in a similar fashion as does the case of 𝖡 having access to differing numbers of random bits.

We may also ask the converse question: given a graph G, how many bits do 𝖠 and 𝖡 need to build it?
Recognising threshold graphs is linear-time <cit.>.
Is there a polynomial-time procedure for determining the number of bits of instructions and memory needed to construct G, beyond the Θ(n^2) bound? 



Acknowledgments. This paper follows a talk given by SS at the
“Doctoral Workshop on Mathematical and Engineering Methods
in Computer Science (MEMICS)”, Telč, Czech Republic,
October 23–25, 2015. SS would like to thank the organisers of MEMICS for
their kind invitation. SS would also like to thank Jan Bouda for being a
great host. 
This paper forms part of a Year 2 undergraduate project for AM.
We also would like to thank Nate Ackerman, Cameron Freer, Christopher Banerji, Josh Lockhart,
Octavio Zapata, and Vern Paulsen, for helpful discussion and their patience.

11
[ASW09]A S. Arora, D. Steurer, A. Wigderson, Towards a Study of
Low-Complexity Graphs, Automata, Languages and Programming, LNCS, 
5555, 119-131, 2009. Also available at 

[BMS14]BMS13 C. R. S. Banerji, T. Mansour and S. Severini, A notion of graph likelihood and an infinite monkey theorem, J. Phys. A: Math. Theor. 47 (2014) 035101

[B74]B N. Biggs, Algebraic graph theory, Cambridge University
Press, London, 1974, Cambridge Tracts in Mathematics, No. 67.

[CFMR13]C13 D. M. Cardoso, M. A. A. Freitas, E. A. Martins, M. Robbiano,
Spectra of graphs obtained by a generalization of the join graph operation, 
Discrete Math. 313 (2013): 733-741. 

[CH73]CH73 V. Chvátal, P.L. Hammer, Set–packing and threshold graphs Res. Report, Comp. Sci. Dept. Univ. of Waterloo, Waterloo, Ontario CORR 73-21 (1973)

[D12]D R. Diestel, Graph Theory, Springer (2012). 

[FG06]fl J. Flum, M. Grohe, Parameterized Complexity Theory,
Springer (2006).

[G80]G80 M. C. Golumbic, Algorithmic Graph Theory and Perfect
Graphs, New York: Academic Press, 1980.

[GV10]gr P. Grünwald and P. Vitányi, Shannon Information and
Kolmogorov Complexity, July 2010, 

[HIS78]HIS78 P.L. Hammer, T. Ibaraki, B. Simeone,
Degree sequences of threshold graphs, Proc. 9th South–Eastern Conf. on Combinatorics, Graph Theory and Computing. (1978) 

[JŁR00]J90 S. Janson, T. Łuczak and A. Ruciński, Random graphs (2000), John Wiley and Sons.

[JS13]JS13 S. Janson, S. Severini, An example of graph limit of growing
sequences of random graphs, J. Comb. 4 (2013), no. 1,
67–80. 

[L12]L12 L. Lovász, Large networks and graph limits, American Mathematical Society (2012) 

[PRS88]pu P. Pudlák, V. Rödl, and P. Savický, Graph
complexity, Acta Inform. 25 (1988), no. 5, 515–535.

[SM95]SM95 R. T. Smythe and H. M. Mahmoud, A survey of recursive trees, Theory Prob. Math. Statist., 51:1–27, (1995).

[W]W E. W. Weisstein, Graph Likelihood, from MathWorld–A Wolfram Web Resource, 



