{"entities":{"Q1598795":{"pageid":1609535,"ns":120,"title":"Item:Q1598795","lastrevid":67954473,"modified":"2026-04-12T20:27:52Z","type":"item","id":"Q1598795","labels":{"en":{"language":"en","value":"Descendants in highly arc transitive digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1746234"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598795$327BF999-E8B4-4DB7-938D-D2588087D0C1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57733f774f3e7c09e68d9cdba7834008c8563402","datavalue":{"value":{"text":"Descendants in highly arc transitive digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1598795$7EE636FE-1779-44FF-BA39-D66070ABDEDB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"441a147ee41900fed4a2b1987478c997888d80c1","datavalue":{"value":"0991.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$51147182-D79D-414B-BA30-53FDD579AF4E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2c24f9b4e162ab30e5b5c1b7e63c9a87fac8d056","datavalue":{"value":"10.1016/S0012-365X(01)00171-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$1BA9FBE6-813E-4AC7-B870-3E20CE1D8CD1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1e595cfdb9b6d25414308d49993af0ec84cba5e","datavalue":{"value":{"entity-type":"item","numeric-id":703599,"id":"Q703599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598795$E7401A27-0600-4E91-A13D-ACCE753FC15C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598795$C5C61DDF-E79E-4717-A0E1-B5F5E569D14F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"948d99aa5eeeabdcba9b276ed31f146b3beac4cb","datavalue":{"value":{"time":"+2002-05-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1598795$8C9C20DB-B875-4CEA-B30A-13204A542123","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"328274916a6c8a832e270da3436189b642a2c84d","datavalue":{"value":"A digraph \\(D\\) is said to be \\(s\\)-arc transitive if Aut\\((D)\\) acts transitively on the set of \\(s\\)-arcs. A highly arc transitive digraph is a digraph that is \\(s\\)-arc transitive for every \\(s\\geq 0\\). A directed line \\(L\\) is a two way infinite sequence \\(\\ldots,v_{-1},v_0,v_1,v_2,\\ldots\\) such that \\((v_i,v_{i+1})\\) is an arc for all \\(i\\in{\\mathbb{Z}}\\). Denote by \\(\\text{desc}(L)\\) the set of vertices in \\(D\\) that can be reached by a directed path from vertices in a directed line \\(L\\). The paper gives insight into the structure of the subdigraph spanned by \\(\\text{desc}(L)\\). The main result is the following. Let \\(D\\) be a locally finite highly arc transitive digraph and let \\(L\\) be a directed line such that desc\\((L)\\) is the set of all vertices in \\(D\\). Then, there exist a directed tree \\(T\\) with in-valency 1 and finite out-valency, and an epimorphism \\(\\varphi\\colon D\\rightarrow T\\) such that (i) \\(\\text{Aut}(D)\\) acts on \\(T\\) by \\(g(\\varphi(v))=\\varphi(g(v))\\), and this action is highly arc transitive; and (ii) all the sets \\(\\varphi^{-1}(t)\\), with \\(t\\) vertex in \\(T\\), have the same finite cardinality. Let \\(v\\) be a vertex in a transitive digraph \\(D\\) with finite out-valency. The number \\(p_k\\) of vertices \\(u\\) in \\(D\\) such that there is a directed path of length \\(k\\) from \\(v\\) to \\(u\\) does not depend on \\(v\\). The out-spread of \\(D\\) is defined as \\(\\limsup_{k\\rightarrow\\infty} (p_k)^{1/k}\\). It is shown that the out-spread of a locally finite highly transitive digraph is an integer. Let \\(Z\\) be the digraph which has the set \\({\\mathbb{Z}}\\) of integers as set of vertices and the couples \\((i,i+1)\\) with \\(i\\in{\\mathbb{Z}}\\) as set of arcs. In \\textit{P. J. Cameron, C. E. Praeger} and \\textit{N. C. Wormald} [Combinatorica 13, 377-396 (1993; Zbl 0793.05065)] it is shown that if a highly arc transitive digraph \\(D\\) has out-spread 1, then there exists an homomorphism \\(\\varphi\\colon D\\rightarrow Z\\), and it is asked wheter \\(\\varphi^{-1}(0)\\) is always finite. Here, it is shown that the answer is no, but also that when both, the out-spread and the in-spread (which is the out-spread of the converse digraph) are 1, if \\(\\varphi\\colon D\\rightarrow Z\\) is an homomorphism, then all the sets \\(\\varphi^{-1}(i)\\), \\(i\\in{\\mathbb{Z}}\\), are finite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598795$750BC031-1C75-41B1-809C-25AD49226456","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"149bbc988a75081535398a6f01834cbcfd6043f6","datavalue":{"value":{"entity-type":"item","numeric-id":588051,"id":"Q588051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598795$9A9614A8-05C6-4965-84E7-37219AF8DBFA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$B4F2E120-D2E7-479C-A212-8AD213B1B691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$AE8D1D8D-216F-4464-A50E-D3FEAC4CA085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$DC611CC8-BD3E-4212-B910-C379AB90705A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5630123120b97a8b54ad7f9b02f1876bbeb71d7f","datavalue":{"value":"1746234","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598795$7EC6410C-49E6-4A98-A593-B1F89BF07305","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a5f4c3020f4ac60294a12061b56b613aa076a4b","datavalue":{"value":"highly arc transitive","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598795$C0909D73-511E-487A-953E-75E867DD8017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598795$BD288879-2F4D-4BF2-A9BA-BA0571737DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce8cedd36dc34f12e10977a3217f3fa2c4f09eb0","datavalue":{"value":"automorphisms group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598795$85DC15AC-0F20-471B-8D2D-9CD4F70638F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598795$0E6B60AA-BFE1-4E03-8533-AA14DBE25AAC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598795$C3D5D265-4BD0-4A12-BD08-87C275A31918","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e8cf0f433c3c0a3ddf70e4be8f17530ce899542","datavalue":{"value":{"entity-type":"item","numeric-id":973132,"id":"Q973132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b26a06d1349201d5f070053e91bef95416893a7","datavalue":{"value":{"amount":"+0.8451091647148132","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598795$42D83956-D4CE-427A-B2E2-683F29CEDAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4128c2c474403887920345dc473d2e664d55ec59","datavalue":{"value":{"entity-type":"item","numeric-id":653999,"id":"Q653999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7f1e3f52910ac8031551469add45465cef6d824","datavalue":{"value":{"amount":"+0.8363681435585022","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598795$BBB7540E-2AA7-4A08-A897-67C9E432E428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f86b42bbbd8bd8e2a4fa31a2358535514bb68d2","datavalue":{"value":{"entity-type":"item","numeric-id":1357656,"id":"Q1357656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01dc91dcc026bcc0150074b569c357c5d5877f96","datavalue":{"value":{"amount":"+0.8312438726425171","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598795$25F8AA28-00EE-45A3-AA59-B83C7C7A31B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4cb848dc92afb32d38bf4114b865a2054e2cf18","datavalue":{"value":{"entity-type":"item","numeric-id":2300154,"id":"Q2300154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a6d3152d6a429772b5a7b350c8448027f1c3dc4","datavalue":{"value":{"amount":"+0.8296902775764465","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598795$E0E8E8F4-233F-4E68-8476-AE9E312FC11B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdd8f6bf1266d7cf59987b5cdc21645dd1f7b6db","datavalue":{"value":{"entity-type":"item","numeric-id":1316644,"id":"Q1316644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ea0906f1884545b25716f09d1110f3cb4b924c2","datavalue":{"value":{"amount":"+0.809739351272583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598795$351D103D-C061-4527-9400-30C4C49E67CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Descendants in highly arc transitive digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Descendants_in_highly_arc_transitive_digraphs"}}}}}