Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHomomorphisms from the torus
83
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus $mathbb{Z}_m^n$, where $m$ is even, to any fixed graph: we show that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some dominant phase. This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper $q$-colourings of $mathbb{Z}_m^n$ (so in particular, the discrete hypercube). We give further applications to the study of height functions and (generalised) rank functions on the discrete hypercube and disprove a conjecture of Kahn and Lawrenz. For the proof we combine methods from statistical physics, entropy and graph containers and exploit isoperimetric and algebraic properties of the torus.
rate research
Read More
Subgraph densities have been defined, and served as basic tools, both in the case of graphons (limits of dense graph sequences) and graphings (limits of bounded-degree graph sequences). While limit objects have been described for the middle ranges, the notion of subgraph densities in these limit objects remains elusive. We define subgraph densities in the orthogonality graphs on the unit spheres in dimension $d$, under appropriate sparsity condition on the subgraphs. These orthogonality graphs exhibit the main difficulties of defining subgraphs the middle range, and so we expect their study to serve as a key example to defining subgraph densities in more general Markov spaces. The problem can also be formulated as defining and computing random orthogonal representations of graphs. Orthogonal representations have played a role in information theory, optimization, rigidity theory and quantum physics, so to study random ones may be of interest from the point of view of these applications as well.
We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma, states that for each $epsilon>0$ there exists $M$ such that every triangle-free graph $G$ has an $epsilon$-approximate homomorphism to a triangle-free graph $F$ on at most $M$ vertices (here an $epsilon$-approximate homomorphism is a map $V(G) to V(F)$ where all but at most $epsilon |V(G)|^2$ edges of $G$ are mapped to edges of $F$). One consequence of our results is that the least possible $M$ in the triangle-free lemma grows faster than exponential in any polynomial in $epsilon^{-1}$. We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.
Let $C$ be a general unital AH-algebra and let $A$ be a unital simple $C^*$-algebra with tracial rank at most one. Suppose that $phi, psi: Cto A$ are two unital monomorphisms. We show that $phi$ and $psi$ are approximately unitarily equivalent if and only if beq[phi]&=&[psi] {rm in} KL(C,A), phi_{sharp}&=&psi_{sharp}tand phi^{dag}&=&psi^{dag}, eneq where $phi_{sharp}$ and $psi_{sharp}$ are continuous affine maps from tracial state space $T(A)$ of $A$ to faithful tracial state space $T_{rm f}(C)$ of $C$ induced by $phi$ and $psi,$ respectively, and $phi^{ddag}$ and $psi^{ddag}$ are induced homomorphisms from $K_1(C)$ into $Aff(T(A))/bar{rho_A(K_0(A))},$ where $Aff(T(A))$ is the space of all real affine continuous functions on $T(A)$ and $bar{rho_A(K_0(A))}$ is the closure of the image of $K_0(A)$ in the affine space $Aff(T(A)).$ In particular, the above holds for $C=C(X),$ the algebra of continuous functions on a compact metric space. An approximate version of this is also obtained. We also show that, given a triple of compatible elements $kappain KL_e(C,A)^{++},$ an affine map $gamma: T(C)to T_{rm f}(C)$ and a hm $af: K_1(C)to Aff(T(A))/bar{rho_A(K_0(A))},$ there exists a unital monomorphism $phi: Cto A$ such that $[h]=kappa,$ $h_{sharp}=gamma$ and $phi^{dag}=af.$
We consider the following problem arising from the study of human problem solving: Let $G$ be a vertex-weighted graph with marked in and out vertices. Suppose a random walker begins at the in-vertex, steps to neighbors of vertices with probability proportional to their weights, and stops upon reaching the out-vertex. Could one deduce the weights from the paths that many such walkers take? We analyze an iterative numerical solution to this reconstruction problem, in particular, given the empirical mean occupation times of the walkers. In the process, a result concerning the differentiation of a matrix pseudoinverse is given, which may be of independent interest. We then consider the existence of a choice of weights for the given occupation times, formulating a natural conjecture to the effect that -- barring obvious obstructions -- a solution always exists. It is shown that the conjecture holds for a class of graphs that includes all trees and complete graphs. Several open problems are discussed.
If the face-cycles at all the vertices in a map on a surface are of same type then the map is called semi-equivelar. There are eleven types of Archimedean tilings on the plane. All the Archimedean tilings are semi-equivelar maps. If a map $X$ on the torus is a quotient of an Archimedean tiling on the plane then the map $X$ is semi-equivelar. We show that each semi-equivelar map on the torus is a quotient of an Archimedean tiling on the plane. Vertex-transitive maps are semi-equivelar maps. We know that four types of semi-equivelar maps on the torus are always vertex-transitive and there are examples of other seven types of semi-equivelar maps which are not vertex-transitive. We show that the number of ${rm Aut}(Y)$-orbits of vertices for any semi-equivelar map $Y$ on the torus is at most six. In fact, the number of orbits is at most three except one type of semi-equivelar maps. Our bounds on the number of orbits are sharp.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
