Tarski's Fixpoint Lemma and combinatorial games

Using Tarski's Fixpoint Lemma for order preserving maps of a complete lattice into itself, a new, lattice theoretic proof is given for the existence of persistent strategies for combinatorial games as well as for games with a topological tolerance and games on lattices. Further, the existence of winning strategies is obtained for games on superalgebraic lattices, which includes the case of ordinary combinatorial games. Finally, a basic representation theorem is presented for those lattices.     

Generalized Davenport-Schinzel sequences

The extremal functionEx(u, n) (introduced in the theory of Davenport-Schinzel sequences in other notation) denotes for a fixed finite alternating sequenceu=ababa... the maximum length of a finite sequencev overn symbols with no immediate repetition which does not containu. Here (following the idea of J. Neetil) we generalize this concept for arbitrary sequenceu. We summarize the already known properties ofEx(u, n) and we present also two new theorems which give good upper bounds onEx(u _i ,n). We use these theorems to describe a wide class of sequencesu (linear sequences) for whichEx(u, n)=O(n). Both theorems are used for obtaining new superlinear upper bounds as well. We partially characterize linear sequences over three symbols. We also present several problems aboutEx(u, n).Supported by Deutsche Forschungsgemeinschaft, grant We 1265/2-1.     

Null sets and games in Banach spaces

The notion of Aronszajn-null sets generalizes the notion of Lebesgue measure zero in the Euclidean space to infinite dimensional Banach spaces. We present a game-theoretic approach to Aronszajn-null sets, establish its basic properties, and discuss some ensuing open problems.     

Restriction operators, balayage and doubly orthogonal systems of analytic functions

Systems of analytic functions which are simultaneously orthogonal over each of two domains were apparently first studied in particular cases by Walsh and Szegö, and in full generality by Bergman. In principle, these are very interesting objects, allowing application to analytic continuation that is not restricted (as Weierstrassian continuation via power series) either by circular geometry or considerations of locality. However, few explicit examples are known, and in general one does not know even gross qualitative features of such systems. The main contribution of the present paper is to prove qualitative results in a quite general situation.It is by now very well known that the phenomenon of “double orthogonality” is not restricted to Bergman spaces of analytic functions, nor even indeed has it any intrinsic relation to analyticity; its essence is an eigenvalue problem arising whenever one considers the operator of restriction on a Hilbert space of functions on some set, to a subset thereof, provided this restriction is injective and compact. However, in this paper only Hilbert spaces of analytic functions are considered, especially Bergman spaces. In the case of the Hardy spaces Fisher and Micchelli discovered remarkable qualitative features of doubly orthogonal systems, and we have shown how, based on the classical potential-theoretic notion of balayage, and its modern generalizations, one can deduce analogous results in the Bergman space set-up, but with restrictions imposed on the geometry of the considered domains and measures; these were not needed in the Fisher-Micchelli analysis, but are necessary here as shown by examples.From a more constructive point of view we study the Bergman restriction operator between the unit disk and a compactly contained quadrature domain and show that the representing kernel of this operator is rational and it is expressible (as an inversion followed by a logarithmic derivative) in terms of the polynomial equation of the boundary of the inner domain.     

Chip firing and the tutte polynomial

It is shown that the generating function of critical configurations of a version of a chip firing game on a graphG is an evaluation of the Tutte polynomial ofG, thus proving a conjecture of Biggs [3]. Supported by a grant from D.G.A.P.A.     

A NOTE ON TEE ACHIEVMYT GEODETIC GAMES

Abstract

In the article “Geodetic games for graphs” by F. Buckley and F. Harary the geodetic game on a generalized wheel W_m,n is stated to be won by the first player iff m + n is odd. This is incorrect; in this paper we show that the necessary and sufficient condition for the first player is that (1) n ? 4 and m + n is odd or m = 1 and n is even, (2) m = 2 and n = 5, (3) n < 5 and m ≥ 2 and either m or n is odd.     

Some strategies for higher dimensional animal achievement games

Due to our lack in higher dimensional imagination, it is difficult to find explicit strategies for higher dimensional animal achievement games. Here, we give two methods to build up strategies step by step for increasing dimension. As applications we obtain improved bounds for the winning dimensions of certain polyominoes and new bounds for hypercube Tic-Tac-Toe with and without diagonals.     

Pre-compact families of finite sets of integers and weakly null sequences in Banach spaces

