Source author record

Robert Šámal

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

ResearcherUnclaimed source record

math.CO quant-ph

Catalog footprint

Research overview

13works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Structure of betweenness uniform graphs with low values of betweenness centrality

This work deals with undirected graphs that have the same betweenness centrality for each vertex, so-called betweenness uniform graphs (or BUGs). The class of these graphs is not trivial and its classification is still an open problem. Recently, Gago, Coroničová-Hurajová and Madaras conjectured that for every rational $α\ge 3/4$ there exists a BUG having betweenness centrality~ $α$ . We disprove this conjecture, and provide an alternative view of the structure of betweenness-uniform graphs from the point of view of their complement. This allows us to characterise all the BUGs with betweennes centrality at most 9/10, and show that their betweenness centrality is equal to $\frac{\ell}{\ell+1}$ for some integer $\ell\le 9$ . We conjecture that this characterization extends to all the BUGs with betweenness centrality smaller than~1.

preprint2021arXiv

3-Flows with Large Support

We prove that every 3-edge-connected graph $G$ has a 3-flow $ϕ$ with the property that $|\mathop{supp}(ϕ)| \ge \frac{5}{6} |E(G)|$ . The graph $K_4$ demonstrates that this $\frac{5}{6}$ ratio is best possible; there is an infinite family where $\frac 56$ is tight.

preprint2020arXiv

A rainbow version of Mantel's Theorem

Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$ , then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$ . We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi. We include a new short proof of Mantel's Theorem we obtained as a byproduct.

preprint2020arXiv

Many flows in the group connectivity setting

Two well-known results in the world of nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero $\mathbb{Z}_2 \times \mathbb{Z}_2$ -flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero $\mathbb{Z}_6$ -flow. Dvořák and the last two authors of this paper extended these results by proving the existence of exponentially many nowhere-zero flows under the same assumptions. We revisit this setting and provide extensions and simpler proofs of these results. The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group $Γ$ , an oriented graph $G = (V,E)$ is called $Γ$ -connected if for every function $f : E \rightarrow Γ$ there is a flow $ϕ: E \rightarrow Γ$ with $ϕ(e) \neq f(e)$ for every $e \in E$ (note that taking $f = 0$ forces $ϕ$ to be nowhere-zero). Jaeger et al. proved that every oriented 3-edge-connected graph is $Γ$ -connected whenever $|Γ| \ge 6$ . We prove that there are exponentially many solutions whenever $|Γ| \ge 8$ . For the group $\mathbb{Z}_6$ we prove that for every oriented 3-edge-connected $G = (V,E)$ with $\ell = |E| - |V| \ge 11$ and every $f: E \rightarrow \mathbb{Z}_6$ , there are at least $2^{ \sqrt{\ell} / \log \ell}$ flows $ϕ$ with $ϕ(e) \neq f(e)$ for every $e \in E$ .

preprint2015arXiv

A new proof of Seymour's 6-flow theorem

Tutte's famous 5-flow conjecture asserts that every bridgeless graph has a nowhere-zero 5-flow. Seymour proved that every such graph has a nowhere-zero 6-flow. Here we give (two versions of) a new proof of Seymour's Theorem. Both are roughly equal to Seymour's in terms of complexity, but they offer an alternative perspective which we hope will be of value.

preprint2015arXiv

Cubical coloring -- fractional covering by cuts and semidefinite programming

