Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom independent sets and vertex colorings to isotropic spaces and isotropic decompositions
93
0
0.0
(
0
)
Added by
Youming Qiao
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. This paper is dedicated to the memory of Ker-I Ko.
rate research
Read More
The decompositions of separable Werner state, and also isotropic state, are well-known tough issues in quantum information theory, in this work we investigate them in the Bloch vector representation, exploring the symmetric informationally complete positive operator-valued measure (SIC-POVM) in the Hilbert space. We successfully get the decomposition for arbitrary $Ntimes N$ Werner state in terms of regular simplexes. Meanwhile, the decomposition of isotropic state is found to be related to the decomposition of Werner state via partial transposition. It is interesting to note that in the large $N$ limit, while the Werner states are either separable or non-steerably entangled, most of the isotropic states tend to be steerable.
In set theory without the Axiom of Choice (AC), we observe new relations of the following statements with weak choice principles. 1. Every locally finite connected graph has a maximal independent set. 2. Every locally countable connected graph has a maximal independent set. 3. If in a partially ordered set all antichains are finite and all chains have size $aleph_{alpha}$, then the set has size $aleph_{alpha}$ if $aleph_{alpha}$ is regular. 4. Every partially ordered set has a cofinal well-founded subset. 5. If $G=(V_{G},E_{G})$ is a connected locally finite chordal graph, then there is an ordering $<$ of $V_{G}$ such that ${w < v : {w,v} in E_{G}}$ is a clique for each $vin V_{G}$.
By implementing algorithm
In this paper, we use the linear programming approach to find new upper bounds for the moments of isotropic measures. These bounds are then utilized for finding lower packing bounds and energy bounds for projective codes. We also show that the obtained energy bounds are sharp for several infinite families of codes.
We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a $d$-degenerate graph $G$ and an integer $k$, outputs an independent set $Y$, such that for every independent set $X$ in $G$ of size at most $k$, the probability that $X$ is a subset of $Y$ is at least $left({(d+1)k choose k} cdot k(d+1)right)^{-1}$.The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph $G$, a set $T = {{s_1, t_1}, {s_2, t_2}, ldots, {s_ell, t_ell}}$ of terminal pairs and an integer $k$, returns an induced subgraph $G^star$ of $G$ that maintains all the inclusion minimal multicuts of $G$ of size at most $k$, and does not contain any $(k+2)$-vertex connected set of size $2^{{cal O}(k)}$. In particular, $G^star$ excludes a clique of size $2^{{cal O}(k)}$ as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for Stable $s$-$t$ Separator, Stable Odd Cycle Transversal and Stable Multicut on general graphs, and for Stable Directed Feedback Vertex Set on $d$-degenerate graphs, resolving two problems left open by Marx et al. [ACM Transactions on Algorithms, 2013]. All of our algorithms can be derandomized at the cost of a small overhead in the running time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
