Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

We present an algorithm for finding shortest surface non-separating cycles in graphs embedded on surfaces in time, where V is the number of vertices in the graph and g is the genus of the surface. If , this represents an improvement over previous results by Thomassen, and Erickson and Har-Peled. We also give algorithms to find a shortest non-contractible cycle in time, which improves previous results for fixed genus. This result can be applied for computing the face-width and the non-separating face-width of embedded graphs. Using similar ideas we provide the first near-linear running time algorithm for computing the face-width of a graph embedded on the projective plane, and an algorithm to find the face-width of embedded toroidal graphs in time.     

Whitney towers and gropes in 4-manifolds

Many open problems and important theorems in low-dimensional topology have been formulated as statements about certain 2-complexes called gropes. This paper describes a precise correspondence between embedded gropes in 4-manifolds and the failure of the Whitney move in terms of iterated `towers' of Whitney disks. The `flexibility' of these Whitney towers is used to demonstrate some geometric consequences for knot and link concordance connected to -solvability, -cobordism and grope concordance. The key observation is that the essential structure of gropes and Whitney towers can be described by embedded unitrivalent trees which can be controlled during surgeries and Whitney moves. It is shown that a Whitney move in a Whitney tower induces an IHX (Jacobi) relation on the embedded trees.

     

A new auto-switched chaotic system and its FPGA implementation

This paper presents a 3D chaotic system which is constructed by an auto-switched numerical resolution of multiple three dimensional continuous chaotic systems. The designed chaotic system provides complex chaotic attractors and can change its behaviors automatically via a chaotic switching-rule. Some complex dynamical behaviors are investigated and analyzed. The originality of the proposed architecture is that allows to solve the problem of the finite precision due to the digital implementation while provides a good trade-off between high security, performance and hardware resources (low power and cost). Hardware digital implementation and FPGA circuit experimental results demonstrate a promising technique can be applied in efficient embedded ciphering communication systems. Moreover, the proposed chaotic system should be very useful for the consideration of reducing negative influence of dynamical degradation in real-time embedded applications.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

Small embeddings for partial cycle systems of odd length

We prove that if m is odd then a partial m-cycle system on n vertices can be embedded in an m-cycle system on at most m((m − 2)n(n − 1) + 2n + 1) vertices and that a partial weak Steiner m-cycle system on n vertices can be embedded in an m-cycle system on m(2n + 1) vertices.     

Finitary set endofunctors are alg-universal

A category is said to be alg-universal, if every category of universal algebras can be fully embedded into it. We prove here that the category of finitary endofunctors of the category Set is alg-universal. We also present an example of a proper class of accessible set functors with no natural transformations between them (except the obvious identities). Presented by J. Adámek. The research was supported by the Grant Agency of the Czech Republic under the grant No. 201/06/0664 and by the project of Ministry of Education under the No. MSM 0021620839. Received February 14, 2006; accepted in final form April 2, 2006.     

The word problem for involutive residuated lattices and related structures

It will be shown that the word problem is undecidable for involutive residuated lattices, for finite involutive residuated lattices and certain related structures like residuated lattices. The proof relies on the fact that the monoid reduct of a group can be embedded as a monoid into a distributive involutive residuated lattice. Thus, results about groups by P. S. Novikov and W. W. Boone and about finite groups by A. M. Slobodskoi can be used. Furthermore, for any non-trivial lattice variety , the word problem is undecidable for those involutive residuated lattices and finite involutive residuated lattices whose lattice reducts belong to . In particular, the word problem is undecidable for modular and distributive involutive residuated lattices. The author would like to thank the Deutsche Telekom Stiftung for financial support. Received: 10 November 2005     

Modelling and sensitivity analysis for design of phononic crystals

The two-scale homogenization is employed to study the band gaps in strongly heterogeneous periodic elastic media – the phononic crystals. It was observed that wave propagation can be suppressed for certain frequency intervals. Moreover, the gap distribution w.r.t. the incident frequencies can be modified by changing the shape of inclusions embedded in the matrix. The sensitivity analysis formulae were derived and implemented to obtain optimized microstructures of the phononic crystals. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Characterisation and Modelling of Piezoceramic Actuator Hystereses

