Extended symmetric spaces and θ-twisted involution graphs

Abstract

For a Weyl group G and an automorphism θ of order 2, the set of involutions and θ-twisted involutions can be generated by considering actions by basis elements, creating a poset structure on the elements. Haas and Helminck showed that there is a relationship between these sets and their Bruhat posets. We extend that result by considering other bases and automorphisms. We show for G = S_n, θ an involution, and any basis consisting of transpositions, the extended symmetric space is generated by a similar algorithm. Moreover, there is an isomorphism of the poset graphs for certain bases and θ.     

Sierpiński graphs as spanning subgraphs of Hanoi graphs

Hanoi graphs H _p ⁿ model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S _p ⁿ arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S _p ⁿ embeds as a spanning subgraph into H _p ⁿ if and only if p is odd or, trivially, if n = 1.     

Equitable Δ-coloring of graphs

Consider a graph $G$ consisting of a vertex set $V\left(G\right)$ and an edge set $E\left(G\right)$. Let $\Delta \left(G\right)$ and $\chi \left(G\right)$ denote the maximum degree and the chromatic number of $G$, respectively. We say that $G$ is equitably $\Delta \left(G\right)$-colorable if there exists a proper $\Delta \left(G\right)$-coloring of $G$ such that the sizes of any two color classes differ by at most one. Obviously, if $G$ is equitably $\Delta \left(G\right)$-colorable, then $\Delta \left(G\right)\ge \chi \left(G\right)$. Conversely, even if $G$ satisfies $\Delta \left(G\right)\ge \chi \left(G\right)$, we cannot guarantee that $G$ must be equitably $\Delta \left(G\right)$-colorable. In 1994, the Equitable $\Delta$-Coloring Conjecture $\left(E\Delta \mathrm{CC}\right)$ asserts that a connected graph $G$ with $\Delta \left(G\right)\ge \chi \left(G\right)$ is equitably $\Delta \left(G\right)$-colorable if $G$ is different from $K_{2n+1,2n+1}$ for all $n\ge 1$. In this paper, we give necessary conditions for a graph $G$ (not necessarily connected) with $\Delta \left(G\right)\ge \chi \left(G\right)$ to be equitably $\Delta \left(G\right)$-colorable and prove that those necessary conditions are also sufficient conditions when $G$ is a bipartite graph, or $G$ satisfies $\Delta \left(G\right)\ge \frac{\left|V\left(G\right)\right|}{3}+1$, or $G$ satisfies $\Delta \left(G\right)\le 3$.     

Turán numbers of vertex-disjoint cliques in r-partite graphs

For two graphs $G$ and $H$, the Turán number$ex(G,H)$ is the maximum number of edges in a subgraph of $G$ that contains no copy of $H$. Chen, Li, and Tu determined the Turán numbers $ex(K_{m,n},k{K}_2)$ for all $k\ge 1$ Chen et al. (2009). In this paper we will determine the Turán numbers $ex(K_{a_1,\dots ,a_r},k{K}_r)$ for all $r\ge 3$ and $k\ge 1$.     

Sharp asymptotics of large deviations in ℝ d

Given a sequence {X₁}i=1,2,3,... of i.i.d. random variables taking values in ? ^d ,d≥2, letS _n =Σ _i=1 ⁿ X _t=1. For Λ a Borel set in ? ^d having smooth boundary, witha=inf_x∈ΛI(x) the minimal value of the large deviation rate functionI(x) over Λ, we find, under suitable hypotheses, asymptotic results asn→∞, of the form $$P(S_n \in n\Gamma ) = n^\gamma e^{ - na} (d_0 + o(1))$$ where the constant γ depends sensitively on the geometry of Λ and the dimensiond, and takes values ?∞<γ≤(d?2/2). For fixeda=inf_x∈ΛI(x), we construct examples having any specific γ in this range.     

On θ-refinability of strict p-spaces

In this paper, some partial solutions are given to the problem concerning θ-refinability of strict p-spaces. It is shown that every locally compact strict p-space is θ-refinable and every locally hereditarily separable strict p-space is subparacompact.     

Some approximations of stochastic θ-integrals

In this paper, we consider problems of approximation of stochastic θ-integrals (θ)∫ ₀ ^t f(B(s))dB(s) with respect to a Brownian motion by sums of the form ∑ _k=1 ^p f_n(B _n ^θ (t_k-1))[B _n ^θ (t_k)-B _n ^θ (t_k-1], where the sequences {f_n,n∈∕#x007D; and {[B _n ^θ ,n∈∕} are convolution-type approximations of the functionf and Brownian motionB. Belorussian State University, F. Skoryna ave. 4, 220050 Minsk, Belorus. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 2, pp. 248–256, April–June, 1999. Translated by V. Mackevičius     

Results of the maximum genus of graphs

In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of Skoviera.     

Quadratic base change of θ10

In case ofGL _n overp-adic fields, it is known that Shintani base change is well behaved. However, things are not so simple for general reductive groups. In the first part of this paper, we present a counterexample to the existence of quadratic base change descent for some Galois invariant representations. These are representations of type θ₁₀. In the second part, we compute the localL-factor of θ₁₀. Unlike many other supercuspidal representations, we find that theL-factor of θ₁₀ has two poles. Finally, we discuss these two results in relation to the local Langlands correspondence. The authors are supported in part by NSF grants.     

Hamiltonian cycles in I–graphs

The I–graphs generalize the family of generalized Petersen graphs. We show that a connected I–graph which is not a generalized Petersen graph is Hamiltonian.     

k L-list λ colouring of graphs

The k L-list λ colouring of a graph G is an L-list colouring (with positive integers) where any two colours assigned to adjacent vertices do not belong to a set λ, where the avoided assignments are listed. Moreover, the length of the list L(x), for every vertex x of G, must be less than or equal to a positive integer k, where k is the number of colours. This problem is NP-complete and we present an efficient heuristic algorithm to solve it. A fundamental aspect of the algorithm we developed is a particular technique of backtracking that permits the direct reassignment of the vertices causing the conflict if, at the moment of assigning a colour to a vertex, no colour on the list associated to it is available. An application of this algorithm to the problem of assigning arriving or leaving trains to the available tracks at a railway station is also discussed.