Wikipedia:Reference desk/Archives/Mathematics/2016 August 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 29

Counting Hamiltonian Circuits

How many Hamiltonian cycles exist for the Cartesian product of K₂ and K_n? Starting with n=2, I get values 1, 3 and 30; is there a formula? (Finding the value for n=4 is equivalent to the problem given here,) --RDBury (talk) 02:22, 29 August 2016 (UTC)

"Cartesian product" means the resulting graph has $2{\binom {n}{2}}+n$ edges, the disjoint union of two n-cliques and a perfect matching, right? If so, does the following work? For some $0<k\leq n/2$, choose in ${\binom {n}{2k}}$ ways the 2k edges of the perfect matching to use. Then choose in $(2k-1)!!$ ways a matching on 2k points, then choose in [some number of ways I haven't worked out] another matching on 2k points so that the union of the two matchings is a cycle, then distribute the $n-k$ other points in each half along the arcs of their matching [in some number of ways I also haven't worked out -- a Stirling number or something?]. --JBL (talk) 20:42, 30 August 2016 (UTC)

In other words simplify each cycle by merging the parts that stay within a singe clique into a single edge. Count the number of simple circuits then count the number of ways so 'recomplicated' them into full circuits. I think for the first part it would be better to skip the $(2k-1)!!$ ways of matchings on the 2k points and just count cycles on K_2k, well known to be $(2k-1)!/2$. Then remove the /2 because direction does make a difference here. So for n=4, k=2 you get 3! = 6 simple circuits which are also the full circuits. For n=4, k=1 you get (4 choose 2) x 1 = 6 simple circuits, and each of these can be re-complicated in 4 ways so there are 24 full circuits all together. That makes 6+24 = 30 which matches what I got earlier. For n=5, k=2 you get 30 simple circuits and 60 full circuits. For n=5, k=1 you get 10 simple circuits and 360 full circuits making 420 total. Not what I was getting so I'll have to work on finding where my mistake was. --RDBury (talk) 14:40, 31 August 2016 (UTC)

Stupid mistake on my part, for n=5, k=2 there are 4 full circuits for each simple circuit so 120 full circuits and 480 total circuits for n=5 and this does match what I got (at least for my last attmpt). There are no OEIS sequences that match this. So far we have

$\sum _{k=1}^{\left\lfloor {n \over 2}\right\rfloor }{\binom {n}{k}}(2k-1)!K_{n,k}^{2}$

where K_n,k is the number of possible 'complexifications' within a single clique. I'll work on finding more values of of K and see if it appears in OEIS. --RDBury (talk) 15:02, 31 August 2016 (UTC)

It appears that K_n,k is

$(n-2k)!{\binom {n-k-1}{k}}$

and the proof is actually fairly straightforward. So formula complete! --RDBury (talk) 15:52, 31 August 2016 (UTC)

(Edit conflict; too slow :).) Right, good, single cycles is much better. (Though your choice of notation $K_{n,k}$ maybe was not optimal ;).) I think $K_{n,k}=(n-2k)!\cdot \left(\!\!{\binom {n-2k+1}{k-1}}\!\!\right)=(n-2k)!\cdot {\binom {n-k-1}{k-1}}={\frac {(n-k-1)!}{(k-1)!}}$: given a complexified half of the simple cycle, choose an order on the arcs and an orientation for each arc and read the vertices not belonging to the matching in that order. This gives you a permutation of $n-2k$ points with markings to separate the permutation into k (possibly empty) segments, so $k-1$ markings. So (fixing a typo in your displayed equation) that would give in total

$\sum _{k=1}^{\left\lfloor {n \over 2}\right\rfloor }{\binom {n}{2k}}(2k-1)!\left({\frac {(n-k-1)!}{(k-1)!}}\right)^{2}$

This gives 0, 1, 3, 30, 480, 12000, 430920, 21052080, 1343381760, 108519626880 for n = 1..10. I haven't thought about whether or how much this simplifies. --JBL (talk) 16:15, 31 August 2016 (UTC)

Your proof of the value for K_n,k is more elegant that what I had in mind, and thanks for working out the additional values. I was about to correct the typo but you beat me to it. Actually I'm a bit surprised that the values can be expressed as a summation, so I'd be really surprised if the formula could be simplified more, but you never know with these things. Thanks for your help. --RDBury (talk) 16:35, 31 August 2016 (UTC)

The GF doesn't seem particularly nice, either (at least as far as 2 minutes poking around goes). My pleasure. I've added the sequence to the OEIS (it hasn't appeared yet). --JBL (talk) 19:03, 31 August 2016 (UTC)

Faithfully flat extensions

Let $R\hookrightarrow S$ be a faithfully flat extension, where R and S are commutative rings. Is the embedding of R into S necessarily an equalizer of the 2 maps $x\mapsto x\otimes 1$ and $x\mapsto 1\otimes x$ from S to $S\otimes _{R}S$ in the category of commutative rings? GeoffreyT2000 (talk) 03:22, 29 August 2016 (UTC)

Yes. This, in the category of R-modules (or the category of commutative algebras) is a beginning of Faithfully Flat Descent Theory. Just came across Descent Theory with an application to Infinite Dimensional Lie Algebras which may be more accessible than our articles and references. Proposition 2.11 on page 5 with N = R (they're smart enough to use the same letters for rings as you do :-) ) is what you want. Various books on (commutative) algebra or algebraic geometry should have it too.John Z (talk) 04:20, 18 September 2016 (UTC)

Matrices

Who invented them?--86.187.164.151 (talk) 23:38, 29 August 2016 (UTC)

See Matrix (mathematics)#History. StuRat (talk) 00:45, 30 August 2016 (UTC)