A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Häggkvist conjecture

In this paper, by using minimum out-degree and minimum in-degree, we give a new lower bound on the vertex-strong connectivity of an oriented graph. In the case of a tournament, our lower bound improves that of Thomassen obtained in 1980 and which use the notion of irregularity (see [C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163]). As application, we determine a pertinent upper bound on the diameter of some oriented graphs, and in a particular case, related to Caccetta Häggkvist conjecture, we improve a result of Broersma and Li obtained in 2002 (see [H.J. Broersma, X. Li, Some approaches to a conjecture on short cycles in digraphs, Discrete Appl. Math. 120 (2002) 45–53]).     

Locally finite graphs with ends: A topological approach, II. Applications

This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [20]. They are complemented by a third part [31], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.     

La relation différence et l'anti-isomorphie

This paper deals with pairs of binary relations defined on the same finite basis and which the 3-element restrictions are isomorphic and those of 5-element restrictions are isomorphic or anti-isomorphic. To each of these pairs, we associate an equivalence relation which yields a decomposition of these relations into classes that we will characterize. As application, we get the treshold of half-reconstruction for tournaments.     

Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r−1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, and very recently the conjecture was proved for the case where r=3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r−1. In particular, this shows that the conjecture is true for (almost) regular tournaments. In the first proof, we prove auxiliary results about union of sets contained in another union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.     

Differentiable and algebroid cohomology,Van Est isomorphisms,and characteristic classes

In the first section we discuss Morita invariance of differentiable/algebroid cohomology.In the second section we extend the Van Est isomorphism to groupoids. As a first application we clarify the connection between differentiable and algebroid cohomology (proved in degree 1, and conjectured in degree 2 by Weinstein-Xu [50]). As a second application we extend Van Ests argument for the integrability of Lie algebras. Applied to Poisson manifolds, this immediately implies the integrability criterion of Hector-Dazord [14].In the third section we describe the relevant characteristic classes of representations, living in algebroid cohomology, as well as their relation to the Van Est map. This extends Evens-Lu-Weinsteins characteristic class $\theta_{L}$ [20] (hence, in particular, the modular class of Poisson manifolds), and also the classical characteristic classes of flat vector bundles [2, 30].In the last section we describe applications to Poisson geometry.     

Extension of Arrow's theorem to symmetric sets of tournaments

Arrow's impossibility theorem [K.J. Arrow, Social Choice and Individual Values, Wiley, New York, NY, 1951] shows that the set of acyclic tournaments is not closed to non-dictatorial Boolean aggregation. In this paper we extend the notion of aggregation to general tournaments and we show that for tournaments with four vertices or more any proper symmetric (closed to vertex permutations) subset cannot be closed to non-dictatorial monotone aggregation and to non-neutral aggregation. We also demonstrate a proper subset of tournaments that is closed to parity aggregation for an arbitrarily large number of vertices. This proves a conjecture of Kalai [Social choice without rationality, Reviewed NAJ Economics 3(4)] for the non-neutral and the non-dictatorial and monotone cases and gives a counter example for the general case.     

Elliptic curve analogues of a pseudorandom generator

Using the discrete logarithm in [7] and [9] a large family of pseudorandom binary sequences was constructed. Here we extend this construction. An interesting feature of this extension is that in certain special cases we get sequences involving points on elliptic curves.     

Standard Monomial Theory for Bott–Samelson Varieties

Bott–Samelson varieties are an important tool in geometric representation theory [1, 3, 10, 25]. They were originally defined as desingularizations of Schubert varieties and share many of the properties of Schubert varieties. They have an action of a Borel subgroup, and the projective coordinate ring of a Bott–Samelson variety splits into certain generalized Demazure modules (which also appear in other contexts [22, 23]). Standard Monomial Theory, developed by Seshadri and the first author [15, 16], and recently completed by the second author [20], gives explicit bases for the Demazure modules associated to Schubert varieties. In this paper, we extend the techniques of [20] to give explicit bases for the generalized Demazure modules associated to Bott–Samelson varieties, thus proving a strengthened form of the results announced by the first and third authors in [12] (see also [13]). We also obtain more elementary proofs of the cohomology vanishing theorems of Kumar [10] and Mathieu [25]; of the projective normality of Bott–Samelson varieties; and of the Demazure character formula.     

Choosability of K5-minor-free graphs

Thomassen, 1994 showed that all planar graphs are 5-choosable. In this paper we extend this result, by showing that all K₅-minor-free graphs are 5-choosable.     

On some riesz bases

In this paper we consider three problems concerning systems of vector exponentials. In the first part we prove a conjecture of V. Komornik raised in [14] on the independence of the movement of a rectangular membrane in different points. It was independently proved by M. Horváth [9] and S. A. Avdonin (personal communication). The analogous problem for the circular membrane was partly solved in [3] — the complete solution is given in [10]. In the second part we fill in a gap in the theory of Blaschke-Potapov products developed in the paper [19] of Potapov. Namely we prove that the Blaschke-Potapov product is determined by its kernel sets up to a multiplicative constant matrix. In the third part of the present paper we give a multidimensional generalization of the notion of sine type function developed by Levin [16], [17] and by our generalization we prove the multidimensional variant of the Levin-Golovin basis theorem [16], [6].     

