Wikipedia:Reference desk/Archives/Mathematics/2022 March 12

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

March 12

Domination on the chessboard - all free squares vs. all squares

The article section Mathematical_chess_problem#Domination_problems briefly mentions that domination is usually defined as the pieces on the board controlling all free squares, but can also be defined as controlling all squares including the occupied ones. Unfortunately today's "Did you know?" article Queen's graph does not mention that at all (I have added details in the meantime). In the book "Chess and Mathematics" of Evgeny Gik, of which I have the German translation and which has apparently not been published in English, he uses dominating only when also control the occupied squares. When they only control all free squares, this is called in the German translation e.g. "Wächter-Damen" ("guardian queens"). This term is not used in English. Are there English sources making a distinction, also in terms? --KnightMove (talk) 09:16, 12 March 2022 (UTC)

It's gone already. The statement in the hook was absolutely correct and did not refer to domination problems. The definitions of the mathematical notions "queen's graph" and "dominating set" being as they are, both of which are graph-theoretic notions that by themselves have no particular relation to puzzles, I see no omission in the article. IMO, paying attention to a variant definition of domination in puzzle contexts will give it undue weight in this article. Even in a puzzle context, the "eight queens puzzle" is universally supposed to be about chessboard arrangements on which the pieces are eight queens and only eight queens.  --Lambiam 14:32, 12 March 2022 (UTC)

Nobody denied that the hook was absolutely correct, but of course it referred to domination problems, as controlling all free squares is what domination on the chess board is about (and it matches the definition of graph theory). As the article Queen's graph demotes much of its content to classic chess puzzles, it cannot be wrong to write about them in related aspects. However, the eight queens puzzle is not part of my question.

The argument with "undue weight" may be valid if there are no English-speaking sources dealing with the alternate definition. --KnightMove (talk) 17:04, 13 March 2022 (UTC)

@KnightMove: According to our article Dominating set, specifically the section titled Variants, the English-language distinction is between a dominating set and a total dominating set of a graph. --JBL (talk) 01:35, 15 March 2022 (UTC)

Thank you very much - this expression is indeed also used in the Queen's context! --KnightMove (talk) 10:42, 15 March 2022 (UTC)

@KnightMove: I went in to the office yesterday, and here's what Doug West's book Introduction to Graph Theory (a standard comprehensive treatment) has to say (Section 3.1):

• The notion of domination was introduced by Claude Berge in his book The theory of graphs and its applications (Wiley, 1962) and the language was coined by O. Ore in Theory of graphs (American Math Society, 1962).
• There's a book by Haynes--Hedetniemi--Slater about domination and its variants (Fundamentals of domination in graphs, Marcel Dekker Inc., 1998).
• West's definitions agree with the (uncited) definitions in our article Dominating set, i.e., domination requires every square without a queen be defended, while total domination requires the queens themselves also be defended. He does not say anything further about total domination, beyond a definition.
• Exercise 3.1.56 specifically asks for the domination number (5) and independent domination number (7) of a standard chessboard by queens, but does not address the total domination number.

I hope this is helpful to you! -- JBL (talk) 12:14, 16 March 2022 (UTC)

Now I have taken the time to study it, and indeed, it is. Thank you very much! --KnightMove (talk) 14:06, 19 March 2022 (UTC)

Pronunciation of graph

Many, many years ago I was watching what I suppose was an Open University programme on BBC2 where the lecturer was talking about graph theory (by now it will be screaming out I am British!). He said the word is pronounced /ɡræf/ to distinguish it from /ɡrɑːf/ which he would use in the y against x sense. Was I dreaming? Or was he expressing a personal, idiosyncratic preference? I can't find anything online about this. Whatever, his system would fail in America anyway. Thincat (talk) 11:33, 12 March 2022 (UTC)

I've never heard anyone make such a meaning-dependent pronunciation distinction on either side of the pond. Also for graph-theoretic graphs, I hear British speakers make the word rhyme with half a laugh.  --Lambiam 14:46, 12 March 2022 (UTC)

I delayed a bit in case there were other replies, but no. So thank you for yours which seems to be pretty definite. Thincat (talk) 19:19, 14 March 2022 (UTC)

Here in Britain, the pronunciation is determined by latitude. catslash (talk) 22:48, 12 March 2022 (UTC)

Well yes. When as a child I went north to visit my granny in Manchester I sometimes heard her shrieking out of the window at next door's cat "Get off the /ɡræs/!" Thincat (talk) 15:49, 13 March 2022 (UTC)

rotating a m-sided polygon in an n-sided polygon. (same edge length) keeping among edges

Is there an easy way to determine the amount of area always covered as an m sided polygon rotates around the inside edges of a n sided polygon? As an example, I have a square of edge 1 rotating in a hexagon of edge 1 by starting with one edge of the square aligned with an edge of the hexagon and then rotating the square on its corner so that the next edge of the square is on the next edge of the hexagon and so on... It appears that if m is less than or equal to half of n (say rotating a triangle in a hexagon) that only the exact center is always covered, so it has measure 0. And the question doesn't really make sense of m=n.Naraht (talk) 15:31, 12 March 2022 (UTC)

Do you mean "regular polygon" or any old polygon, such as ?  --Lambiam 16:04, 12 March 2022 (UTC)

Regular. :)Naraht (talk) 21:55, 12 March 2022 (UTC)

The area of a regular $n$-gon with fixed side length increases strictly with $n$. So a regular $m$-gon only fits inside a regular $n$-gon if $m\leq n$, and for it to be able to rotate we need the strict inequality $m<n$.  --Lambiam 23:19, 14 March 2022 (UTC)

Apparently you want to minimize the area of the always-covered region, since it is possible to rotate the equilateral triangle inside the regular hexagon while keeping a non-degenerate central disk covered. I think the best is indeed to compose the full rotation from a sequence of partial rotations, each around a vertex of the inner polygon pegged to a vertex of the outer polygon. The sides of the rotating polygon then sweep out regions bounded by circular arcs. I doubt that there is an easy way to determine the area of the always-covered region. The considerations can be simplified by using the symmetries of the outer polygon, which can be divided into $2n$ congruent right triangles. Find the area of the region of one right triangle that can remain uncovered during a full rotation, and multiply by $2n$.  --Lambiam 11:38, 15 March 2022 (UTC)

Since the above-mentioned circular arcs are swept, then each point on the arc must be strictly outside the rolling m-gon some of the time, and so the arcs cannot be part of the boundary of the always-covered region. Is the always-covered region any different from the intersection of n m-gons (each sharing a side with the containing n-gon)? (clearly, that is false for odd m) catslash (talk) 23:16, 16 March 2022 (UTC)