Search algorithm for Ramsey graphs by union of group orbits

Show simple item record

dc.contributor.author Radziszowski, Stanislaw
dc.contributor.author Kreher, Donald
dc.date.accessioned 2009-06-10T18:57:15Z
dc.date.available 2009-06-10T18:57:15Z
dc.date.issued 1988
dc.identifier.citation Journal of Graph Theory. vol. 12, no.1, 1988
dc.identifier.uri http://hdl.handle.net/1850/9813
dc.description Originally published in The Journal of Graph Theory by John Wiley and Sons, Ltd. en_US
dc.description RIT community members may access full-text via RIT Libraries licensed databases: http://library.rit.edu/databases/
dc.description.abstract An algorithm for the construction of Ramsey graphs with a given automorphism group G is presented. To find a graph on n vertices with no clique of k vertices. Kk • and no independent set of I vertices. 7</. k. I::; n. with an automorphism group G. a Boolean formula Q' based on the G-orbits of k-subsets and I-subsets of vertices is constructed from incidence matrices belonging to G. This Boolean formula is satisfiable if and only if the desired graph exists. and each satisfying assignment to Q' specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of Q' from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP-hard. we present an "efficient" method to do the conversion for the formulas that appear in this particular problem. When G is taken to be the dihedral group On for n ≤ 101. this method matches all of the previously known cyclic Ramsey graphs. as reported by F. R. K. Chung and C. M. Grinstead ["A Survey of Bounds for Classical Ramsey Numbers." Journal of Graph Theory. 7 (1983). 25-38]. in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established: R(4. 7) ≥ 47. R(4. 8) ≥ 52. R(4. 9) ≥ 69. R(5. 7) ≥ 76. and R(5. 8) ≥ 94. Also. some previously known cyclic graphs are shown to be unique up to isomorphism. *Please refer to full-text for correct equations and numerical values
dc.language.iso en_US
dc.publisher John Wiley & Sons
dc.relation.ispartofseries vol. 12
dc.relation.ispartofseries no. 1
dc.title Search algorithm for Ramsey graphs by union of group orbits
dc.type Article

Files in this item

Files Size Format View
JohnWileySonsArchivePolicy.pdf 95.61Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse