how to generate {8,3} regular graphs for large number of vertices

hyperbolic lattices

Answer 1

[Simar]

Hi Zahid,

I understand that you are seeking assistance in generating the adjacency matrix representation for a regular graph that corresponds to a {8,3} tiling, for large number of vertices.

The {8,3} tiling is a hyperbolic tiling where each vertex is surrounded by three octagons. As mentioned, this tiling can be represented in the Poincaré disk model. The challenge is to convert this geometric representation into a graph's adjacency matrix. Given the complexity of directly translating tiling into an adjacency matrix for large n, a practical approach involves understanding the tiling's properties and generating the graph programmatically.

Here is a conceptual guide and MATLAB code to help start with this process, focusing on the adjacency matrix generation.

• Vertex Identification: Assign a unique identifier to each vertex in the tiling. In the {8,3} tiling, vertices can be identified based on their position in the tiling pattern.
• Adjacency Rules: Determine the rules of adjacency based on the tiling. In the {8,3} tiling, each vertex is connected to three other vertices. The challenge is to systematically identify these connections based on the tiling's geometry.
• Adjacency Matrix Generation: Once have a systematic way to identify vertices and their adjacencies, generate the adjacency matrix.

This code does not directly generate the {8,3} tiling but provides a framework to generate the adjacency matrix once a method for identifying vertices and their adjacencies is in place.

% Assuming you have a way to identify vertices and their adjacencies 
n = 10000; % Number of vertices 
A = sparse(n, n); % Initialize a sparse adjacency matrix for efficiency 

% Hypothetical function to get adjacency list for a vertex 
% Define this based on tiling generation 
% function adjVertices = getAdjacentVertices(vertexId) 
%     adjVertices = [...]; % Return IDs of adjacent vertices 
% end 

% Populate the adjacency matrix 
% This is a conceptual loop. Replace it with your logic 
% Based on how you are generating or traversing the {8,3} tiling. 
for vertexId = 1:n 
    adjVertices = getAdjacentVertices(vertexId); % Need to implement this 
    for adjVertex = adjVertices 
        A(vertexId, adjVertex) = 1; % Mark the adjacency 
        A(adjVertex, vertexId) = 1; % For undirected graph 
    end 
end 

The critical part is implementing the “getAdjacentVertices” function to systematically determine the adjacencies in the {8,3} tiling. This requires a deep understanding of the tiling's geometry and a way to navigate or iterate through the tiling pattern programmatically.

Due to the complexity and specificity of the {8,3} tiling in hyperbolic geometry, there is not a universal solution that can be provided without a more detailed exploration of the tiling's properties and its representation in the code.

Please refer to the following documentation links-

• Sparse-https://www.mathworks.com/help/matlab/ref/sparse.html?searchHighlight=sparse&s_tid=srchtitle_support_results_1_sparse
• Graph-https://www.mathworks.com/help/matlab/ref/graph.html?searchHighlight=graph&s_tid=srchtitle_support_results_1_graph
• Graph & Network- https://www.mathworks.com/help/matlab/graph-and-network-algorithms.html

Hope it helps!

Best Regards,

Simar