A canonical restricted version of van der waerden’s theorem

It is shown that there is a subsetS of integers containing no (k+1)-term arithmetic progression such that if the elements ofS are arbitrarily colored (any number of colors),S will contain ak-term arithmetic progression for which all of its terms have the same color, or all have distinct colors.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Van der Waerden 数 W(3,n) 的新上界公式

本文运用m+1色等价分布类方法,求得VanderWaerden数W(3,n)的上界为 n-1i=0(2Ri+1)<n43n,n>4.     

Heap games, numeration systems and sequences

We propose and analyze a 2-parameter family of 2-player games on two heaps of tokens, and present a strategy based on a class of sequences. The strategy looks easy, but it is actually hard. A class of exotic numeration systems is then used, which enables us to decide whether the family has an efficient strategy or not. We introduce yet another class of sequences and demonstrate its equivalence with the class of sequences defined for the strategy of our games.     

Tandem antagonistic games

We study an antagonistic sequential game of two players that undergoes two phases. Each phase is modeled by multi-dimensional random walk processes. During phase 1 (or game 1), the players exchange a series of random strikes of random magnitudes. Game 1 ends whenever one of the players sustains damages in excess of some lower threshold. However, the total damage does not exceed another upper threshold which allows the game to continue. Phase 2 (game 2) is run by another combination of random walk processes. At some point of phase 2, one of the players, after sustaining damages in excess of its third threshold, is ruined and he loses the entire game. We predict that moment, along with the total casualties to both players, and other critical information; all in terms of tractable functionals. The entire game is analyzed by tools of fluctuation theory.     

Schröder matrix as inverse of Delannoy matrix

Using Riordan arrays, we introduce a generalized Delannoy matrix by weighted Delannoy numbers. It turns out that Delannoy matrix, Pascal matrix, and Fibonacci matrix are all special cases of the generalized Delannoy matrices, meanwhile Schröder matrix and Catalan matrix also arise in involving inverses of the generalized Delannoy matrices. These connections are the focus of our paper. The half of generalized Delannoy matrix is also considered. In addition, we obtain a combinatorial interpretation for the generalized Fibonacci numbers.     

Eigenvalues,geometric expanders,sorting in rounds,and ramsey theory

Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices. These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing an explicit algorithm to sortn elements ink time units using parallel processors, where, e.g., α₂=7/4, α₃=8/5, α₄=26/17 and α₅=22/15. Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics.     

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.     

Layers of noncooperative games

We model and analyze classes of antagonistic stochastic games of two players. The actions of the players are formalized by marked point processes recording the cumulative damage to the players at any moment of time. The processes evolve until one of the processes crosses its fixed preassigned threshold of tolerance. Once the threshold is reached or exceeded at some point of the time (exit time), the associated player is ruined. Both stochastic processes are being “observed” by a third party point stochastic process, over which the information regarding the status of both players is obtained. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes. Furthermore, we also look into the game more closely by introducing an intermediate threshold (see a layer), which a losing player is to cross prior to his ruin, in order to analyze the game more scrupulously and see what makes the player lose the game.     

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.     

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].     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.     

Classes of graphs that exclude a tree and a clique and are not vertex ramsey

A class of graphs is vertex Ramsey if for allH there existsG such that for all partitions of the vertices ofG into two parts, one of the parts contains an induced copy ofH. Forb (T,K) is the class of graphs that induce neitherT norK. LetT(k, r) be the tree with radiusr such that each nonleaf is adjacent tok vertices farther from the root than itself. Gyárfás conjectured that for all treesT and cliquesK, there exists an integerb such that for allG in Forb(T,K), the chromatic number ofG is at mostb. Gyárfás' conjecture implies a weaker conjecture of Sauer that for all treesT and cliquesK, Forb(T,K) is not vertex Ramsey. We use techniques developed for attacking Gyárfás' conjecture to prove that for allq, r and sufficiently largek, Forb(T(k,r),K _q ) is not vertex Ramsey.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Hermite-Fejer type interpolation of higher order

The paper introduces Hermite-Fejér type (Hermite type) interpolation of higher order denoted by S _mn(f)(S* _mm(f)), and gives some basic properties including expression formulas, convergence relationship between S _mn(f) and H _mn(f) (Hermite-Fejér interpolation of higher order), and the saturation of S _mn(f). Supported by the Science Foundation of Shanxi Province for Returned Scholars.     

Geometries of type [L.Af*]

Let be a [L.Af*]-geometry, that is a rank 3 geometry with linear spaces as plane residues, with dual affine planes as point residues and with generalized digons as line residues. Assume that (LL) holds in . In the particular case where the plane residues are finite circles, the structure of such geometries has been strongly restricted by A. P. Sprague. Moreover, C. Lefèvre and L. Van Nypelseer have given a complete classification of such geometries under the assumption that the plane residues are affine planes. We generalize these two results for [L.Af*]-geometries.Aspirant du Fonds National Belge de la Recherche Scientifique.     

Simple proof of the existence of restricted ramsey graphs by means of a partite construction

By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK _m and does not contain two copies ofK _m with more than two vertices in common.     

Integral operators of Sturm-Liouville type

This paper extends the class of integral equations whose solutions can be generated from a finite number of particular cases to include those of Sturm-Liouville type, including the case where the associated operators are not self-adjoint. An explicit expression for the resolvent operator is generated from two particular solutions, in a form amenable to the use of approximation techniques. A usable estimate of the norm of the inverse operator is obtained even in cases where approximate solutions have to be used.