**Summary Report**

**DIMACS Research and Education Institute**

**Graph Theory and Combinatorial Optimization**

**July 20 through August 7, 1998**

Norman L. Webb, Evaluator

Kathryn Mertz, Evaluator

November 25, 1998

The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a partnership of Rutgers University, Princeton University, AT&T Research, Bellcore, and Bell Laboratories/Lucent Technologies, sponsored a three week summer Research and Education Institute (DREI '98) at Rutgers University from July 20 through August 7, 1998, on Graph Theory and Combinatorial Optimization. A major goal of the Institute was to connect educational and research components, and facilitate communication among all participants.

Twenty-four high school teachers and one community college instructor participated in the three-week long Education Program. One director, one consultant, and three lead teachers organized and conducted activities for the Education Program. More than 140 mathematics researchers and graduate students attended the Research Program that ran concurrently and interactively with the Education Program. The Research Program was divided into three one-week workshops each organized by a coordinator. Most researchers attended the Institute for one of the three weeks. However, some researchers attended the Institute for two or three weeks. The director of the entire Institute, DREI '98, also served as the director of the Research Program.

**Evaluation Methodology**

A multiple of methods were used to gather data for the evaluation of the Institute. Participants were asked to complete two written questionnaires--a Background Questionnaire given to participants the first day they attended the Institute and an Exit Questionnaire before leaving the Institute. A total of 97 completed Background Questionnaires were received. Twenty-four were among the 25 who attended the Education Program (96%), 68 were among the 140 (48%) who attended the Research Program, and 5 were received from staff. A total of 72 participants returned completed Exit Questionnaires including 21 (84%) of those who attended the Education Program and 48 (34%) of those who attended the Research Program including 35 researchers and 13 graduate students. In addition to the written questionnaires, an evaluator attended nine of the fifteen days the Institute was held and the three Sundays prior to each week. This evaluator conducted a total of 41 interviews, 33 formal interviews with prepared questions and eight informal interviews. In addition, the evaluator observed 34 sessions held at the Institute and attended 13 of the meals.

**Program**

The Education Program addressed three main topics. Paths and cycles were discussed during the first week including factors, tree diagrams, max flows, nowhere zero flows, and matching. For the second week teachers worked in the area of topological graph theory addressing concepts such as Euler's formula, surfaces and bedding, torus, vertex coloring, unit distance graphs, connectivity, and minors. The final week focused on graph coloring including edge coloring, face coloring, and the four-color theorem. During the Institute's three weeks teachers attended classes, worked on assigned homework, worked with graph theory computer software, participated in implementation sessions provided by the lead teachers, and attended discussion of research. Each week groups of teachers were assigned research questions that they used to develop a project culminating in a presentation given to both teachers and researchers. Additional joint sessions with researchers included an introduction each Monday, plenary sessions, a weekly special presentation, an educational panel, evening sessions, and module presentations. In addition to attending the joint sessions, researchers attended research talks given by a variety of speakers and staff.

**Results**

*Participants Reported a High Overall Satisfaction*

Participants indicated on both the Exit Questionnaire and in interviews a high level of satisfaction with the Institute, noticeably higher than for the previous year. Over 90% of the responding participants (95% high school teachers, 100% of the researchers, and 92% of the graduate students) reported that their overall satisfaction with the Institute was high to extremely high.

**Cross-program Interactions Were Significant**

The level of interaction among those from the different groups was significant, greater than for the 1997 Institute. Over 86% of 21 high school teachers reported they had at least daily interactions with researchers compared to 74% in 1997. Researchers in 1998, the highest number who have responded to the Exit Questionnaire for any year, reported that 63% had at least daily interactions with high school teachers compared to 30% in 1997. The researchers also found the interactions they did have to be of value. Eighty-five percent of 33 researchers in 1998 reported their interactions with high school teachers at the Institute were of moderate to very valuable. This is compared to 54% of 13 researchers who indicated this level of value on a questionnaire in 1997. High school teachers reported their interactions with researchers were of value in about the same percentage as for 1997, 95% in 1998 as moderate to very valuable compared to 89% in 1997.

On the Exit Questionnaire participants were asked to describe the nature of the interactions with other participants while at the Institute. All of those in the Education Program reported they had at least once exchanged information with a researcher on education and on mathematics. Nine out of ten high school teachers (89%) reported they had exchanged information on mathematics two or more times a week with a researcher. Seven out of ten high school teachers (74%) reported they had exchanged information on education with a researcher at least this frequently. A large percentage of those in the Education Program reported they had engaged in more cooperative activities. All but one of the 21 Education Program participants who responded to the questionnaire reported they had collaborated with a researcher on a project, problem, or work more than once during the three weeks. Two-thirds of the respondents reported they had planned future joint work efforts with a researcher at least once during the Institute.

Researchers confirmed what teachers reported. Seventy-eight percent of those who responded reported they had exchanged information on education with an Education Program participant two or more times a week. Slightly fewer, but still 66% of the 31 researchers who responded to the questionnaire, reported they had exchanged information on mathematics with someone from the Education Program two or more times a week. Researchers also reported their conversations with high school teachers went further than just the exchange of information. Over half of the Research Program respondents reported that they had collaborated on a project, problem, or work with a high school teacher at least once. One-third reported they had planned future joint work efforts with a high school teacher.

One activity that helped increase the interactions between high school teachers and researchers that was implemented for the first time at the 1998 Institute was the teacher presentations. The organizers designed this activity specifically to have teachers assume a role as speakers at a mathematics institute where traditionally most of the talks are given by researchers. Teachers in groups of three or four were assigned a mathematical project that culminated in a presentation to the entire institute on Thursday evenings. Groups took names that represented their topic such as "The Platonic Trio," "Spare Change," and "The Invisible Nodes." Teachers consulted researchers in planning their presentation. One high school teacher reported his group had worked with six different researchers with their preparations. The high school teachers actively sought researchers who were working in the area of their project.

**Participants Increased Their Knowledge of Education and Mathematics**

Both researchers and high school teachers reported they had increased their knowledge of graph theory. Whereas over 90% of the high school teachers reported they had only a general or lower level of knowledge of graph theory, all of them reported they had increased their knowledge of this area because of attending the Institute. Eighty-four percent of the high school teachers had increased at least some their knowledge of software related to graph theory. Even though most (86%) of the researchers reported they had an advanced knowledge of graph theory, 84% reported they had increased at least some their knowledge of graph theory while at the Institute. About one-third of the researchers (36%) reported they had increased at least some their knowledge of software related to graph theory.

Both researchers and high school teachers reported they had increased their knowledge of education in high school and post secondary education. Even though teachers were very knowledgeable of curriculum and teaching mathematics prior to attending the Institute, over 50% of them reported they had increased at least some their knowledge of the high school mathematics curriculum, teaching mathematics in high school, and teaching mathematics in post secondary. Over 40% of the 43 researchers who responded to this question reported they had increased at least some their knowledge of the mathematics curriculum and teaching mathematics in high school. Only 28% of these researchers reported they had increased their knowledge of teaching in post secondary education.

**Conclusions**

Significant changes were implemented in the 1998 Institute from the previous years to increase the interaction between researchers and high chool teachers. These changes, such as the teacher presentation projects, were specifically designed to have teachers and researchers engage in meaningful activities in which those from both groups could contribute. This was done by giving teachers a project involving a product (a presentation) they had to produce. To produce this product they were required to gain knowledge of mathematics that could be obtained by talking with researchers. Because presentations incorporated some "interesting" mathematics, researchers were more likely to attend. In some reported instances, researchers reported they had gained in their own knowledge of mathematics from the teachers' presentation. This increase in interactions between the two programs was not at the expense of the mathematics component. Both researchers and high school teachers reported a high degree of overall satisfaction with the Institute and that their personal expectations had been met. For the three years that the DREI has been evaluated, the leadership has strived to develop a model for achieving integration between high school teachers and researchers. The evidence from the evaluation of the 1998 Institute indicates that significant progress had been made. Teachers not only interacted with researchers frequently, but also engaged in cooperative and collaborative activities. Even about one-third of the high school teachers reported they had planed future work with researchers.