Zobrazeno 1 - 10
of 203
pro vyhledávání: '"Schrijver, Alexander"'
Autor:
Schrijver, Alexander
Let $\Theta(G)$ denote the Shannon capacity of a graph $G$. We give an elementary proof of the equivalence, for any graphs $G$ and $H$, of the inequalities $\Theta(G\sqcup H)>\Theta(G)+\Theta(H)$ and $\Theta(G\boxtimes H)>\Theta(G)\Theta(H)$. This wa
Externí odkaz:
http://arxiv.org/abs/2204.06853
Autor:
Polak, Sven, Schrijver, Alexander
Publikováno v:
Information Processing Letters, 143 (2019), 37-40
We give an independent set of size $367$ in the fifth strong product power of $C_7$, where $C_7$ is the cycle on $7$ vertices. This leads to an improved lower bound on the Shannon capacity of $C_7$: $\Theta(C_7)\geq 367^{1/5} > 3.2578$. The independe
Externí odkaz:
http://arxiv.org/abs/1808.07438
Publikováno v:
Designs, Codes and Cryptography, 84 (1) (2017), 87-100
For nonnegative integers $q,n,d$, let $A_q(n,d)$ denote the maximum cardinality of a code of length $n$ over an alphabet $[q]$ with $q$ letters and with minimum distance at least $d$. We consider the following upper bound on $A_q(n,d)$. For any $k$,
Externí odkaz:
http://arxiv.org/abs/1602.02531
Autor:
Lovász, László, Schrijver, Alexander
Publikováno v:
in: Journey Through Discrete Mathematics. A Tribute to Jiri Matousek, Springer (2017), 571-591
We study relations between geometric embeddings of graphs and the spectrum of associated matrices, focusing on outerplanar embeddings of graphs. For a simple connected graph $G=(V,E)$, we define a "good" $G$-matrix as a $V\times V$ matrix with negati
Externí odkaz:
http://arxiv.org/abs/1601.03434
Autor:
Schrijver, Alexander, Sevenster, Bart
We show that if $G=(V,E)$ is a 4-connected flat graph, then any real symmetric $V\times V$ matrix $M$ with exactly one negative eigenvalue and satisfying, for any two distinct vertices $i$ and $j$, $M_{ij}<0$ if $i$ and $j$ are adjacent, and $M_{ij}=
Externí odkaz:
http://arxiv.org/abs/1512.03200
Autor:
Schrijver, Alexander
The {\it partially disjoint paths problem} is: {\it given:} a directed graph, vertices $r_1,s_1,\ldots,r_k,s_k$, and a set $F$ of pairs $\{i,j\}$ from $\{1,\ldots,k\}$, {\it find:} for each $i=1,\ldots,k$ a directed $r_i-s_i$ path $P_i$ such that if
Externí odkaz:
http://arxiv.org/abs/1504.00185
We characterize the virtual link invariants that can be described as partition function of a real-valued R-matrix, by being weakly reflection positive. Weak reflection positivity is defined in terms of joining virtual link diagrams, which is a specia
Externí odkaz:
http://arxiv.org/abs/1503.01882
A {\em cyclic graph} is a graph with at each vertex a cyclic order of the edges incident with it specified. We characterize which real-valued functions on the collection of cubic cyclic graphs are partition functions of a real vertex model (P. de la
Externí odkaz:
http://arxiv.org/abs/1503.00337
Autor:
Schrijver, Alexander
Let $T$ be a set, of {\em types}, and let $\iota,o:T\to\oZ_+$. A {\em $T$-diagram} is a locally ordered directed graph $G$ equipped with a function $\tau:V(G)\to T$ such that each vertex $v$ of $G$ has indegree $\iota(\tau(v))$ and outdegree $o(\tau(
Externí odkaz:
http://arxiv.org/abs/1501.04945