On Some Problems For Graph Induced Symbolic Systems

On Some Problems For Graph Induced Symbolic Systems

dc.contributor.advisor	Sharma, Puneet
dc.creator.researcher	Kumar, Prashant
dc.date.accessioned	2025-01-23T09:23:24Z
dc.date.available	2025-01-23T09:23:24Z
dc.date.awarded	2024-08-13
dc.date.issued	2024-02-15
dc.date.registered	2016
dc.description.abstract	Symbolic dynamics was introduced in the late 19th century by Jacques Hadamard, where he applied the theory of symbolic dynamics to examine the geodesic flows on surfaces of negative curvature [Hadamard, 1898]. Later, Morse and Hedlund used symbolic dynamics as a tool to study the qualitative behavior of a general dynamical system [Morse and Hedlund, 1938]. In 1948, Shannon employed symbolic dynamics to examine certain fundamental problems in communication theory [Shannon, 1948]. The convenience of symbolic representation and easier computability of the system has attracted attention of several researchers around the globe and the topic has found applications in various branches of science and engineering. In particular, the area has found applications in areas like data storage, data transmission and communication systems to name a few [Shannon, 1948; Lind and Marcus, 1995; Kitchens, 1998]. Since it is known that every discrete dynamical system can be embodied in a symbolic dynamical system (with an appropriate number of symbols) [Fu et al., 2001], it is sufficient to study the shift spaces and its subsystems to investigate the dynamics of a general topological dynamical system. In this work, we investigate a d-dimensional shift space arising from a d-dimensional graph G = (G1;G2 :::Gd), where each graph Gi has common set of vertices and i-th graph determines the compatibility of vertices in the i-th direction. In particular, we investigate non-emptiness, finiteness, existence of periodic points and mixing notions for a d-dimensional shift space. We examine the structure of the shift space using generating matrices and establish that a d-dimensional shift of finite type is finite if and only if it is conjugate to a shift generated through permutation matrices. We establish conditions under which a two-dimensional shift space is non-empty and contains periodic points. We introduce the notion of an E-pair for a two-dimensional shift space and use it to derive sufficient conditions for non-emptiness, finiteness and periodicity of the two-dimensional shift space under discussion. Additionally, we study properties such as transitivity, directional transitivity, weak mixing, directional weak mixing and total transitivity for the two-dimensional shift space XG. We assert that if the condition (HV)i j 6= 0 , (VH)i j 6= 0 holds for all i; j 2 V (G), then the irreducibility of any generating matrix guarantees the equivalence of transitivity and directional transitivity for the shift generated by the graph G = (H;V). We present examples demonstrating that weak mixing and totally transitivity are not analogous in two-dimensional shift spaces (it is known that these two notions coincide in one-dimensional case). Further, we characterize directional transitivity (in (r;s)-direction for rs > 0) through the block representation of HrV s. We provide necessary and sufficient criteria to establish horizontal (vertical) transitivity for the shift space XG. We investigate the topological dynamics of a general two-dimensional shift space generated by a graph G = (H;V) through matrices M;N; where M;N are indexed with allowed triangular patterns of form c a b ; x z y respectively. We investigate how the characteristics of matrices M and N are related to one another. We derive sufficient conditions on M and N to exhibit non-emptiness and existence of periodic points for shift space XG. We assert that if the condition MIJ 6= 0 , NI1J1 6= 0 holds for all E-pairs (I;I1) and (J;J1); then XG is doubly (1;1)-transitive ((1;1)-weak mixing) if and only if M is an irreducible (Primitive) matrix. We establish that under imposed conditions, (1;1)-weak mixing implies (r;s)-weak mixing (for rs > 0) for XG. We provide necessary and sufficient conditions for any graph G to be expressed as a graph product of two smaller graphs. We relate the dynamics of one-dimensional shift space XG with the dynamics of component shift spaces XGi, where graph G can be expressed as graph product (Cartesian, Tensor, Lexicographic and Strong Product) of two smaller graphs G1;G2. We investigate structural properties such as non-emptiness problem and the existence of periodic points for shift spaces through graph product of two-dimensional graphs. We assert that a shift arising from Cartesian (Lexicographic, Strong) product of two-dimensional graphs is always non-empty and possesses periodic points, but the shift arising from Tensor graph product is non-empty and contains a non-empty set of periodic points if and only if each component shift space (i.e., XGi) is non-empty and possesses periodic points. Finally, we examine various mixing notions such as transitivity, directional transitivity and weak mixing for two-dimensional shift space XG (under imposed condition) through its component subshifts XGi.
dc.description.sponsorship	IIT Jodhpur
dc.description.statementofresponsibility	by Prashant Kumar
dc.format.extent	viii, 65p.
dc.identifier.accession	TP00161
dc.identifier.citation	Kumar, Prashant(2016). On Some Problems For Graph Induced Symbolic Systems,Indian Institute of Tehcnology Jodhpur
dc.identifier.uri	https://ir.iitj.ac.in/handle/123456789/167
dc.language.iso	en
dc.publisher	Indian Institute of Technology Jodhpur
dc.publisher.department	Mathematics
dc.publisher.place	Jodhpur
dc.title	On Some Problems For Graph Induced Symbolic Systems
dc.type	Thesis
dc.type.degree	Ph.D.