Piezoelectric ceramics are often used as actuators in smart structures technology. In the vast majority of papers dealing with this topic only linear constitutive relations are used. However, the electric field-strain relations of such actuators show hysteretic behaviour, which means that the piezoelectric coupling coefficient is not constant. In this study the hysteresis of a mechanically unconstrained actuator is obtained using the Michelson interferometry. The hysteretic behaviour is modelled by a Preisach model. Using these experimental data, for the modelling of an active structure with embedded piezoelectric actuators the actual coupling coefficient can then be determined with the help of the Preisach model. With this procedure the actuation strain of an embedded actuator, including the physical nonlinearities, can be calculated using the material characteristics obtained for an unconstrained actuator. For an experimental validation of the method outlined above, a Lead Zirconate Titanate (PZT) actuator is characterised experimentally and then glued to a cantilever beam. Then, the tip displacement of the actuated beam is determined experimentally and simulated numerically using the above method. The experimental and numerical results agree reasonably well if the shear lag due to the bonding layer between the actuator and the structure is taken into consideration. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Jet schemes and minimal toric embedded resolutions of rational double point singularities

Using the structure of the jet schemes of rational double point singularities, we construct “minimal embedded toric resolutions” of these singularities. We also establish, for these singularities, a correspondence between a natural class of irreducible components of the jet schemes centered at the singular locus and the set of divisors which appear on every “minimal embedded toric resolution”. We prove that this correspondence is bijective except for the E₈ singulartiy. This can be thought as an embedded Nash correspondence for rational double point singularities.     

Extreme Elevation on a 2-Manifold

Given a smoothly embedded 2-manifold in we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant under rigid motions and can be used to define features such as lines of discontinuous or continuous but non-smooth elevation. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions and are useful in matching shapes as for example in protein docking.     

Nearly light cycles in embedded graphs and crossing‐critical graphs

We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large k‐crossing‐critical graph has crossing number at most 2k + 23. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 151–156, 2006     

Stably embedded minimal hypersurfaces

We use Schoen’s curvature estimates to prove that the subfocal tubular neighborhood of a nonplanar minimal hypersurface with bounded second fundamental form, stably embedded in whose radius decays sufficiently slowly cannot be embedded. In particular such hypersurfaces admit no embedded tubular neighborhoods of constant radius, whatever small the radius. However, assuming a further hypothesis on the embedding, we prove that such hypersurfaces admit an embedded tube whose radius decays sufficiently fast.      

MacNeille completions and canonical extensions

Let be a variety of monotone bounded lattice expansions, that is, bounded lattices endowed with additional operations, each of which is order preserving or reversing in each coordinate. We prove that if is closed under MacNeille completions, then it is also closed under canonical extensions. As a corollary we show that in the case of Boolean algebras with operators, any such variety is generated by an elementary class of relational structures.

Our main technical construction reveals that the canonical extension of a monotone bounded lattice expansion can be embedded in the MacNeille completion of any sufficiently saturated elementary extension of the original structure.

     

Moral Ambivalence,Relativism, and Pluralism

David Wong (2006) has introduced the notion of moral ambivalence in the philosophical debate. In this paper, we focus on the nature of moral ambivalence and on its interpretation. We hold that moral ambivalence is not a phenomenon that provides evidence for relativism, as Wong claims, and as relativism is usually understood. Rather, ambivalence denotes a pluralist attitude, an attitude characterized by the thought that two different, even incompatible, courses of action can both be permissible when considered from a single perspective. We distinguish pluralism from relativism and argue that it is more appropriate to consider Wong’s position as an objectivist pluralism (as pluralism is characterized by Berlin and others). We also highlight the similarity between Wong and Hume’s accounts.     

Embeddings of resolvable group divisible designs with block size 3

It is proved in this paper that an RGD(3, g;v) can be embedded in an RGD(3, g;u) if and only if , , , v ≥ 3g, u ≥ 3v, and (g,v) ≠ (2,6),(2,12),(6,18).     

Classification of stable time-optimal controls on 2-manifolds

In this paper, we provide a topological classification via graphs of time-optimal flows for generic control systems of the form , x ∈ M, |u| ≤ 1, on two-dimensional orientable compact manifolds, also proving the structural stability of generic optimal flows. More precisely, adding some additional structure to topological graphs, more precisely, rotation systems, and owing to a theorem of Heffter, dating back to the 19th century, we prove that there is a one-to-one correspondence between graphs with rotation systems and couples formed by a system and the 2-D manifold of minimal genus in which the system can be embedded. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 21, Geometric Problems in Control Theory, 2004.     

Number Worlds: Visual and Experimental Access to Elementary Number Theory Concepts

Recent research demonstrates that many issues related to the structure of natural numbers and the relationship among numbers are not well grasped by students. In this article, we describe a computer-based learning environment called Number Worlds that was designed to support the exploration of elementary number theory concepts by making the essential relationships and patterns more accessible to learners. Based on our research with pre-service elementary school teachers, we show how both the visual representations embedded in the microworld, and the possibilities afforded for experimentation affect learners' understanding and appreciation of basic concepts in elementary number theory. We also discuss the aesthetic and affective dimensions of the research participants' engagement with the learning environment. This revised version was published online in July 2006 with corrections to the Cover Date.