33428908
Analyzing Nash-Williams' partition theorem by means of ordinal types
There is a natural way of assigning ordinal-valued functions to certain Ramsey-type theorems. In particular, they can be regarded as an extension of the classical notion of Ramsey numbers. The purpose of this paper is to obtain an estimate of these functions for the Nash-Williams' partition theorem.
33726107
A menger-like property of tree-width: The finite case
The notion of tree-width was introduced by Robertson and Symour. A graph has tree-width ≦ w if it admits a tree-decomposition of tree-width ≦ w. We prove here that if G is finite and has tree-width ≦ w then it admits a tree-decomposition of tree-width ≦ w which satisfies a certain Menger-like condition. This result will be used in a future paper on well-quasi-ordering infinite graphs of bounded tree-width.
10511288
Clique Minors in Graphs and Their Complements
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t?1 be an integer, and let G be a graph on n vertices with no minor isomorphic to Kt+1. Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has a minor isomorphic to Ks, where s=?12(1+1/t)n?c?. We prove that Kostochka's conjecture is equivalent to the conjecture of Duchet and Meyniel that every graph with no minor isomorphic to Kt+1 has an independent set of size at least n/t. We deduce that Kostochka's conjecture holds for all integers t?5, and that a weaker form with s replaced by s?=?12(1+1/(2t))n?c? holds for all integers t?1.
206570580
Sachs' Linkless Embedding Conjecture
Abstract We prove Sachs′ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K 6 by Y − Δ and Δ − Y exchanges. We also show the following: (i) A graph admits such a "linkless" embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Bohme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are "different," that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K 5 or K 3, 3 such that the two induced embeddings of this subgraph are still different.
18561897
Excluding infinite minors
Let ? be an infinite cardinal, and let H be either a complete graph with ? vertices, or a tree in which every vertex has valency ?. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H?These four questions are answered for each infinite cardinal ?. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.
2783736
List Edge-Colorings of Series-Parallel Graphs
It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least $k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
1883056
An Investigation into Keystroke Latency Metrics as an Indicator of Programming Performance
Typing has long been studied in psychology and HCI, and strong cognitive models for transcription typing exist. The goal of the present research was to test if there is any correlation between students' keystroking speed and performance while they are programming. We present the results from two studies with computer science students conducted in different contexts. Keystroke timings were recorded while they worked on Java and Ada source code. Quality of their programming work was measured mainly in terms of completeness. In the controlled experiment that lasted six hours, 39 students undertook three change tasks on a 6000 LOC Java application. In the field study, data was collected over 6 weeks from 141 students while they worked unsupervised on Ada programming in first year laboratories. In both cases there were highly significant (P=0.001), moderately strong, negative correlations between speed and coding performance. With additional development, these techniques may have promise for user modelling and assessment as well as in educational diagnostics.
9403384
A pilot study of teaching the strategic use of common computer applications
Many users do not progress from a basic use of computer applications to more efficient usage. A strategic approach to training that focuses on teaching efficient strategies in addition to commands was successfully developed by Bhavnani and John at Carnegie Mellon University. A controlled experiment comparing this method of teaching to traditional command-based instruction was performed at the University of Western Australia. We found the teaching method is transferable to the Australian context and it appears to be remarkably robust in terms of delivery, student prior experience levels and motivation. The results clearly indicate that students can be taught to use common computer applications more efficiently than they would otherwise achieve.
6336074
Developing Case Studies to Enhance Student Learning
In this paper we describe the cases developed in response to the multifaceted challenges we faced in educating IT professionals in intermediate-level programming. The challenges included: the practical nature of the subject, the level of skill attained, preparing students for the workplace and class size. We implemented Problem-Based Learning (PBL) as the teaching and learning method to meet these challenges by helping first-year university students learn programming while simultaneously developing graduate capabilities. This necessitated redevelopment of the curriculum and the way it was taught. We combined software engineering and information systems approaches in real-world scenarios. The cases were designed to help students come to terms with the human side of information technology through the context and method of teaching and learning as they worked through the cases.
33773
An Agent-Based Optimal Bidding Function
Problems such as price volatility have been observed in electric power markets. Demand-side participation is often offered as a potential solution by promising to increase market efficiency when hockey-stick type offer curves are present. However, individual end-consumer will surely value electricity differently, which makes demand-side participation as a group and at a bus difficult. In this paper demand is categorized into two groups: one that highly values reliability and the other that does not. The two types are modeled separately and a new optimal bidding function is developed and tested based on this model.
37344904
Power System Bidding Tournaments for a Deregulated Environment
In this paper we describe certain tools for understanding and operating power systems in a deregulated environment. Many of the current models for this competitive market that employ an independent system operator (ISO) for controlling transmission, ensuring fair access and security, and providing a spot market for power will be studied. This centrally-dispatched power pool also ensures that generation meets demand based on bids submitted daily from independent generators (and from customers offering interruptible loads). Currently, most I S 0 bidding models allow only a single bid per day. In this paper, we present an asynchronous bidding scheme as a possible alternative. In particular, we examine the effects of including a feedback mechanism such that upon receiving generation levels from the ISO, independent generators (IGs) be allowed to modify their bid if they so desire. This competitive or ‘sequential’ bidding process should be allowed to take place each day for a predetermined period of time; in this way, IGs will have a chance to compete and hopefully optimize their profit margins. This paper also discusses the development tools necessary for examining the effects of different bidding processes on the I S 0 model and evaluating their capability of driving the market to an efJicient state of operation.