Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn inequivalent factorizations of a cycle
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We introduce a bijection between inequivalent minimal factorizations of the n-cycle (1 2 ... n) into a product of smaller cycles of given length, on one side, and trees of a certain structure on the other. We use this bijection to count the factorizations with a given number of different commuting factors that can appear in the first and in the last positions, a problem which has found applications in physics. We also provide a necessary and sufficient condition for a set of cycles to be arrangeable into a product evaluating to (1 2 ... n).
rate research
Read More
Write $mathcal{C}(G)$ for the cycle space of a graph $G$, $mathcal{C}_kappa(G)$ for the subspace of $mathcal{C}(G)$ spanned by the copies of the $kappa$-cycle $C_kappa$ in $G$, $mathcal{T}_kappa$ for the class of graphs satisfying $mathcal{C}_kappa(G)=mathcal{C}(G)$, and $mathcal{Q}_kappa$ for the class of graphs each of whose edges lies in a $C_kappa$. We prove that for every odd $kappa geq 3$ and $G=G_{n,p}$, [max_p , Pr(G in mathcal{Q}_kappa setminus mathcal{T}_kappa) rightarrow 0;] so the $C_kappa$s of a random graph span its cycle space as soon as they cover its edges. For $kappa=3$ this was shown by DeMarco, Hamm and Kahn (2013).
Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, universal summation) that can be critical tasks when complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.
In this note we show that the maximum number of edges in a $3$-uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))frac{n^{3/2}}{sqrt{10}}$. This improves earlier estimates by GyH{o}ri and Lemons and by Furedi and Ozkahya.
We give two combinatorial proofs of Goulden and Jacksons formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type $B$.
We use the Chicken McNugget monoid to demonstrate various factorization properties related to relations and chains of factorizations. We study in depth the catenary and tame degrees of this monoid.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
