very hasty notes about math by ~pgadey rss
Hex Theory
2016-09-11

Hex Opening Theory

  • The Zermelo-von Neumann Theorem

  • The Nash-Hein Ramsey Theorem

  • The Topological Lemma (both cannot win)

  • Anatole Beck

    • Tree Games
    • Beck's Hex : Does every opening win?
    • ``This wrecks Beck's Hex'' : The opening the acute corner loses.
  • The Central Opening Conjecture (Hayward? Jack van Rijswijck? Berger?)

    • Question 1: On an odd sized board, does opening with the center win?
    • Question 2: Does each opening on the short diagonal win?

Hex and Topology

  • The Nash-Gale Theorem

    • Gale's O(n) algorithm for detecting who won a finished game
  • Ea Ea

    • Hex to Y
    • Y Reduction
    • Sperner's Lemma
    • K_5 Embedability?
  • Topological Dimension Theory

    • Covering dimension of the square

Hex and Probability

  • Oded Schramm

    • Random Turn Hex: At the start of each turn, toss a fair coin. The person who wins the coin plays the next move to the game.
    • Percolation probability

[2017-03-04] At long last, the first batch of percolation criticality numbers are in!

 # one hundred trials on a 7x7 board with coin-toss colouring
 :! python HexMonteCarlo.py 

 [[  1.   3.   4.   4.   5.   8.   5.]
  [  1.   0.   7.   7.  10.   7.   7.]
  [  4.   6.   4.  10.  10.  12.   7.]
  [  4.   6.   9.   9.   4.   8.   8.]
  [  3.  12.  12.  12.   8.   6.   2.]
  [  4.   9.   7.   7.   9.   5.   4.]
  [ 15.   6.   5.   5.   5.   0.   2.]]


  # ten thousand trials on a 7x7 board

  Simulating 7x7 with N=10000 trials
  [[  128.   232.   363.   478.   582.   704.  1065.]
   [  236.   500.   624.   846.  1001.  1077.   806.]
   [  358.   637.   899.  1076.  1120.   982.   554.]
   [  471.   817.  1114.  1165.  1064.   806.   466.]
   [  572.  1028.  1081.  1086.   908.   636.   350.]
   [  767.  1005.   990.   833.   605.   424.   250.]
   [ 1014.   751.   555.   448.   323.   226.   116.]]
  • Monte Carlo simulation

    • Three variants: Ramsey, Symmetric, and Hex

      • Ramsey:
      • Symmetric:
      • Hex:

    + Programming

  • Sample RP(x) for small boards. (How big is feasible?)

    • Implement Gale
    • Toss lots of coins
    • Tally the results
  • Examine the "gradient ascent" for RP(x)

    • Fix a gigantic board size (n = 10**6 + 1 to be odd?)
    • Pick a position x0 uniformly at random
    • Randomly sample RP(x0+eps) for all epsilon neighbours
    • Let x1 maximize RP(x-+eps)
    • Iterate.
    • Keep track of how long it takes x1 to get to xN (a fixed point?).

Conjecturing

   Suppose x and y are neighbours. 
      Q. Is it possible that P(x) = P(y)?
      Q. If x is a winning opening and P(x) < P(y) then is y also a winning opening? 

   Suppose x, y, and z are neighbours.
     Q. Do we always get a better "pair of neighbours"?

   Can P(x) gradient ascent have periodic points?

   What "should" the P(x) flow lines look like?

   If x_0 is a winning opening and x_n is its forward orbit under P(x)-ascent
     then do we get x_n is a winning opening?

   The Role of Central Symmetry P(x) = P(-x)
adding
2016-12-08

Adding

It is often handy to add numbers.

For example, 2+2=4.

String Figures
2016-06-11

[Plinthios Brokhos from String Figure Magazine 4 Vol. 6(2) June 2001]

String Figures:

  1. Storer Code talk [Translate the W.W. Ball lecture in to Storer!]
  2. Crossing analysis for Sandsnipe [String Figure Magazine Vol 2(1) March 1997] and Lightening [Jayne]
  3. Figure out how to flip the Laia Flower upside down (flower to mushroom cap)

