The Experts below are selected from a list of 303 Experts worldwide ranked by ideXlab platform
Le Anh Vinh - One of the best experts on this subject based on the ideXlab platform.
-
On k-Simplexes in (2k-1)-dimensional vector spaces over finite fields
arXiv: Combinatorics, 2009Co-Authors: Le Anh VinhAbstract:We show that if the cardinality of a subset of the $(2k-1)$-dimensional vector space over a finite field with $q$ elements is $\gg q^{2k-1-\frac{1}{2k}}$, then it contains a positive proportional of all $k$-Simplexes up to congruence.
-
On $k$-Simplexes in $(2k-1)$-dimensional vector spaces over finite fields
Discrete Mathematics & Theoretical Computer Science, 2009Co-Authors: Le Anh VinhAbstract:We show that if the cardinality of a subset of the $(2k-1)$-dimensional vector space over a finite field with $q$ elements is $\gg q^{2k-1-\frac{1}{ 2k}}$, then it contains a positive proportional of all $k$-Simplexes up to congruence.
Roderick Melnik - One of the best experts on this subject based on the ideXlab platform.
-
Functional Geometry of Human Connectomes.
Scientific reports, 2019Co-Authors: Bosiljka Tadić, Miroslav Andjelković, Roderick MelnikAbstract:Mapping the brain imaging data to networks, where nodes represent anatomical brain regions and edges indicate the occurrence of fiber tracts between them, has enabled an objective graph-theoretic analysis of human connectomes. However, the latent structure on higher-order interactions remains unexplored, where many brain regions act in synergy to perform complex functions. Here we use the simplicial complexes description of human connectome, where the shared Simplexes encode higher-order relationships between groups of nodes. We study consensus connectome of 100 female (F-connectome) and of 100 male (M-connectome) subjects that we generated from the Budapest Reference Connectome Server v3.0 based on data from the Human Connectome Project. Our analysis reveals that the functional geometry of the common F&M-connectome coincides with the M-connectome and is characterized by a complex architecture of Simplexes to the 14th order, which is built in six anatomical communities, and linked by short cycles. The F-connectome has additional edges that involve different brain regions, thereby increasing the size of Simplexes and introducing new cycles. Both connectomes contain characteristic subjacent graphs that make them 3/2-hyperbolic. These results shed new light on the functional architecture of the brain, suggesting that insightful differences among connectomes are hidden in their higher-order connectivity.
-
Functional Geometry of Human Connectome and Robustness of Gender Differences
arXiv: Neurons and Cognition, 2019Co-Authors: Bosiljka Tadić, Miroslav Andjelković, Roderick MelnikAbstract:Mapping the brain imaging data to networks, where each node represents a specific area of the brain, has enabled an objective graph-theoretic analysis of human connectome. However, the latent structure on higher-order connections remains unexplored, where many brain regions acting in synergy perform complex functions. Here we analyse this hidden structure using the simplicial complexes parametrisation where the shared faces of Simplexes encode higher-order relationships between groups of nodes and emerging hyperbolic geometry. Based on data collected within the Human Connectome Project, we perform a systematic analysis of consensus networks of 100 female (F-connectome) and 100 male (M-connectome) subjects by varying the number of fibres launched. Our analysis reveals that the functional geometry of the common F\&M-connectome coincides with the M-connectome and is characterized by a complex architecture of Simplexes to the 14th order, which is built in six anatomical communities, and short cycles among them. Furthermore, the F-connectome has additional connections that involve different brain regions, thereby increasing the size of Simplexes and introducing new cycles. By providing new insights into the internal organisation of anatomical brain modules as well as into the links between them that are essential to dynamics, these results also highlight the functional gender-related differences
Kachanovich Siargey - One of the best experts on this subject based on the ideXlab platform.
-
Maillage de variétés avec les triangulations de Coxeter
HAL CCSD, 2019Co-Authors: Kachanovich SiargeyAbstract:This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation).We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud.Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal.Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of thequality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space.Cette thèse s’adresse au problème du maillage d’une variété donnée dans une dimension arbitraire. Intuitivement, on peux supposer que l’on s'est donné une variété — par exemple l’intérieur d’un tore plongé dans R9, et notre objectif est de construire une maillage de cette variété (par exemple une triangulation).Nous proposons trois contributions principales. La première est l’algorithme du tracé des variétés qui reconstruit un complexe cellulaire approchant une variété compacte et lisse de dimension m dans l’espace Euclidien Rd, pour m et d arbitraires. L’algorithme proposé utilise une triangulation T qui est supposé être une transformation linéaire de la triangulation de Freudenthal-Kuhn de Rd. La complexité dépend linéairement de la taille de la sortie dont chaque élément est calculé en temps seulement polynomial en la dimension ambiante d. Cet algorithme nécessite que la variété soit connue par un oracle d’intersection qui répond si un simplexe (d−m)-dimensionnel donné intersecte la variété. À ce titre, ce cadre est général et couvre plusieures représentations des variétés populaires, telles que le niveau d’une fonction multivariée ou les variétés données par un nuage de points.Notre deuxième contribution est une structure de données qui représente la triangulation de Freudenthal-Kuhn de Rd. À chaque étape de l’exécution, l’espace utilisé par la structure de données est au plus O(d2). La structure de données supporte plusieures opérations d’une manière efficace telles que la localisation d’un point dans la triangulation et accès aux faces et cofaces d’un simplexe donné. Les Simplexes dans une triangulation de Freudenthal-Kuhn de Rd sont encodés par une nouvelle représentation qui généralise celle de Freudenthal pour les Simplexes d-dimensionels.Enfin, nous étudions la géométrie et la combinatoire des deux types de triangulations étroitement liés : des triangulations de Freudenthal-Kuhn et des triangulations de Coxeter. Pour les triangulations de Coxeter, on démontre que la qualité des Simplexes d-dimensionels est O(1/ \sqrt{d}) comparé au simplexe régulier. Par ailleurs, nous établissons lesquelles des triangulations sont de Delaunay. Nous considérons aussi l’extension de la propriété d’être Delaunay qui s’appelle la protection et qui mesure la généricité de la triangulation de Delaunay. En particulier, nous montrons qu’une famille de triangulations de Coxeter atteint la protection O(1/d2). Nous proposons une conjecture que les deux bornes sont optimales pour les triangulations de l’espace Euclidien
-
Meshing submanifolds using Coxeter triangulations
2019Co-Authors: Kachanovich SiargeyAbstract:Cette thèse s’adresse au problème du maillage d’une variété donnée dans une dimension arbitraire. Intuitivement, on peut supposer que l’on s'est donné une variété — par exemple l’intérieur d’un tore plongé dans R9, et notre objectif est de construire un maillage de cette variété (par exemple une triangulation). Nous proposons trois contributions principales. La première est l’algorithme du tracé des variétés qui reconstruit un complexe cellulaire approchant une variété compacte et lisse de dimension m dans l’espace Euclidien Rd, pour m et d arbitraires. L’algorithme proposé utilise une triangulation T qui est supposé être une transformation linéaire de la triangulation de Freudenthal-Kuhn de Rd. La complexité dépend linéairement de la taille de la sortie dont chaque élément est calculé en temps seulement polynomial en la dimension ambiante d. Cet algorithme nécessite que la variété soit connue par un oracle d’intersection qui répond si un simplexe (d−m)-dimensionnel donné intersecte la variété. À ce titre, ce cadre est général et couvre plusieures représentations des variétés populaires, telles que le niveau d’une fonction multivariée ou les variétés données par un nuage de points. Notre deuxième contribution est une structure de données qui représente la triangulation de Freudenthal-Kuhn de Rd. À chaque étape de l’exécution, l’espace utilisé par la structure de données est au plus O(d2). La structure de données supporte plusieurs opérations d’une manière efficace telles que la localisation d’un point dans la triangulation et accès aux faces et cofaces d’un simplexe donné. Les Simplexes dans une triangulation de Freudenthal-Kuhn de Rd sont encodés par une nouvelle représentation qui généralise celle de Freudenthal pour les Simplexes d-dimensionels. Enfin, nous étudions la géométrie et la combinatoire des deux types de triangulations étroitement liés : des triangulations de Freudenthal-Kuhn et des triangulations de Coxeter. Pour les triangulations de Coxeter, on démontre que la qualité des Simplexes d-dimensionels est O(1/ \sqrt{d}) comparé au simplexe régulier. Par ailleurs, nous établissons lesquelles des triangulations sont de Delaunay. Nous considérons aussi l’extension de la propriété d’être Delaunay qui s’appelle la protection et qui mesure la généricité de la triangulation de Delaunay. En particulier, nous montrons qu’une famille de triangulations de Coxeter atteint la protection O(1/d2). Nous proposons une conjecture que les deux bornes sont optimales pour les triangulations de l’espace Euclidien.This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation). We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud. Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal. Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of the quality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space
-
Maillage de variétés avec les triangulations de Coxeter
HAL CCSD, 2019Co-Authors: Kachanovich SiargeyAbstract:This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation). We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud. Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal. Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of the quality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space.Cette thèse s’adresse au problème du maillage d’une variété donnée dans une dimension arbitraire. Intuitivement, on peut supposer que l’on s'est donné une variété — par exemple l’intérieur d’un tore plongé dans R9, et notre objectif est de construire un maillage de cette variété (par exemple une triangulation). Nous proposons trois contributions principales. La première est l’algorithme du tracé des variétés qui reconstruit un complexe cellulaire approchant une variété compacte et lisse de dimension m dans l’espace Euclidien Rd, pour m et d arbitraires. L’algorithme proposé utilise une triangulation T qui est supposé être une transformation linéaire de la triangulation de Freudenthal-Kuhn de Rd. La complexité dépend linéairement de la taille de la sortie dont chaque élément est calculé en temps seulement polynomial en la dimension ambiante d. Cet algorithme nécessite que la variété soit connue par un oracle d’intersection qui répond si un simplexe (d−m)-dimensionnel donné intersecte la variété. À ce titre, ce cadre est général et couvre plusieures représentations des variétés populaires, telles que le niveau d’une fonction multivariée ou les variétés données par un nuage de points. Notre deuxième contribution est une structure de données qui représente la triangulation de Freudenthal-Kuhn de Rd. À chaque étape de l’exécution, l’espace utilisé par la structure de données est au plus O(d2). La structure de données supporte plusieurs opérations d’une manière efficace telles que la localisation d’un point dans la triangulation et accès aux faces et cofaces d’un simplexe donné. Les Simplexes dans une triangulation de Freudenthal-Kuhn de Rd sont encodés par une nouvelle représentation qui généralise celle de Freudenthal pour les Simplexes d-dimensionels. Enfin, nous étudions la géométrie et la combinatoire des deux types de triangulations étroitement liés : des triangulations de Freudenthal-Kuhn et des triangulations de Coxeter. Pour les triangulations de Coxeter, on démontre que la qualité des Simplexes d-dimensionels est O(1/ \sqrt{d}) comparé au simplexe régulier. Par ailleurs, nous établissons lesquelles des triangulations sont de Delaunay. Nous considérons aussi l’extension de la propriété d’être Delaunay qui s’appelle la protection et qui mesure la généricité de la triangulation de Delaunay. En particulier, nous montrons qu’une famille de triangulations de Coxeter atteint la protection O(1/d2). Nous proposons une conjecture que les deux bornes sont optimales pour les triangulations de l’espace Euclidien
Bosiljka Tadić - One of the best experts on this subject based on the ideXlab platform.
-
Topology of nanonetworks grown by aggregation of Simplexes with defects
arXiv: Algebraic Topology, 2019Co-Authors: Bosiljka Tadić, Miroslav Andjelković, Milovan Šuvakov, G. J. RodgersAbstract:Motivated by the relevance of higher-order interactions in quantum physics and materials science at the nanoscale, recently a model has been introduced for new classes of networks that grow by the geometrically constrained aggregation of Simplexes (triangles, tetrahedra and higher-order cliques). Their key features are hyperbolic geometry and hierarchical architecture with simplicial complexes, which can be described by the algebraic topology of graphs. Based on the model of chemically tunable self-assembly of Simplexes [\v{S}uvakov et al., Sci.Rep 8, 1987 (2018)], here we study the impact of defect Simplexes on the course of the process and their organisation in the grown nanonetworks for varied chemical affinity parameter and the size of building Simplexes. Furthermore, we demonstrate how the presence of patterned defect bonds can be utilised to alter the structure of the assembly after the growth process is completed. In this regard, we consider the structure left by the removal of defect bonds and quantify the changes in the structure of simplicial complexes as well as in the underlying topological graph, representing 1-skeleton of the simplicial complex. By introducing new types of nanonetworks, these results open a promising application of the network science for the design of complex materials. They also provide a deeper understanding of the mechanisms underlying the higher-order connectivity in many complex systems.
-
Functional Geometry of Human Connectomes.
Scientific reports, 2019Co-Authors: Bosiljka Tadić, Miroslav Andjelković, Roderick MelnikAbstract:Mapping the brain imaging data to networks, where nodes represent anatomical brain regions and edges indicate the occurrence of fiber tracts between them, has enabled an objective graph-theoretic analysis of human connectomes. However, the latent structure on higher-order interactions remains unexplored, where many brain regions act in synergy to perform complex functions. Here we use the simplicial complexes description of human connectome, where the shared Simplexes encode higher-order relationships between groups of nodes. We study consensus connectome of 100 female (F-connectome) and of 100 male (M-connectome) subjects that we generated from the Budapest Reference Connectome Server v3.0 based on data from the Human Connectome Project. Our analysis reveals that the functional geometry of the common F&M-connectome coincides with the M-connectome and is characterized by a complex architecture of Simplexes to the 14th order, which is built in six anatomical communities, and linked by short cycles. The F-connectome has additional edges that involve different brain regions, thereby increasing the size of Simplexes and introducing new cycles. Both connectomes contain characteristic subjacent graphs that make them 3/2-hyperbolic. These results shed new light on the functional architecture of the brain, suggesting that insightful differences among connectomes are hidden in their higher-order connectivity.
-
Functional Geometry of Human Connectome and Robustness of Gender Differences
arXiv: Neurons and Cognition, 2019Co-Authors: Bosiljka Tadić, Miroslav Andjelković, Roderick MelnikAbstract:Mapping the brain imaging data to networks, where each node represents a specific area of the brain, has enabled an objective graph-theoretic analysis of human connectome. However, the latent structure on higher-order connections remains unexplored, where many brain regions acting in synergy perform complex functions. Here we analyse this hidden structure using the simplicial complexes parametrisation where the shared faces of Simplexes encode higher-order relationships between groups of nodes and emerging hyperbolic geometry. Based on data collected within the Human Connectome Project, we perform a systematic analysis of consensus networks of 100 female (F-connectome) and 100 male (M-connectome) subjects by varying the number of fibres launched. Our analysis reveals that the functional geometry of the common F\&M-connectome coincides with the M-connectome and is characterized by a complex architecture of Simplexes to the 14th order, which is built in six anatomical communities, and short cycles among them. Furthermore, the F-connectome has additional connections that involve different brain regions, thereby increasing the size of Simplexes and introducing new cycles. By providing new insights into the internal organisation of anatomical brain modules as well as into the links between them that are essential to dynamics, these results also highlight the functional gender-related differences
Chein-i Chang - One of the best experts on this subject based on the ideXlab platform.
-
recursive orthogonal projection based simplex growing algorithm
IEEE Transactions on Geoscience and Remote Sensing, 2016Co-Authors: Chein-i ChangAbstract:The simplex growing algorithm (SGA) has been widely used for finding endmembers. It can be considered as a sequential version of the well-known endmember finding algorithm, N-finder algorithm (N-FINDR), which finds endmembers one at a time by growing Simplexes. However, one of the major hurdles for N-FINDR and SGA is the calculation of simplex volume (SV) which poses a great challenge in designing any algorithm using SV as a criterion for finding endmembers. This paper develops an orthogonal projection (OP)-based SGA (OP-SGA) which essentially resolves this computational issue. It converts the issue of calculating SV to calculating the OP on previously found Simplexes without computing matrix determinants. Most importantly, a recursive Kalman filter-like OP-SGA, to be called recursive OP-SGA (ROP-SGA), can be also derived to ease computation. By virtue of ROP-SGA, several advantages and benefits in computational savings and hardware implementation can be gained for which N-FINDR and SGA do not have.
-
WHISPERS - An orthogonal projection approach to simplex growing algorithm
2015 7th Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing (WHISPERS), 2015Co-Authors: Chein-i ChangAbstract:Simplex growing algorithm (SGA) is an endmember finding algorithm which grows Simplexes one vertex at a time by finding vertexes which yield maximal simplex volumes via determinant calculation. This paper presents a new version of SGA, called orthogonal projection based simplex growing algorithm (OPSGA) which takes advantage of a simplex's geometric structure to calculate simplex volume by multiplying its height with its base where the height is the magnitude of the newly generated endmember and the base is the volume of the simplex formed by previous endmembers. With such a simple structure OPSGA can be very easily implemented with significant saving of computing time. Most importantly, OPSGA bridges gaps between fully constrained SGA and most commonly used orthogonal projection-based unconstrained technique, Automatic target generation process (ATGP) to find endmembers.