0
votes
0answers
60 views

Proving The Diamond Lemma

We have the diamond lemma as follows: Let $\rightarrow$ be relation on a set $P$. Let $\twoheadrightarrow$ be the reflexive transitive closure of $\rightarrow$ and $\sim$ the equivalence relation ...
0
votes
0answers
29 views

Graph algebra papers

The following graph multiplication appears to be quite natural: Let $g_1=(V_1,E_1)$ and $g_2=(V_2,E_2)$ be two graphs ($V_i$ are sets of vertexes and $E_i$, sets of edges). Intuitively, the product I ...
3
votes
1answer
58 views

Proof Technique: Linear Independence - What makes the technique work in general?

Reading the book on Graph theory written by Bondy and Murty (Springer), they present the following proof technique (Linear Indepence) to use when the combinatorial approach fail. My questions are: ...
0
votes
1answer
24 views

Determining Commutativity from a Digraph?

I'm trying to sort out when a group is commutative, given its digraph. We have vertices of the digraph for each element in the group and different arcs connecting the vertices for each generator of ...
0
votes
1answer
43 views

Subgroup lattice

I've been searching around for a while now and can't seem to find a clear explanation of what a subgroup lattice of a group actually is. I see the vertex set is given by the subgroups of the group, ...
2
votes
2answers
72 views

Number of functions with some property

A function $f$ is defined on the set $\{0,1,2,3,…,n-1\}$ to itself. This is a function such that if you take any $k$ from the set $\{0,1,2,3,…,n-1\}$ then $f^m (k)=0$ for some natural number $m$. ...
0
votes
1answer
55 views

Cycle type of induced permutation

Let $m = \binom{n}{2}$ and $S_n, S_m$ be the symmetric groups, $S_n \subset S_m$. Let $\pi \in S_n$ and let $\pi$ have the the cycle type $[λ_1,λ_2,\dots,λ_k]$, $\lambda_1+\lambda_2+ ...
0
votes
2answers
48 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
1
vote
5answers
116 views

When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...
0
votes
1answer
61 views

graphs and groups

In many papers we see a group which is constructed a graph from it and captures some information about the group. There are several ways of doing this, non-commuting graph, power graph, cayley ...
0
votes
0answers
27 views

Isomorphism of complete DAG corresponding to group action on group ordering.

Label the complete directed acyclic graph nodes with elements of a group of size $|V|$ where $V$ is the set of vertices. This graph represents a total ordering $\lt$ of the group minus antisymmetry. ...
13
votes
3answers
340 views

Metal Ball Cage Template Cardinality: A Brilliantly Lazy PROOF

N.B. - I'm looking for the simplest way to ascertain the number of templates $T$ (see below) comprising the structure from just one angle alone; that is, I'm sitting down looking up at this thing, ...
1
vote
2answers
503 views

Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question: How many antisymmetric relations are there on an $n$-element set? Guess: I suspect that there are $2^n$ such relations. Discussion: I'm told that anti-symmetric relations on a ...
4
votes
1answer
168 views

A doubt in the proof of Frucht's theorem

I am trying to understand the proof of Frucht's theorem which is: Every finite group is isomorphic to the automorphism group of some simple graph. The proof (which I am reading from this book) ...
0
votes
1answer
162 views

Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group. So for the mapping from the group to the graph, I ...
14
votes
1answer
345 views

What are all conditions on a finite sequence $x_1,x_2,…,x_m$ such that it is the sequence of orders of elements of a group?

My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers, is said to be generated by the finite group $G$ iff $n:=|G|=x_1+x_2+...+x_m$. $n$ has $m$ divisors. if ...
3
votes
1answer
227 views

Intuitive interpretation of the adjacency matrix as a linear operator.

Naturally we can describe graphs via tables of "yes there is an edge" or "no there is not" between each pair of vertices, so the definition of an adjacency matrix is easily understood. Thinking of ...
1
vote
1answer
82 views

Is an abstract simplicial complex a quiver?