In this paper we use the Nash-Williams theory of fronts and barriers to study weakly null sequences in Banach spaces. Specifically, we show how barriers relate to the classical fact that C(K) with K a countable compactum is c₀-saturated. Another result relates the notion of a barrier to the Maurey-Rosenthal example of a weakly null sequence with no unconditional subsequences. In particular, we construct examples of weakly-null sequences which are α-unconditional but not β-unconditional.     

Classes of sequences of real numbers, games and selection properties

This is a continuation of our investigation of classes of sequences of positive real numbers satisfying some selection principles as well as having certain game-theoretic properties. We improve main results from [D. Djur?i?, Lj.D.R. Ko?inac, M.R. ?i?ovi?, Some properties of rapidly varying sequences, J. Math. Anal. Appl. 327 (2007) 1297-1306] and [D. Djur?i?, Lj.D.R. Ko?inac, M.R. ?i?ovi?, Rapidly varying sequences and rapid convergence, Topology Appl. (2008), doi: 10.1016/j.topol.2007.05.026, in press].     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

4n − 10

We show that the maximal number K₂(n) of splits in a 2-compatible split system on an n-set is exactly 4n – 10, for every n > 3.Since K₂(n) = CF₃(n)/2 where CF₃(n) is the maximal number of members in any 3-cross-free collection of (proper) subsets of an n-set, this gives a definitive answer to a question raised in 1979 by A. Karzanov who asked whether CF₃(n) is, as a function of n, of type O(n).Karzanovs question was answered first by P. Pevzner in 1987 who showed K₂(n) 6n, a result that was improved by T. Fleiner in 1998 who showed K₂(n) 5n.The argument given in the paper below establishes that the even slightly stronger inequality K₂(n) 4n – 10 holds for every n > 3; the identity K₂(n) = 4n – 10 (n > 3) then follows in conjunction with a result from a previous paper that implies K₂(n) 4n – 10. In that paper, it was also mentioned that—in analogy to well known results regarding maximal weakly compatible split systems—2-compatible split systems of maximal cardinality 4n – 10 should be expected to be cyclic. Luckily, our approach here permits us also to corroborate this expectation. As a consequence, it is now possible to generate all 2-compatible split systems on an n-set (n > 3) that have maximal cardinality 4n – 10 (or, equivalently, all 3-cross-free set systems that have maximal cardinality 8n – 20) in a straight forward, systematic manner.Received March 19, 2003     

Pattern sequences in ‹q, r›- numeration systems

Let q ≥ 2 and 0 ≤ r ≤ q − 2 be integers. In this paper, we study pattern sequences for patterns in ‹q, r›-numeration systems through their generating functions. Our result implies that any nontrivial linear combination over ? of pattern sequences chosen from different ‹q, r›-numeration systems cannot be a linear recurrence sequence. In particular, pattern sequences in different ‹q, r›-numeration systems are linearly independent over ?, while within one ‹q, r›-numeration system they can be linearly dependent ?.     

Constructing MSTD sets using bidirectional ballot sequences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We construct a new dense family of MSTD subsets of {0,1,2,…,n−1}. Our construction gives Θ(n²/n) MSTD sets, improving the previous best construction with Ω(n²/n⁴) MSTD sets by Miller, Orosz, and Scheinerman.     

GEODETIC GAMES FOR GRAPHS

ABSTRACT

Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v₁ of G. The second player B then picks v₂ ≠ v₁ and forms the geodetic closure (S₂) = ({v₁, v₂}). Now A selects v₃ ε V—S₂ and forms (S₃) = ({v₁, v₂, v₃}), etc. The player who first selects a vertex v_n such that (S_n) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.     

Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport—Schinzel sequence composed ofn symbols is Θ (nα(n)), where α(n) is the functional inverse of Ackermann’s function, and is thus very slowly increasing to infinity. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes. Work on this paper by the second author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.     

Functorial methods in the theory of group representations I

We introduce a candidate for the group algebra of a Hausdorff group which plays the same role as the group algebra of a finite group. It allows to define a natural bijection betweenk-continuous representations of the group in a Hilbert space and continuous representations of the group algebra. Such bijections are known, but to our knowledge only for locally compact groups. We can establish such a bijection for more general groups, namely Hausdorff groups, because we replace integration techniques by functorial methods, i.e., by using a duality functor which lives in certain categories of topological Banach balls (resp., unit balls of Saks spaces).This paper was written while the authors were supported by the Swiss National Science Foundation under grant 21-33644.92.     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.