Intereting Posts

little-o and its properties
What is the standardized way to represent $\pi$ in binary notation?
Calculating a real integral using complex integration
Why does the discriminant of a cubic polynomial being less than $0$ indicate complex roots?
Find the derivative of the inverse of this real function $f(x) = 2x + \cos(x)$
operations on probability distributions
Find the value of $a^2-b^2+c^2$
Is there a “geometric” interpretation of inert primes?
Minimal polynomial and diagonalizable matrix
Subring of a finitely generated Noetherian ring need not be Noetherian?
Calculating derivative by definition vs not by definition
Principal ideals having embedded components
Order-preserving injections of ordinals into $$
If xy + yz + zx = 1, …
Resource for Vieta root jumping

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$.

DefinitionA left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on $\Gamma$ such that, at each vertex, the path turns left in the orientation $\mathcal O$.

I want to calculate the number of left-hand turn paths of $\Gamma$ without drawing them. I found the following:

When you look at a vertex with the given (planar) edge-coloring i.e. orientation, there are two situations that can happen:

- How to find chromatic number of the hypercube $Q_n$?
- Monochromatic Rectangle of a 2-Colored 8 by 8 Lattice Grid
- Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?
- Coloring Graph Problem
- Is the Odd-4 graph a unit-distance graph without vertex overlap?
- Edge-coloring of bipartite graphs

$\hskip1.7in$

Lets start with the left figure: When you come from the color-1 edge and you want to go left you end at the color-2 edge. Coming from 2 you end at 3, and from 3 to 1.

Fine in the right figure the orientation is inverted, so left is right here. So if we come from the color-1 edge we end at (surprise,surprise) the color-2 edge.

And so forth…

So after 1 follows 2 after that 3 and then 1 again, no matter if we reach a left- or right-oriented vertex.

Now, the adajency matrix of the graph $A_\Gamma$ splits up into three different color submatrices, with $A_\Gamma=A_1+A_2+A_3$. $A_k$ are permutation matrices with $A_k^2=1$.

So the number of left-hand turn path can be calculated when you look at the number of unique solutions of

$$(A_3A_2A_1) v_kv_{k+1} =v_kv_{k+1},$$

where $v_k$ can be any vertex as starting point and $v_kv_{k+1}$ indicates the starting edge.

Vertices are allowed multiple times. Edges may be traversed in the opposite directions as well…

Is this correct and if so are there other ways to do it?

- Graph with 10 nodes and 26 edges must have at least 5 triangles
- A binary sequence graph
- Finding the spanning subgraphs of a complete bipartite graph
- Adjacency matrix and connectivity proof
- counting triangles in a graph or its complement
- Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$
- Understanding the properties and use of the Laplacian matrix (and its norm)
- For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?
- Graph theory and tree company
- Havel & Hakimi degree sequence theory

Solving your equation $(A_1A_2A_3)^t v_kv_{k+1} =v_kv_{k+1}$ will count each cycle multiple times, even if you only consider the minimal positive $t$ that works, since each cycle will be counted once for every $3\rightarrow 1$ transition it contains (and it must contain an even number of them, since the graph is bipartite).

Since the $A_k$ are permutation matrices, the matrix $M=A_1A_2A_3$ is itself a permutation matrix, and what you want is exactly the number of cycles in this permutation $\pi_M$.

Since the graph is bipartite, every cycle of $\pi_M$ will be of even length, corresponding to a unique “left hand turn” cycle in $\Gamma$ that is three times longer.

Clearly each cycle in $\pi_M$ corresponds to a unique “left hand turn” cycle in the graph, and vice versa.

You might be worried that $\pi_M$ could have cycles where we return to a vertex but we are traveling in the opposite direction and so it is not really a cycle. But this cannot happen, since every vertex in a cycle of $\pi_M$ is always being traversed in the $3\rightarrow 1$ direction.

If we return to a vertex, we are passing through it in exactly the same way.

- What is the field of fractions of $\mathbb{Q}/(x^2+y^2)$?
- closure of finite unions
- Why was set theory inadequate as a foundation to the emerging new fields and why category theory isn't?
- A necessary condition for a multi-complex-variable holomorphic function.
- Homomorphism and normal subgroups
- Derivative of $a^x$ from first principles
- Prove $\lim _{ n\to\infty } \sqrt { \sum _{ i=0 }^{ k } a_i ^n } =\max { \{{ a }_{ 1 }, \ldots ,{ a }_{ k }\} } $
- Algebraic field extensions: Why $k(\alpha)=k$.
- How to show that $\phi_a(z)=\frac{z-a}{1-\bar{a}z}$ is mapping $\phi_a(z):\mathbb{D} \rightarrow \mathbb{D}$?
- Is the metric induced by convergence in probability (Ky Fan metric) complete?
- the ideal generated by general polynomials is radical
- Is the intersection of a closed set and a compact set always compact?
- Calculate: $ \lim_{x \to 0 } = x \cdot \sin(\frac{1}{x}) $
- Real function with complex antiderivative $\frac{\sqrt{x+\sqrt{x^2+1}}}{\sqrt{x}\sqrt{x^2+1}}$?
- What are some martingales for asymmetric random walks?