[math-fun] Fwd: "The" q-Fibonacci numbers
George Andrews privately replied A variety of problems arise in trying to work out q-analogs of various aspects of the Fibonacci numbers using Schur's q-Fibonacci numbers. A description of some of these is given in Fibonacci numbers and the Rogers-Ramanujan identities. Fibonacci Quarterly 42(1):3-19 (2004) George [...] This interesting paper, by somebody-or-other, can be found at http://www.fq.math.ca/Papers1/42-1/quartgranville01_2004.pdf --rwg
The Paley graph has vertices {0,1,...,p-1} where p is prime. Draw an edge between every pair (x,y), and color it red or blue depending on whether or not (x-y) is a quadratic residue, i.e. whether it has a square root. (If p=1 mod 4, then x-y is a residue if and only if y-x is, so the color is the same in both directions.) Some people believe that the largest monochromatic clique in the Paley graph has size O(log n) --- which, in terms of Ramsey graphs, makes it as good (within a constant) as a uniformly random coloring. How much numerical work has been done on this? What is the largest value of p that has been tried? - Cris
p.s. in particular, quoth Wikipedia: • The Paley graph of order 17 is the unique largest graph G such that neither G nor its complement contains a complete 4-vertex subgraph (Evans et al. 1981). It follows that the Ramsey number R(4, 4) = 18. • The Paley graph of order 101 is currently the largest known graph G such that neither G nor its complement contains a complete 6-vertex subgraph. Cris On Aug 6, 2013, at 5:17 PM, Cris Moore <moore@santafe.edu> wrote:
The Paley graph has vertices {0,1,...,p-1} where p is prime. Draw an edge between every pair (x,y), and color it red or blue depending on whether or not (x-y) is a quadratic residue, i.e. whether it has a square root. (If p=1 mod 4, then x-y is a residue if and only if y-x is, so the color is the same in both directions.)
Some people believe that the largest monochromatic clique in the Paley graph has size O(log n) --- which, in terms of Ramsey graphs, makes it as good (within a constant) as a uniformly random coloring.
How much numerical work has been done on this? What is the largest value of p that has been tried?
- Cris
hm. this page is helpful: http://mathoverflow.net/questions/48591/cliques-paley-graphs-and-quadratic-r... In particular, Graham and Ringrose showed that the smallest quadratic non-residue grows as least as log^2 p, in which case so does the size of the largest monochromatic clique. Cris
participants (2)
-
Bill Gosper -
Cris Moore