Pictures:

[2016-05-16] I put together a small photo setup for taking shots of string figures. It is still a work in progress, but will be helpful in making a shots of figures. Eventually I'll put together an album of the figures that I know. The setup consists of putting my laptop on my desk chair, with a dark shirt over the back of the chair for a backdrop. The lamp points towards the black backdrop and lights up the figure. The lighting is a bit too strong and the photos come out overexposed.

Brokhos Brokhos via the pindiki extension

[2016-06-11] The figure below is a slight reworking of the Bolivian figure Footprint from SFM March 2002. The presentation of the Storer code together with the water colouring painting of the final figure is appealing. The colouring of the figure is supposed to mimic the effect of a tie dye string. One can trace through the crossings easily because of the colour

Randomizer:

[2016-08-03] Today I put up a page which displays selections from String Figure Magazine chosen uniformly at random. It is available here: http://pgadey.ca/string-figures/.

Books:

  1. Fun with String, Joseph Leeming
  2. String Figures, Jayne
  3. BISFA Vol 13, 2006
  4. BISFA Vol 9, 2002
  5. BISFA Vol 1, 1994
  6. Eskimo String Figures, Jenness
  7. Cat's Cradle, Owl's Eyes: A Book of String Games, Gryski
  8. Many Stars & More String Games, Gryski
  9. Super String Games, Gryski
  10. SFM, 2002
  11. SFM, 2001
  12. SFM, 2000
  13. SFM, 1999
  14. Abbot's Encyclopedia of Rope Tricks for Magicians, James, 1945
  15. The String Figures of Naura Island, Maude
  16. String Games for Beginners, Kathleen Haddon, 1942
Bongard Problems
2016-08-01-1 at 13h

"Given examples of x such that P(x) and examples such that not P(x), what is P?"

The puzzle above is the proto-type for all Bongard type puzzles. I'm a fancier of these kind of puzzles, because I think that they really get at an important skill that doesn't get practiced much: inductive thinking. One has to dream up a solution to the problems, there is no formal method for attacking them.

The original canon of Bongard's own Bongard problems and some additional problems, copied from the appendix in Harry Foundalis' thesis, are available without solutions here.

There is also an easy to print edition with six problems per page available: here.

For more information see:

  1. Wikipedia for historical information about Bongard problems.

  2. Linhares, A. (2000). A glimpse at the metaphysics of Bongard problems. Artificial Intelligence, Volume 121, Issue 1-2, pp. 251–270. Available here (mirror). This is a nice paper. It uses the concrete, printed on the page, sense of certain well chosen Bongard problems to talk about metaphysics. It reminds me of the good in Hofstader.

Low Complexity Art
2016-04-24

This is a working note about Jürgen Schmidhuber's notion of low-complexity art (wp).

Consider a piece of music, or a text, and call it X. Now -- Fix a programming language, and call it P. We say that the complexity of X relative to P is the length of the shortest program written in P that outputs X. We will call the length of that program K(X,P). This notion is called the Kolmogorov complexity of X measured relative to the programming language P.

It is interesting to note that the language P is irrelevant to definition of K(X,P). Suppose that you wanted work in some other language Q. Now you want to evaluate K(X,Q). Suppose it is possible to implement a Q compiler in P using at most N characters. Over all strings X we know that K(X,Q) is at most K(X,P) + N. Therefore, switching languages only costs a fixed amount of length. And so, we can really ingore the language we work in and think of K(X) in terms of one idealized language.

Kolmogorov complexity expresses a really fundamental idea about information. For example, K(X,P) is not computable. Proof?

Speed Prior (wp) is a nice alternative to K(X,P) since Speed Prior is computable.

Freudenthal Problems
2016-04-23-6 at 01h

"Given a message, what does it mean?"

See: Wikipedia or Three Compositions for Nash Camp

generated by bake