Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10369131" target="_blank" >RIV/00216208:11320/17:10369131 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00454-017-9899-2" target="_blank" >http://dx.doi.org/10.1007/s00454-017-9899-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-017-9899-2" target="_blank" >10.1007/s00454-017-9899-2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings

Popis výsledku v původním jazyce

An embedding $i mapsto p_iin R^d$ of the vertices of a graph $G$ is called universally completable if the following holds: For any other embedding $imapsto q_i~in R^{k}$ satisfying $q_itranspose q_j = p_itranspose p_j$ for $i = j$ and $i$ adjacent to $j$, there exists an isometry mapping the $q_i$&apos;s to the $p_i$&apos;s for all $ iin V(G)$. The notion of universal completability was introduced recently due to its relevance to the positive semidefinite matrix completion problem. In this work we focus on graph embeddings constructed using the eigenvectors of the least eigenvalue of the adjacency matrix of $G$, which we call least eigenvalue frameworks. We identify two necessary and sufficient conditions for such frameworks to be universally completable. Our conditions also allow us to give algorithms for determining whether a least eigenvalue framework is universally completable. Furthermore, our computations for Cayley graphs on $Z_2^n (n le 5)$ show that almost all of these graphs have universally completable least eigenvalue frameworks. In the second part of this work we study uniquely vector colorable (UVC) graphs, i.e., graphs for which the semidefinite program corresponding to the Lovász theta number (of the complementary graph) admits a unique optimal solution. We identify a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework. This allows us to prove that Kneser and $q$-Kneser graphs are UVC. Lastly, we show that least eigenvalue frameworks of 1-walk-regular graphs always provide optimal vector colorings and furthermore, we are able to characterize all optimal vector colorings of such graphs. In particular, we give a necessary and sufficient condition for a 1-walk-regular graph to be uniquely vector~colorable.

Název v anglickém jazyce

Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings

Popis výsledku anglicky

An embedding $i mapsto p_iin R^d$ of the vertices of a graph $G$ is called universally completable if the following holds: For any other embedding $imapsto q_i~in R^{k}$ satisfying $q_itranspose q_j = p_itranspose p_j$ for $i = j$ and $i$ adjacent to $j$, there exists an isometry mapping the $q_i$&apos;s to the $p_i$&apos;s for all $ iin V(G)$. The notion of universal completability was introduced recently due to its relevance to the positive semidefinite matrix completion problem. In this work we focus on graph embeddings constructed using the eigenvectors of the least eigenvalue of the adjacency matrix of $G$, which we call least eigenvalue frameworks. We identify two necessary and sufficient conditions for such frameworks to be universally completable. Our conditions also allow us to give algorithms for determining whether a least eigenvalue framework is universally completable. Furthermore, our computations for Cayley graphs on $Z_2^n (n le 5)$ show that almost all of these graphs have universally completable least eigenvalue frameworks. In the second part of this work we study uniquely vector colorable (UVC) graphs, i.e., graphs for which the semidefinite program corresponding to the Lovász theta number (of the complementary graph) admits a unique optimal solution. We identify a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework. This allows us to prove that Kneser and $q$-Kneser graphs are UVC. Lastly, we show that least eigenvalue frameworks of 1-walk-regular graphs always provide optimal vector colorings and furthermore, we are able to characterize all optimal vector colorings of such graphs. In particular, we give a necessary and sufficient condition for a 1-walk-regular graph to be uniquely vector~colorable.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

58

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

28

Strana od-do

265-292

Kód UT WoS článku

000406409600002

EID výsledku v databázi Scopus

—