June 22 & 25: F. Harary & W. Slany: Combinatorial games and Ramsey theory


Subject: June 22 & 25: F. Harary & W. Slany: Combinatorial games and Ramsey theory
From: Wolfgang Slany (wsi@dbai.tuwien.ac.at)
Date: Wed Jun 16 1999 - 12:47:53 MET DST


Announcement of three lectures on combinatorial games and Ramsey theory
-----------------------------------------------------------------------

Frank Harary
------------------
Computer Science Department, New Mexico State University

Achievement and avoidance games on geometries, graphs, grids, groups and numbers
================================================================================
Tuesday, June 22, 1999, 17h c.t.

Freihaus Hoersaal 6: A-1040 Wien, Technische Universitaet Wien, Wiedner
Hauptstrasse 8-10, Freihaus, Turm A, 2. Stock, gruener Bereich.

Abstract

Thus far, the games which I have been discovering deal with geometries,
graphs, groups, games played on grids [where they generalize tic-tac-toe
in many directions], numbers, and chess pieces. There are unsolved
problems galore, both for `pure' mathematicians and for computer
scientists. Some of the graph games have catchy names like: Kingmaker,
Blockbuster, Pathfinder, Trailblazer. The number games can be useful in
teaching children arithmetic in a rather enjoyable way. I will be
delighted when these games are programmed for a person to play against a
computer. At least one game of each type will be played.

These games have relevance to pedagogy as children of all ages enjoy
playing them and thus enjoy while learning the mathematical operations
needed to play them. They represent research challenges to both
mathematicians and computer scientists as only a few of their strategies
have been developed.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Wolfgang Slany
---------------------
Institut fuer Informationssysteme, Technische Universitaet Wien

The complexity of graph Ramsey achievement and avoidance games
==============================================================
Tuesday, June 22, 1999, after Prof. Harary's lecture.

Freihaus Hoersaal 6: A-1040 Wien, Technische Universitaet Wien, Wiedner
Hauptstrasse 8-10, Freihaus, Turm A, 2. Stock, gruener Bereich.

Abstract

Given two graphs G and A, two players, Red and Green, alternate in
coloring the edges of G in their respective colors. Aim is to avoid to
build a monochromatic subgraph isomorphic to A. In another variant, aim is
to achieve to build a monochromatic subgraph isomorphic to A. I determine
the computational complexity of finding winning strategies for several
variants of these games and ultra-strongly solve some small instances.

A Java applet that improves its strategy by playing over the Internet and
that allows to play some small but nontrivial instances can be challenged
at http://www.dbai.tuwien.ac.at/proj/ramsey/. Please try it out! In case
you win, you will be able to leave your name in our hall-of-fame.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Frank Harary
------------------
Computer Science Department, New Mexico State University

My adventures with Ramsey theory
================================
Friday, June 25, 1999, 16h c.t.

Hoersaal EI 10: A-1040 Wien, Technische Universitaet Wien, Gusshausstrasse
27-29 (Elektrotechnisches Institut "Neubau"), Erdgeschoss.

Abstract

When I heard a lecture given by the prolific Paul Erdos in London in 1962,
it seemed an omission that only complete graphs had a ramsey number. Only
in 1970 did I confide this idea to Vasek Chvatal and showed him some
ramsey numbers for noncomplete graphs. Thus my series "Generalized ramsey
theory for graphs" was begun. There are now 19 papers in this series !
During the process of developing the properties of this very rich source
of theorems, I discovered the ramsey multiplicity of a graph, its
achievement number, the fact that 4 is the only number that is NOT the
ramsey number of some graph, a ramsey theorem for finite groups, and
achievement/avoidance games, etc.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST