Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximate Representations and Approximate Homomorphisms
167
0
0.0
(
0
)
Added by
Alexander Russell
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Approximate algebraic structures play a defining role in arithmetic combinatorics and have found remarkable applications to basic questions in number theory and pseudorandomness. Here we study approximate representations of finite groups: functions f:G -> U_d such that Pr[f(xy) = f(x) f(y)] is large, or more generally Exp_{x,y} ||f(xy) - f(x)f(y)||^2$ is small, where x and y are uniformly random elements of the group G and U_d denotes the unitary group of degree d. We bound these quantities in terms of the ratio d / d_min where d_min is the dimension of the smallest nontrivial representation of G. As an application, we bound the extent to which a function f : G -> H can be an approximate homomorphism where H is another finite group. We show that if Hs representations are significantly smaller than Gs, no such f can be much more homomorphic than a random function. We interpret these results as showing that if G is quasirandom, that is, if d_min is large, then G cannot be embedded in a small number of dimensions, or in a less-quasirandom group, without significant distortion of Gs multiplicative structure. We also prove that our bounds are tight by showing that minors of genuine representations and their polar decompositions are essentially optimal approximate representations.
rate research
Read More
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.
A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this conjecture, and also studied its implied fraction
We determine the multiplicities of irreducible summands in the symmetric and the exterior squares of hook representations of symmetric groups over an algebraically closed field of characteristic zero.
Let $C$ be a unital AH-algebra and $A$ be a unital simple C*-algebra with tracial rank zero. It has been shown that two unital monomorphisms $phi, psi: Cto A$ are approximately unitarily equivalent if and only if $$ [phi]=[psi] {rm in} KL(C,A) and taucirc phi=taucirc psi tforal tauin T(A), $$ where $T(A)$ is the tracial state space of $A.$ In this paper we prove the following: Given $kappain KL(C,A)$ with $kappa(K_0(C)_+setminus {0})subset K_0(A)_+setminus {0}$ and with $kappa([1_C])=[1_A]$ and a continuous affine map $lambda: T(A)to T_{mathtt{f}}(C)$ which is compatible with $kappa,$ where $T_{mathtt{f}}(C)$ is the convex set of all faithful tracial states, there exists a unital monomorphism $phi: Cto A$ such that $$ [phi]=kappaandeqn taucirc phi(c)=lambda(tau)(c) $$ for all $cin C_{s.a.}$ and $tauin T(A).$ Denote by ${rm Mon}_{au}^e(C,A)$ the set of approximate unitary equivalence classes of unital monomorphisms. We provide a bijective map $$ Lambda: {rm Mon}_{au}^e (C,A)to KLT(C,A)^{++}, $$ where $KLT(C,A)^{++}$ is the set of compatible pairs of elements in $KL(C,A)^{++}$ and continuous affine maps from $T(A)$ to $T_{mathtt{f}}(C).$ Moreover, we realized that there are compact metric spaces $X$, unital simple AF-algebras $A$ and $kappain KL(C(X), A)$ with $kappa(K_0(C(X))_+setminus{0})subset K_0(A)_+setminus {0}$ for which there is no hm $h: C(X)to A$ so that $[h]=kappa.$
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundamental combinatorial problem and has received extensive attention in various subdomains of algorithmics. In the area of kernelization, it is known that this problem is unlikely to have efficient preprocessing algorithms, also known as polynomial kernelizations. However, it has been shown in a recent work of Lokshtanov et al. [STOC 2017] that if one considered an appropriate notion of approximate kernelization, then this problem parameterized by the solution size does admit an approximate polynomial kernelization. In fact, Lokhtanov et al. were able to obtain a polynomial size approximate kernelization scheme (PSAKS) for Connected Vertex Cover parameterized by the solution size. A PSAKS is essentially a preprocessing algorithm whose error can be made arbitrarily close to 0. In this paper we revisit this problem, and consider parameters that are strictly smaller than the size of the solution and obtain the first polynomial size approximate kernelization schemes for the Connected Vertex Cover problem when parameterized by the deletion distance of the input graph to the class of cographs, the class of bounded treewidth graphs, and the class of all chordal graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
