**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

**sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Helmut Veith : "June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees"**Previous message:**Helmut Veith: "June 11: B.C.Desai, Concordia Indexing and Discovery System"

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.

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

**Next message:**Helmut Veith : "June 24: A. Voronkov, Expressive power and data complexity of first-order logic over trees"**Previous message:**Helmut Veith: "June 11: B.C.Desai, Concordia Indexing and Discovery System"

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