Let $\Delta$ be an abstract simplicial complex. Then for $B\in \Delta$ and $A\subseteq B$ we have that $A\in\Delta$. If we define $V$ to be the set of faces of $\Delta$, construct a directed edge from ...
4
votes
1answer
197 views

Graphs with a unique $3$-path free acyclic orientation up to isomorphism.

Let $\Gamma$ be a simple, $3$-colorable graph such that, up to isomorphism, there exists exactly one acyclic orientation of $\Gamma$ that does not contain a directed 3-path. (To be clear, when I say ...
2
votes
1answer
103 views

Lattices of Subgroups and Graph

In Dummit and Foote´s Abstract Algebra, when talking about the lattice of subgroups of $A_4$, the authors make the statement that, unlike virtaully all groups, $A_4$ has a planar lattice? My question ...
3
votes
1answer
119 views

Ends of a Group

I have these two questions that I cannot get any intuition about. Perhaps someone can possibly offer a few hints on how to get started? 1) Show that the ends of ${\bf F_2} \oplus {\bf F_2}$ is equal ...
3
votes
1answer
111 views

Behaviour of the Cayley graph of a group when changing the generating set / Number of ends of a group

Introduction of terminology: Let $G$ be an infinite group and let $S$ be a finite generating subset of $G$ that is symmetric, i.e. $x\in S$ implies $x^{-1}\in S$. Then the relation $g\sim ...
4
votes
1answer
271 views

Orbits of adjacency matrices under conjugation by permutation matrices.

(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.) I am interested in if anyone knows of ways of characterizing the orbits of an adjacency ...
0
votes
2answers
170 views

Infinite rooted binary tree

Let $T$ be a rooted infinite binary tree and let $\text{Sym}(T)$ be the group of all symmetries of $T$. Show that any $\alpha \in \text{Sym}(T)$ sends the root to the root, even if you just view ...
1
vote
2answers
83 views

Properties of an element $x\in X$ in the Cayley-Graph $\Gamma(G,X)$ of a group G.

My problem ist the following: Let G be a group with generating set X. We can look the Cayley-Graph $\Gamma(G,X)$ of G. Let $x\in G$. Then it holds: $d_{\Gamma}(v,xv)\leq 1$ f.a. $v\in G=\Gamma(G,X)$ ...
2
votes
0answers
52 views

Dehn Twist in the sense of graphs

Does anyone knows a good book or script about Dehn Twists in the sense of graphs. More precisely: I need to know how a Dehn Twist yields an automorphism of a group or subgroups. I want to know ...
4
votes
1answer
98 views

Why does every finite subgroup of $\mathrm{Aut}(F_n)$ acts on a graph of Euler characteristic $n-1$?

My question is the following: In a paper I read that: Any finite subgroup of $\mathrm{Aut}(F_n)$ can be realised as agroup of baspoint-preserving isometries of a graph of Euler characteristic $1-n$. ...
2
votes
2answers
202 views

Given any polynomial p(x) over Z, can one construct a graph with characteristic polynomial p(x)?

Given any polynomial $p(x)$ over $\mathbb{Z}$, can one construct a graph with characteristic polynomial $p(x)$? [Edit: Title question added to post.} Further questions include: Are there classes of ...
1
vote
1answer
45 views

Understanding special weightings for a digraph / noncommutative polynomial ring

A digraph is defined as $G=(V,E,\phi)$ with a set of nodes $V$ a set of edges $E$ a mapping $\phi : E \rightarrow V \times V$ A weighting $\mathcal{W}$ for a directed graph $G=(V,E,\phi)$ is a ...
2
votes
1answer
648 views

Why is the Fundamental Group of a Connected Graph $G$ Free on elements in $G-T$; $T$ spanning tree for $G$)

The fundamental group $\Pi_1(G)$ of a connected graph $G$ is defined to consist of all loops (i.e., closed paths) based at a given fixed basepoint/vertex $g \in G$ as elements, and concatenation ...