3
votes
0answers
33 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
1
vote
0answers
44 views

ZigZag product - A simpler definition?

I have been fiddling with the ZigZag product and constructing expanders for a while now. I was wondering if the following definition of a ZigZag product is the same as the original article: Lets ...
0
votes
0answers
40 views

How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
4
votes
1answer
109 views

Category theory for graph theory research

I am doing research in algebraic graph theory, focusing on the relation between graphs and groups (especially the representing groups as graphs) for my Ph.D. In particular, one of the ideas is to ...
0
votes
2answers
122 views

Difference between Topological Data Analysis and Graph Technology

I'm trying to understand the difference between Oracle's graph technology which apparently has an inherent understanding of topology and Ayasdi's Topological Data Analysis technology. Are these two ...
1
vote
1answer
28 views

What sets of transpositions generate full $S_n$? Connected graphs?

I'm looking for an easy characterization of transpositions $\pi_1, \ldots, \pi_d \in S_d$ that generate $S_d$ or a transitive subgroup thereof (this should be equivalent). Examples include $(1 2), ...
0
votes
1answer
43 views

Does the Cayley digraph $C$= [(12)(34),(123):$A_4$] have a Hamiltonian Circuit?

This is a problem I'm working on for a friend of mine. I haven't been able to solve it, or make much progress. I have drawn the digraph, and it consists of four directed cycles of three vertices all ...
3
votes
2answers
36 views

All tree orders are lattice orders?

Say that a set is tree ordered if the downset $\downarrow a =\{b:b\leq a\}$ is linearly ordered for each $a$. In a comment, Keinstein says that such sets are also semi-lattices, provided they are ...
2
votes
0answers
28 views

Dhar's Burning Test - Confusion about Abelian Sandpile Model

Dhar's Burning test is a bijection between the spanning trees of a certain graph and the recurrent states Abelian sandpile model. I would like some help working out this bijection in different cases: ...
2
votes
0answers
47 views

About Network Dynamics

Consider the 6-node ring with only one bit active (000001). This is shown in the following figure as a hexagon with one circle filled. If the active bit is traveling in the counter clockwise ...
0
votes
1answer
136 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
31 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
26 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
52 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
76 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
61 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
51 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
133 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
64 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
351 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
546 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
202 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
174 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
348 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 ...
4
votes
1answer
253 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
83 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
201 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
104 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
121 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
117 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
302 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
186 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 ...
3
votes
2answers
86 views

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

My problem is 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$ for all $v\in ...
2
votes
0answers
54 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
101 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
209 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
47 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
716 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 ...