# Tagged Questions

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 ...
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 ...
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 ...
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 ...
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 ...
28 views

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 ...
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 ...
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 ...
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. ...
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, ...
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 ...
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) ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
117 views

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 ...
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$. ...
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 ...
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 ...
### 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 ...