Graph Theory 47, 9–28 (2004)Īxenovich, M., Jiang, T.: Anti-Ramsey numbers for small complete bipartite graphs, Ars Combin. Generate all combinations of n - m fixed bit indicesĬonst fixedIndices = getCombinations(fixed, Object.keys(new Array(n).fill(true))) įor (let i = 0 i < fixedIndices.Axenovich, M., Jiang, T., Kündgen, A.: Bipartite anti-Ramsey numbers of cycles and path covers in bipartite graphs.
Number of edges in hypercube free#
An m-face has m free bits and n - m fixed bits Returns a list of m-faces of an n-dimensional hypercube Utility function that gets all n-length combinations of elements in arrĬonst getCombinations = (n, arr) => (arr.length = n) ? : (n = 0) ? ] :. Instead of producing an array of vertices, it produces an array of indexes i that represent the ith vertex: generateEdges(n) ` I was able to deduce the following recursive algorithm using the patterns I noticed (where m = 1 is the dimension of the face and n is the dimension of the hypercube). The numbers in the black squares represent the index of the vertex in v. Here, v represents the ordered array of vertices, a represents the output m-face array, each column represents an m-face, and the colored outlines show the relationships to the m-face list in lower dimensions (the recursive relationship to lower dimensions). I rearranged my spreadsheet and made sheets for n = 1.4 and m = 1.3: m = 1 for dimensions 1 - 4 This makes sense since n-hypercube geometries build off of n-1-hypercube geometries. Then I noticed that the edge list of dimension n builds off of the edge list of dimension n-1 recursively. There are n different sized gaps between vertex indexes.To visualize this relationship between n and m, I threw ordered vertices in a spreadsheet and colored in cells to represent m-faces. Using this pattern, I should be able to come up with a new algorithm that didn't depend on building combinations.
I figured that, because the array of vertices provided was always ordered, there must be some pattern that forms as n and/or m increase. Once I started building m-face lists for dimensions 9 and above the algorithm would take 30 seconds, 1 minute, 5 minutes, etc. The number of combinations that need to be checked get exponentially larger as the dimension n of the hypercube increases. The problem with this algorithm is that it's extremely inefficient. This would continue until all combinations had been checked. If it did, and the hamming distance was exactly m, it would be added to the m-face list. If the hamming distance was > m, the combination would be ignored, otherwise we would continue building the combination until it contained 2^m vertices. Each time a vertex was added to the combination, the hamming distance would be checked between all vertices in the combination. My algorithm produced lists of m-faces by recursively building combinations of vertices. ,, , and form a face (2-face) because they differ by 2 bits (i.e. If a combination of 2^m vertices differ by exactly m bits, then they form an m-face.įor example, and form an edge (1-face) because they differ by 1 bit. One solution (which I currently have working) is to use the hamming distance between vertices' binary representations to determine whether or not they are part of an m-face. an n-face is represented by a length 2^n array of vertices. Same goes for cels and any other n-face, i.e. Note that a face is not an array of edge arrays, instead an array of the vertices that represent the face. , ]), we would have: > getMFaces(1, 3, vertices)Įdges in a 2-dimensional hypercube (a face) would give: > getMFaces(1, 2, vertices)įaces (2-faces) in a cube would give: > getMFaces(2, 3, vertices) If we assume vertices is an ordered array of binary representations of vertices in a cube (i.e. Say we wanted to get an array of edges (1-faces) in a cube (3-dimensional hypercube). That may have been a confusing way to word it, so here are a few examples: I'm attempting to design an algorithm that, given n, m, and vertices (where n = the dimension of a hypercube, m = the dimension of the faces we're trying to generate, and vertices is an ordered list of vertices in an n-dimensional hypercube), returns an array of arrays of vertices representing m-faces in an n-dimensional hypercube.
0 kommentar(er)
