On iterated image size for point-symmetric relations
| dc.creator | Hamidoune, Yahya Ould | |
| dc.date | 2007-04-03 | |
| dc.date.accessioned | 2026-07-07T07:54:29Z | |
| dc.date.available | 2026-07-07T07:54:29Z | |
| dc.description | Let $Γ=(V,E)$ be a point-symmetric reflexive relation and let $v\in V$ such that $|Γ(v)|$ is finite (and hence $|Γ(x)|$ is finite for all $x$, by the transitive action of the group of automorphisms). Let $j\in \N$ be an integer such that $Γ^j(v)\cap Γ^{-}(v)=\{v\}$. Our main result states that $$ |Γ^{j} (v)|\ge | Γ^{j-1} (v)| + |Γ(v)|-1.$$ As an application we have $ |Γ^{j} (v)| \ge 1+(|Γ(v)|-1)j.$ The last result confirms a recent conjecture of Seymour in the case of vertex-symmetric graphs. Also it gives a short proof for the validity of the Caccetta-Häggkvist conjecture for vertex-symmetric graphs and generalizes an additive result of Shepherdson. | |
| dc.identifier | https://arxiv.org/abs/0704.0459 | |
| dc.identifier | http://arxiv.org/abs/0704.0459 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/126625 | |
| dc.subject | Combinatorics | |
| dc.subject | 20D60 | |
| dc.title | On iterated image size for point-symmetric relations | |
| dc.type | text |