SO(∀∃*) Sentences and Their Asymptotic Probabilities

We prove a 0‐1 law for the fragment of second order logic SO(∀∃*) over parametric classes of finite structures which allow only one unary atomic type. This completes the investigation of 0‐1 laws for fragments of second order logic defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0‐1 law for Σ¹₄(∀∃*) without any restriction on the number of unary types.     

On probabilistic elimination of generalized quantifiers

Let ?? be a collection of generalized quantifiers. We give a convenient characterization for the cases where the logic ??(??) has quantifier elimination for an arbitrary class of structures. The results provide a method to prove zero‐one and convergence laws for such logics with arbitrary sequences of probability measures of finite structures. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 1–36, 2001     

Linear preservers of minimal rank

It is proved that a linear transformation on the vector space of upper triangular matrices that maps the set of matrices of minimal rank 1 into itself, and either has the analogous property with respect to matrices of full minimal rank, or is bijective, is a triangular equivalence, or a flip about the south-west north-east diagonal followed by a triangular equivalence. The result can be regarded as an analogue of Marcus–Moyls theorem in the context of triangular matrices.     

Infinitesimal F-planar transformations

The theory of F-planar maps of Riemannian spaces and affinely connected spaces developed by J. Mike? and N. S. Sinyukov [1–6] naturally extends the theory of geodesic and holomorphic projective maps. In the present paper we find basic equations of infinitesimal F-planar maps and study these equations. The F-planar maps are maps between spaces endowed with affinor structures. The geometry of Riemannian spaces and affinely connected spaces endowed by affinor structures was investigated by A. P. Shirokov (see, e.g., [7–14]) who also studied maps between spaces of this type ([13, 14]).     

A scaling limit for the degree distribution in sublinear preferential attachment schemes

We consider a general class of preferential attachment schemes evolving by a reinforcement rule with respect to certain sublinear weights. In these schemes, which grow a random network, the sequence of degree distributions is an object of interest which sheds light on the evolving structures. In this article, we use a fluid limit approach to prove a functional law of large numbers for the degree structure in this class, starting from a variety of initial conditions. The method appears robust and applies in particular to ‘non‐tree’ evolutions where cycles may develop in the network. A main part of the argument is to show that there is a unique nonnegative solution to an infinite system of coupled ODEs, corresponding to a rate formulation of the law of large numbers limit, through C₀‐semigroup/dynamical systems methods. These results also resolve a question in Chung, Handjani and Jungreis (2003). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 703–731, 2016     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

Cross ratios,surface groups,PSL(<Emphasis Type="Italic">n</Emphasis>,ℝ) and diffeomorphisms of the circle

This article relates representations of surface groups to cross ratios. We first identify a connected component of the space of representations into PSL(n,ℝ) – known as the n-Hitchin component – to a subset of the set of cross ratios on the boundary at infinity of the group. Similarly, we study some representations into associated to cross ratios and exhibit a “character variety” of these representations. We show that this character variety contains all n-Hitchin components as well as the set of negatively curved metrics on the surface.     

Construction of Fuzzy σ-algebras using triangular norms

Generalizing the definitions given by the author [Fuzzy Sets and Systems4 (1980), 83–93] we introduce and study T-fuzzy σ-algebras, T being any triangular norm. The main result is that for a large class of triangular norms each T-fuzzy σ-algebra is generated, i.e., consists of all functions μ:X → [0, 1] being measurable with respect to some σ-algebra on X.     

Oriented matroids and complete-graph embeddings on surfaces

We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function f that assigns to each simple pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of f is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus g admits a complete curve arrangement with at most 2g+1 curves in contrast to the non-orientable surface where the number of curves is not bounded.     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

NASH EQUILIBRIUM OF TWO GAME MODELS ON THE RANDOM SOCIAL NETWORK

A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e''\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e''\in E(T_k)$. Two edges $e,e''\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow.     

Integrable couplings,bi‐integrable couplings and their Hamiltonian structures of the Giachetti–Johnson soliton hierarchy

On the basis of zero curvature equations from semi‐direct sums of Lie algebras, we construct integrable couplings of the Giachetti–Johnson hierarchy of soliton equations. We also establish Hamiltonian structures of the resulting integrable couplings by the variational identity. Moreover, we obtain bi‐integrable couplings of the Giachetti–Johnson hierarchy and their Hamiltonian structures by applying a class of non‐semisimple matrix loop algebras consisting of triangular block matrices. Copyright © 2014 John Wiley & Sons, Ltd.     

A Short Note on Essentially Σ1 Sentences

