Learning of winning strategies for terminal games with linear-size memory

We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If a drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph). Z. Tuza’s research has been supported in part by the grant OTKA T-049613.     

Menger-type theorems with restrictions on path lengths

If the paths of length s, joining two non-adjacent vertices u, υ of a graph cannot be destroyed by deleting less than t vertices, then there are at least t internally vertex-disjoint paths joining u and υ, each having length less than . Some constructions show that using paths of length at least s/t−1^t might be necessary.     

Dominating cliques in P5-free graphs

All induced connected subgraphs of a graphG contain a dominating set of pair-wise adjacent vertices if and only if there is no induced subgraph isomorphic to a path or a cycle of five vertices inG. Moreover, the problem of finding any given type of connected dominating sets in all members of a classG of graphs can be reduced to the graphsG∈G that have a cut-vertex or do not contain any cutsetS dominated by somes∈S. This research was supported in part by the “AKA” Research Fund of the Hungarian Academy of Sciences.     

Critical hypergraphs and intersecting set-pair systems

A method is given for solving extremal problems of the following type: determine the maximal number of vertices in a class of hypergraphs. Results are applied for τ-critical and ν-critical hypergraphs.     

Partition of <Emphasis Type="Italic">C</Emphasis><Subscript>4</Subscript>-Designs into Minimum and Maximum Number of <Emphasis Type="Italic">P</Emphasis><Subscript>3</Subscript>-Designs

Let be a C₄-design of order n and index , on the vertex set V, |V|=n. If V₁V_m=V is a partition of the vertex set, such that the intersections of the with V_i form a P₃-design of order |V_i| and the same index , for each 1im, then 2m log₃(2n+1). The minimum bound is best possible for every . The maximum bound is best possible for =2, and hence also for every even .Supported by MIUR, Italy and CNR-GNSAGAAlso affiliated with the Department of Computer Science, University of Veszprém, Hungary; supported in part by the Hungarian Scientific Research Fund, grant OTKA T-32969AMS classification: 05B05     

Inequalities for two set systems with prescribed intersections

Inequalities are presented for systems {(A _i ,B _i ):1 i m} of pairs of finite sets satisfyingA _i B _i = andA _i B _j orA _j B _i fori j.     

Self-generating hexagonal cell division patterns

Consider the plane covered by regular hexagons. We investigate division patterns in which each hexagon is divided into two new regions, each new region has six neighbouring regions and each vertex in the new structure belongs to three new regions. These patterns are of interest for cell division processes in biology and are related to a certain class of hexagonal tilings of the plane.Research supported in part by the University of Utrecht and in part by the OTKA Research Fund of the Hungarian Academy of Sciences.     

Hydration Dynamics and the Future of Small-Amplitude AFM Imaging in Air

Here, we discuss the effects that the dynamics of the hydration layer and other variables, such as the tip radius, have on the availability of imaging regimes in dynamic AFM—including multifrequency AFM. Since small amplitudes are required for high-resolution imaging, we focus on these cases. It is possible to fully immerse a sharp tip under the hydration layer and image with amplitudes similar to or smaller than the height of the hydration layer, i.e., ~1 nm. When mica or HOPG surfaces are only cleaved, molecules adhere to their surfaces, and reaching a thermodynamically stable state for imaging might take hours. During these first hours, different possibilities for imaging emerge and change, implying that these conditions must be considered and reported when imaging.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998