BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Alexander Schrijver contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let $Θ(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 $Θ(G\sqcup H)>Θ(G)+Θ(H)$ and $Θ(G\boxtimes H)>Θ(G)Θ(H)$. This was shown independently by Wigderson and Zuiddam [2022] using Kadison-Dubois duality and the Axiom of choice.
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 negative entries corresponding to adjacent nodes, zero entries corresponding to distinct nonadjacent nodes, and exactly one negative eigenvalue. We give an algorithmic proof of the fact that it $G$ is a 2-connected graph, then either the nullspace representation defined by any "good" $G$-matrix with corank 2 is an outerplanar embedding of $G$, or else there exists a "good" $G$-matrix with corank 3.
We give a short proof of Szemerédi's regularity lemma, based on elementary Euclidean geometry. The general line of the proof is that of the standard proof (in fact, of Szemerédi's original proof), but most technicalities are swallowed by applying Pythagoras' theorem.
We characterize which graph invariants are partition functions of a spin model over the complex numbers, in terms of the rank growth of associated `connection matrices'.
We show that for each fixed $k$, the problem of finding $k$ pairwise vertex-disjoint directed paths between given source-sink pairs in a planar directed graph is solvable in polynomial time. In fact, it suffices to fix the number of faces needed to cover all sources and sinks. Moreover, the method can be extended to any fixed compact orientable surface (instead of the plane) and to rooted trees (instead of paths). Our approach is algebraic and is based on cohomology over graph (nonabelian) groups. More precisely, let $D=(V,A)$ be a directed graph and let $(G,\cdot)$ be a group. Call two function $ϕ,ψ:A\to G$ {\em cohomologous} if there exists a function $p:V\to G$ such that $p(u)\cdotϕ(a)\cdot p(w)^{-1}=ψ(a)$ for each arc $a=(u,w)$. Now given a function $ϕ:A\to G$ we want to find a function $ψ$ cohomologous to $ϕ$ such that each $ψ(a)$ belongs to a prescribed subset $H(a)$ of $G$. We give a polynomial-time algorithm for this problem in case $G$ is a graph group and each $H(a)$ is closed (i.e., if word $xyz$ belongs to $H(a)$ then also word $y$ belongs to $H(a)$). The method also implies that such a $ψ$ exists, if and only if for each $s\in V$ and each pair $P,Q$ of (undirected) $s-s$ paths there exists an $x\in G$ such that $x\cdotϕ(P)\cdot x^{-1}\in H(P)$ and $x\cdotϕ(Q)\cdot x^{-1}\in H(P)$. (Here $ϕ(P)$ is the product of the $ϕ(a)$ over the arcs in $P$. Similarly, $H(P)$ is the (group subset) product of the $H(a)$.)
Let $k\leq n$. Each polynomial $p\in\oR[x_1,...,x_n]$ can be uniquely written as $p=\sum_μμp_μ$, where $μ$ ranges over the set $M$ of all monomials in $\oR[x_1,...,x_k]$ and where $p_μ\in\oR[x_{k+1},...,x_n]$. If $p$ is $d$-homogeneous and $\varepsilon>0$, we say that $p$ is {\em $\varepsilon$-concentrated on the first $k$ variables} if $$\sum_{μ\in M\atop°(μ)<d}\max_{x\in\oR^{n-k}\atop\|x\|=1}p_μ(x)^2\leq\varepsilon\|p\|^2,$$ where $\|p\|$ is the Bombieri norm of $p$. We show that for each $d\in\oN$ and $\varepsilon>0$ there exists $k_{d,\varepsilon}$ such that for each $n$ and each $d$-homogeneous $p\in\oR[x_1,...,x_n]$ there exists $k\leq k_{d,\varepsilon}$ such that $p$ is $\varepsilon$-concentrated on the first $k$ variables {\em after some orthogonal transformation of $\oR^n$}. (So $k_{d,\varepsilon}$ is independent of the number $n$ of variables.) We derive this as a consequence of a more general theorem on low rank approximation of polynomials.
Virtual links were introduced by Kauffman in 1999. We characterize the virtual link invariants that are partition functions of vertex models (as considered by de la Harpe and Jones), both in the real and in the complex case. We show that for any fixed number of states, these invariants form an affine variety. Basic techniques are the first and second fundamental theorem of invariant theory for the orthogonal group (in the sense of Weyl) and some related methods from algebraic geometry.
Let $X$ be an inner product space, let $G$ be a group of orthogonal transformations of $X$, and let $R$ be a bounded $G$-stable subset of $X$. We define very weak and very strong regularity for such pairs $(R,G)$ (in the sense of Szemerédi's regularity lemma), and prove that these two properties are equivalent. Moreover, these properties are equivalent to the compactness of the space $(B(H),d_R)/G$. Here $H$ is the completion of $X$ (a Hilbert space), $B(H)$ is the unit ball in $H$, $d_R$ is the metric on $H$ given by $d_R(x,y):=\sup_{r\in R}|<r,x-y>|$, and $(B(H),d_R)/G$ is the orbit space of $(B(H),d_R)$ (the quotient topological space with the $G$-orbits as quotient classes). As applications we give Szemerédi's regularity lemma, a related regularity lemma for partitions into intervals, and a low rank approximation theorem for homogeneous polynomials.
We characterize which graph parameters are partition functions of a vertex model over an algebraically closed field of characteristic 0 (in the sense of de la Harpe and Jones). We moreover characterize when the vertex model can be taken so that its moment matrix has finite rank.
Let $A(n,d)$ be the maximum number of $0,1$ words of length $n$, any two having Hamming distance at least $d$. We prove $A(20,8)=256$, which implies that the quadruply shortened Golay code is optimal. Moreover, we show $A(18,6)\leq 673$, $A(19,6)\leq 1237$, $A(20,6)\leq 2279$, $A(23,6)\leq 13674$, $A(19,8)\leq 135$, $A(25,8)\leq 5421$, $A(26,8)\leq 9275$, $A(21,10)\leq 47$, $A(22,10)\leq 84$, $A(24,10)\leq 268$, $A(25,10)\leq 466$, $A(26,10)\leq 836$, $A(27,10)\leq 1585$, $A(25,12)\leq 55$, and $A(26,12)\leq 96$. The method is based on the positive semidefiniteness of matrices derived from quadruples of words. This can be put as constraint in a semidefinite program, whose optimum value is an upper bound for $A(n,d)$. The order of the matrices involved is huge. However, the semidefinite program is highly symmetric, by which its feasible region can be restricted to the algebra of matrices invariant under this symmetry. By block diagonalizing this algebra, the order of the matrices will be reduced so as to make the program solvable with semidefinite programming software in the above range of values of $n$ and $d$.