Guaspari (J Symb Logic 48:777–789, 1983) conjectured that a modal formula is it essentially Σ₁ (i.e., it is Σ₁ under any arithmetical interpretation), if and only if it is provably equivalent to a disjunction of formulas of the form ${\square{B}}$ . This conjecture was proved first by A. Visser. Then, in (de Jongh and Pianigiani, Logic at Work: In Memory of Helena Rasiowa, Springer-Physica Verlag, Heidelberg-New York, pp. 246–255, 1999), the authors characterized essentially Σ₁ formulas of languages including witness comparisons using the interpretability logic ILM. In this note we give a similar characterization for formulas with a binary operator interpreted as interpretability in a finitely axiomatizable extension of IΔ ₀  + Supexp and we address a similar problem for IΔ ₀  + Exp.     

Combinatorial Yang–Baxter maps arising from the tetrahedron equation

We survey the matrix product solutions of the Yang–Baxter equation recently obtained from the tetrahedron equation. They form a family of quantum R-matrices of generalized quantum groups interpolating the symmetric tensor representations of U_q(A_n?1⁽¹⁾) and the antisymmetric tensor representations of \({U_{ - {q^{ - 1}}}}\left( {A_{n - 1}^{\left( 1 \right)}} \right)\). We show that at q = 0, they all reduce to the Yang–Baxter maps called combinatorial R-matrices and describe the latter by an explicit algorithm.     

Real structures of Teichmüller spaces, Dehn twists, and moduli spaces of real curves

An orientation reversing involution of a topological compact genus surface induces an antiholomorphic involution of the Teichmüller space of genus g Riemann surfaces. Two such involutions and are conjugate in the mapping class group if and only if the corresponding orientation reversing involutions and of are conjugate in the automorphism group of . This is equivalent to saying that the quotient surfaces and are homeomorphic. Hence the Teichmüller space has distinct antiholomorphic involutions, which are also called real structures of ([7]). This result is a simple fact that follows from Royden's theorem ([4]) stating that the the mapping class group is the full group of holomorphic automorphisms of the Teichmüller space (). Let and be two real structures that are not conjugate in the mapping class group. In this paper we construct a real analytic diffeomorphism such that This mapping d is a product of full and half Dehn–twists around certain simple closed curves on the surface . This has applications to the moduli spaces of real algebraic curves. A compact Riemann surface admitting an antiholomorphic involution is a real algebraic curve of the topological type . All fixed–points of the real structure of the Teichmüller space , are real curves of the above topological type and every real curve of that topological type is represented by an element of the fixed–point set of . The fixed–point set is the Teichmüller space of real algebraic curves of the corresponding topological type. Given two different real structures and , let d the the real analytic mapping satisfying (1). It follows that d maps onto and is an explicit real analytic diffeomorphism between these Teichmüller spaces. Received 8 December 1997; accepted 12 August 1998     

Every completely polynomially bounded operator is similar to a contraction

It is proved that a bounded operator on a Hilbert space is similar to a contraction if and only if it is completely polynomially bounded. This gives a partial answer to Problem 6 of Halmos (Bull. Amer. Math. Soc.76 (1970). 877–933). The set of completely bounded maps between C¹-algebras is studied to obtain some structure, representation, and extension theorems for this class of maps. These allow a characterization of the completely bounded representations, on a Hilbert space, of any subalgebra of a C¹-algebra to be obtained. The result in the title follows by applying this characterization to the disk algebra.     

Forbidden subgraphs that imply hamiltonian‐connectedness*

It is proven that if G is a 3‐connected claw‐free graph which is also H₁‐free (where H₁ consists of two disjoint triangles connected by an edge), then G is hamiltonian‐connected. Also, examples will be described that determine a finite family of graphs such that if a 3‐connected graph being claw‐free and L‐free implies G is hamiltonian‐connected, then L . © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 104–119, 2002     

A Boundary Value Problem for Conjugate Conductivity Equations

We give explicit integral formulas for the solutions of planar conjugate conductivity equations in a circular domain of the right half‐plane with conductivity , . The representations are obtained via the so‐called unified transform method or Fokas method, involving a Riemann–Hilbert problem on the complex plane when p is even and on a two‐sheeted Riemann surface when p is odd. They are given in terms of the Dirichlet and Neumann data on the boundary of the domain. For even exponent p, we also show how to make the conversion from one type of conditions to the other by using the global relation that follows from the closedness of some differential form. The method used to derive our integral representations could be applied in any bounded simply connected domain of the right half‐plane with a smooth boundary.