We introduce a new graph invariant that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. We find the value of our parameter for a family of graphs based on hypercubes. These graphs play for our parameter the role that circular cliques play for the circular chromatic number. The fact that the defined parameter attains on these graphs the `correct' value suggests that the definition is a natural one. In the proof we use the eigenvalue bound for maximum cut and a recent result of Engström, Färnqvist, Jonsson, and Thapper. We also provide a polynomial time approximation algorithm based on semidefinite programming and in particular on vector chromatic number (defined by Karger, Motwani and Sudan [Approximate graph coloring by semidefinite programming, J. ACM 45 (1998), no. 2, 246--265]).

preprint2015arXiv

Universal completability, least eigenvalue frameworks, and vector colorings

An embedding $i \mapsto p_i\in \mathbb{R}^d$ of the vertices of a graph $G$ is called universally completable if the following holds: For any other embedding $i\mapsto q_i~\in \mathbb{R}^{k}$ satisfying $q_i^T q_j = p_i^T p_j$ for $i = j$ and $i$ adjacent to $j$ , there exists an isometry mapping the $q_i$ 's to the $p_i$ 's for all $i\in 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 $\mathbb{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.

preprint2013arXiv

Flow-continuous mappings -- influence of the group

Many questions at the core of graph theory can be formulated as questions about certain group-valued flows: examples are the cycle double cover conjecture, Berge-Fulkerson conjecture, and Tutte's 3-flow, 4-flow, and 5-flow conjectures. As an approach to these problems Jaeger and DeVos, Nešetřil, and Raspaud define a notion of graph morphisms continuous with respect to group-valued flows. We discuss the influence of the group on these maps. In particular, we prove that the number of flow-continuous mappings between two graphs does not depend on the group, but only on the largest order of an element of the group (i.e., on the exponent of the group). Further, there is a nice algebraic structure describing for which groups a mapping is flow-continuous. On the combinatorial side, we show that for cubic graphs the only relevant groups are $\Z_2$ , $\Z_3$ , and $\Z$ .

preprint2013arXiv

Highly arc-transitive digraphs -- counterexamples and structure

We resolve two problems of [Cameron, Praeger, and Wormald -- Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 1993]. First, we construct a locally finite highly arc-transitive digraph with universal reachability relation. Second, we provide constructions of 2-ended highly arc transitive digraphs where each `building block' is a finite bipartite graph that is not a disjoint union of complete bipartite graphs. This was conjectured impossible in the above paper. We also describe the structure of 2-ended highly arc transitive digraphs in more generality, although complete characterization remains elusive.

preprint2013arXiv

Sabidussi Versus Hedetniemi for Three Variations of the Chromatic Number

We investigate vector chromatic number, Lovasz theta of the complement, and quantum chromatic number from the perspective of graph homomorphisms. We prove an analog of Sabidussi's theorem for each of these parameters, i.e. that for each of the parameters, the value on the Cartesian product of graphs is equal to the maximum of the values on the factors. We also prove an analog of Hedetniemi's conjecture for Lovasz theta of the complement, i.e. that its value on the categorical product of graphs is equal to the minimum of its values on the factors. We conjecture that the analogous results hold for vector and quantum chromatic number, and we prove that this is the case for some special classes of graphs.

preprint2012arXiv

Cycle-continuous mappings -- order structure

Given two graphs, a mapping between their edge-sets is cycle-continuous, if the preimage of every cycle is a cycle. The motivation for this notion is Jaeger's conjecture that for every bridgeless graph there is a cycle-continuous mapping to the Petersen graph. Answering a question of DeVos, Nešetřil, and Raspaud, we prove that there exists an infinite set of graphs with no cycle-continuous mapping between them. Further extending this result, we show that every countable poset can be represented by graphs and existence of cycle-continuous mappings between them.

preprint2011arXiv

Star chromatic index

The star chromatic index $χ_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored. We obtain a near-linear upper bound in terms of the maximum degree $Δ=Δ(G)$ . Our best lower bound on $χ_s'$ in terms of $Δ$ is $2Δ(1+o(1))$ valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.

preprint2010arXiv

An Eberhard-like theorem for pentagons and heptagons

Eberhard proved that for every sequence $(p_k), 3\le k\le r, k\ne 5,7$ of non-negative integers satisfying Euler's formula $\sum_{k\ge3} (6-k) p_k = 12$ , there are infinitely many values $p_6$ such that there exists a simple convex polyhedron having precisely $p_k$ faces of length $k$ for every $k\ge3$ , where $p_k=0$ if $k>r$ . In this paper we prove a similar statement when non-negative integers $p_k$ are given for $3\le k\le r$ , except for $k=5$ and $k=7$ . We prove that there are infinitely many values $p_5,p_7$ such that there exists a simple convex polyhedron having precisely $p_k$ faces of length $k$ for every $k\ge3$ . %, where $p_k=0$ if $k>r$ . We derive an extension to arbitrary closed surfaces, yielding maps of arbitrarily high face-width. Our proof suggests a general method for obtaining results of this kind.

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.

Robert Šámal

Research overview

Is this your work?

13 publications

Structure of betweenness uniform graphs with low values of betweenness centrality

3-Flows with Large Support

A rainbow version of Mantel's Theorem

Many flows in the group connectivity setting

A new proof of Seymour's 6-flow theorem

Cubical coloring -- fractional covering by cuts and semidefinite programming

Universal completability, least eigenvalue frameworks, and vector colorings

Flow-continuous mappings -- influence of the group

Highly arc-transitive digraphs -- counterexamples and structure

Sabidussi Versus Hedetniemi for Three Variations of the Chromatic Number

Cycle-continuous mappings -- order structure

Star chromatic index

An Eberhard-like theorem for pentagons and heptagons

See the researcher in context

Building this map preview