1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I'm trying to come up with a good Ramsey Theory question (details)

  1. Jun 11, 2013 #1
    I have this really cool idea of asking Ramsey Theory questions on tilings (tessellations).

    Classical Ramsey theory asks what is the minimum number of people one needs to invite to a party in order to have that every person knows m mutual friends or n mutual strangers.

    I was thinking about coloring a tiling red and blue and asking similar questions, but I'm not sure what would be interesting. I have thought about this for a couple of weeks.

    Basically, Ramsey Theory is simply asking "how many elements of some structure must there be to guarantee that a particular property will hold?"

    I'm just not sure how to come up with an interesting question!
  2. jcsd
  3. Jun 11, 2013 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    What - like "what is the minimum number of colors of tile needed so you can cover a surface so that no two adjacent tiles share the same color?" But something that requires students to exploit tesselation ideas?

    OR: "How many trainee chefs in a kitchen before Ramsey is guaranteed to throw a wobbler?"
    ... ah... wrong Ramsey...
  4. Jun 12, 2013 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    The most elmentary questions are whether there is some way to represent graphs as tilings and vice-versa.

    It seems clear than any colored tiling could be represented as a colored graph by using an edge connection between two nodes to represent two tiles sharing a common side. That representation would not capture the property of two tiles only sharing a common vertex. Is there a graph that also represents that property?

    And given a colored graph, can it be represented as a tiling? I suppose that requires a rigorous definition of what a tiling is.
  5. Jun 12, 2013 #4
    The question I had, which didn't work, is this: Given positive integers m and n, does there exist a tiling such that for ANY two-coloring of the tiling, every tile has m friends OR n strangers. (In this case two tiles are friends if they are adjacent and share a color and strangers if they are adjacent and do not share a color)

    But it doesn't work because even starting with the extremely basic equilateral triangle tiling, and low numbers such as m = 2, and n = 3, we always find counterexamples.

    I'm pretty sure the answer to the first question is four via the four color map theorem, no?

    The answer to the second question I'm guessing is no because what if you had a colored, say K_6. I don't think it would be possible to have all 6 tiles adjacent to every other tile at once. I will think about it.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - trying Ramsey Theory Date
I Trying to get an explicit function(ish) Sunday at 5:39 PM
I Trying to understand the mistake in my logical reasoning Sep 19, 2016
Insights Comments - Friends, strangers, 7825 and computers Jun 21, 2016
Fun integrals to try Nov 10, 2015
Trying to invert an expression May 26, 2015