Source author record

Simon Schmidt

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.QA Discrete Mathematics math.OA quant-ph

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Quantum symmetry vs nonlocal symmetry

We introduce the notion of nonlocal symmetry of a graph $G$ , defined as a winning quantum correlation for the $G$ -automorphism game that cannot be produced classically. Recent connections between quantum group theory and quantum information show that quantum correlations for this game correspond to tracial states on $C(\text{Qut}(G))$ -- the algebra of functions on the quantum automorphism group of $G$ . This allows us to also define nonlocal symmetry for any quantum permutation group. We investigate the differences and similarities between this and the notion of quantum symmetry, defined as non-commutativity of $C(\text{Qut}(G))$ . Roughly speaking, quantum symmetry vs nonlocal symmetry can be viewed respectively as non-classicality of our model of reality vs non-classicality of our observation of reality. We show that quantum symmetry is necessary but not sufficient for nonlocal symmetry. In particular, we show that the complete graph on five vertices is the only connected graph on five or fewer vertices with nonlocal symmetry, despite a dozen others having quantum symmetry. In particular this shows that the quantum symmetric group on four points, $S_4^+$ , does not exhibit nonlocal symmetry, answering a question from the literature. In contrast to quantum symmetry, we show that two disjoint classical automorphisms do not guarantee nonlocal symmetry. However, three disjoint automorphisms do suffice. We also give a construction of quantum permutation matrices built from a finite abelian group $Γ$ and a permutation $π$ on $|Γ|$ elements. Computational evidence suggests that for cyclic groups of increasing size almost all permutations $π$ result in nonlocal symmetry. Surprisingly, the construction never results in nonlocal symmetry when $\mathbb{Z}_2^3$ is used. We also investigate under what conditions nonlocal symmetry arises when taking unions or products of graphs.

preprint2019arXiv

On the quantum symmetry of distance-transitive graphs

In this article, we study quantum automorphism groups of distance-transitive graphs. We show that the odd graphs, the Hamming graphs $H(n,3)$ , the Johnson graphs $J(n,2)$ and the Kneser graphs $K(n,2)$ do not have quantum symmetry. We also give a table with the quantum automorphism groups of all cubic distance-transitive graphs. Furthermore, with one graph missing, we can now decide whether or not a distance-regular graph of order $\leq 20$ has quantum symmetry. Moreover, we prove that the Hoffman-Singleton graph has no quantum symmetry. On a final note, we present an example of a pair of graphs with the same intersection array (the Shrikhande graph and the $4 \times 4$ rook's graph), where one of them has quantum symmetry and the other one does not.

preprint2015arXiv

Game Distinguishing Numbers of Cartesian Products of Graphs

The distinguishing number of a graph $H$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(H)$ is the least integer $d$ such that $H$ has a $d$ -distinguishing coloring. A $d$ -distinguishing coloring is a coloring $c:V(H)\rightarrow\{1,\dots,d\}$ invariant only under the trivial automorphism. In this paper, we continue the study of a game variant of this parameter, recently introduced. The distinguishing game is a game with two players, Gentle and Rascal, with antagonist goals. This game is played on a graph $H$ with a fixed set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $H$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then Gentle wins if the coloring is $d$ -distinguishing and Rascal wins otherwise. This game defines two new invariants, which are the minimum numbers of colors needed to ensure that Gentle has a winning strategy, depending who starts the game. The invariant could eventually be infinite. In this paper, we focus on cartesian product, a graph operation well studied in the classical case. We give sufficient conditions on the order of two connected factors $H$ and $F$ relatively prime, which ensure that one of the game distinguishing numbers of the cartesian product $H\square F$ is finite. If $H$ is a so-called involutive graph, we give an upper bound of order $D^2(H)$ for one of the game distinguishing numbers of $H\square F$ . Finally, using in part the previous result, we compute the exact value of these invariants for cartesian products of relatively prime cycles. It turns out that the value is either infinite or equal to $2$ , depending on the parity of the product order.

preprint2015arXiv

On the Complexity of the Misère Version of Three Games Played on Graphs

We investigate the complexity of finding a winning strategy for the misère version of three games played on graphs : two variants of the game $\text{NimG}$ , introduced by Stockmann in 2004 and the game $\text{Vertex Geography}$ on both directed and undirected graphs. We show that on general graphs those three games are $\text{PSPACE}$ -Hard or Complete. For one $\text{PSPACE}$ -Hard variant of $\text{NimG}$ , we find an algorithm to compute an effective winning strategy in time $\mathcal{O}(\sqrt{|V(G)|}.|E(G)|)$ when $G$ is a bipartite graph.

preprint2015arXiv

The 3/5-conjecture for weakly $S(K_{1,3})$ -free forests

The $3/5$ -conjecture for the domination game states that the game domination numbers of an isolate-free graph $G$ on $n$ vertices are bounded as follows: $γ_g(G)\leq \frac{3n}5$ and $γ_g'(G)\leq \frac{3n+2}5$ . Recent progress have been done on the subject and the conjecture is now proved for graphs with minimum degree at least $2$ . One powerful tool, introduced by Bujtás is the so-called greedy strategy for \D. In particular, using this strategy, she has proved the conjecture for isolate-free forests without leafs at distance $4$ . In this paper, we improve this strategy to extend the result to the larger class of weakly $S(K_{1,3})$ -free forests, where a weakly $S(K_{1,3})$ -free forest $F$ is an isolate-free forest without induced $S(K_{1,3})$ , whose leafs are leafs of $F$ as well.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Simon Schmidt

Research overview

Is this your work?

5 publications

Quantum symmetry vs nonlocal symmetry

On the quantum symmetry of distance-transitive graphs

Game Distinguishing Numbers of Cartesian Products of Graphs

On the Complexity of the Misère Version of Three Games Played on Graphs

The 3/5-conjecture for weakly $S(K_{1,3})$ -free forests

See the researcher in context

Building this map preview

Simon Schmidt

Research overview

Is this your work?

5 publications

Quantum symmetry vs nonlocal symmetry

On the quantum symmetry of distance-transitive graphs

Game Distinguishing Numbers of Cartesian Products of Graphs

On the Complexity of the Misère Version of Three Games Played on Graphs

The 3/5-conjecture for weakly S(K1,3)S(K_{1,3})S(K1,3​)-free forests

See the researcher in context

Building this map preview

The 3/5-conjecture for weakly $S(K_{1,3})$ -free forests