Cubic vertices in planar hypohamiltonian graphs

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in J. Graph Theory [79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.     

A Unified Approach to Generalized Stirling Functions

Here presented is a unified approach to generalized Stirling functions by using generalized factorial functions, k-Gamma functions, generalized divided difference, and the unified expression of Stirling numbers defined in [16]. Previous well-known Stirling functions introduced by Butzer and Hauss [4], Butzer, Kilbas, and Trujilloet [6] and others are included as particular cases of our generalization. Some basic properties related to our general pattern such as their recursive relations, generating functions, and asymptotic properties are discussed,which extend the corresponding results about the Stirling numbers shown in [21] to the defined Stirling functions.     

Morse Theory for Geodesics in Conical Manifolds

The aim of this paper is to extend the Morse theory for geodesics to the conical manifolds. In a previous paper [15] we defined these manifolds as submanifolds of with a finite number of conical singularities. To formulate a good Morse theory we use an appropriate definition of geodesic, introduced in the cited work. The main theorem of this paper (see Theorem 3.6, section 3) proofs that, although the energy is nonsmooth, we can find a continuous retraction of its sublevels in absence of critical points. So, we can give a good definition of index for isolated critical values and for isolated critical points. We prove that Morse relations hold and, at last, we give a definition of multiplicity of geodesics which is geometrical meaningful. In section 5 we compare our theory with the weak slope approach existing in literature. Some examples are also provided.     

Note on Kocay's 3-Hypergraphs and Stockmeyer's Tournaments

In this note, we study the nonreconstructibility property through examples given by Stockmeyer (for tournaments) and Kocay (for 3-hypergraphs). Relating these examples we show how to obtain non (−1)-reconstructible ternary relations from particular non (−1)-reconstructible binary ones.     

On the 3-kings and 4-kings in multipartite tournaments

Koh and Tan gave a sufficient condition for a 3-partite tournament to have at least one 3-king in [K.M. Koh, B.P. Tan, Kings in multipartite tournaments, Discrete Math. 147 (1995) 171-183, Theorem 2]. In Theorem 1 of this paper, we extend this result to n-partite tournaments, where n?3. In [K.M. Koh, B.P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Math. 154 (1996) 281-287, K.M. Koh, B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167/168 (1997) 411-418] Koh and Tan showed that in any n-partite tournament with no transmitters and 3-kings, where n?2, the number of 4-kings is at least eight, and completely characterized all n-partite tournaments having exactly eight 4-kings and no 3-kings. Using Theorem 1, we strengthen substantially the above result for n?3. Motivated by the strengthened result, we further show that in any n-partite tournament T with no transmitters and 3-kings, where n?3, if there are r partite sets of T which contain 4-kings, where 3?r?n, then the number of 4-kings in T is at least r+8. An example is given to justify that the lower bound is sharp.     

The Vietoris hyperspace structure for approach spaces

We show that there exists a natural approach version of the topological Vietoris hyperspace construction [16], [17] which has several advantages over the topological version. In the first place the important structural fact that the Vietoris construction can now also be considered, not only for topological but also intrinsically for metric spaces, but equally important in the second place the fact that we can considerably strengthen fundamental classic results. In this paper we mainly pay attention to properties concerning or involving compactness. As main results, in the first place we prove that it is not merely compactness of the Vietoris hyperspace which is equivalent to compactness of the original space [3] but that actually in the approach setting the indices of compactness [7], [8], [9], [10] numerically completely coincide. In the second place the well-known result [3], [4], [15] which says that if the original space is compact metric then the Vietoris topology is metrizable by the Hausdorff metric gets strengthened in the sense that in the approach setting under the same conditions the Vietoris approach structure actually coincides with the Hausdorff metric. Classic results follow as easy corollaries. Besides these main results we also draw attention to the good functorial relationship between the Vietoris approach structures and the associated topologies.     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

Some results on modified Szász-Mirakjan operators

In this paper we study the mixed summation-integral type operators having Szász and Beta basis functions. We extend the study of Gupta and Noor [V. Gupta, M.A. Noor, Convergence of derivatives for certain mixed Szász-Beta operators, J. Math. Anal. Appl. 321 (1) (2006) 1-9] and obtain some direct results in local approximation without and with iterative combinations. In the last section are established direct global approximation theorems.     

First and second order sensitivity analysis of nonlinear programs under directional constraint qualification conditions

An extension and unification is presented, of the recent results of Shapiro [16] and Gatjvin & Janin [8] about second order differentiability of the optimal value function and directional differentiability of optimal solutions of perturbed mathematical programs, under a relaxed directional version of the Managasarian-Fromowitz constraint qualification condition introduced by Gollan [9]