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, let $$\mathcal{C}_k$$ be the collection of codes of cardinality at most k. Then $$A_q(n,d)$$ is at most the maximum value of $$\sum _{v\in [q]^n}x(\{v\})$$ , where x is a function $$\mathcal{C}_4\rightarrow {\mathbb {R}}_+$$ such that $$x(\emptyset )=1$$ and $$x(C)=\!0$$ if C has minimum distance less than d, and such that the $$\mathcal{C}_2\times \mathcal{C}_2$$ matrix $$(x(C\cup C'))_{C,C'\in \mathcal{C}_2}$$ is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds $$A_4(6,3)\le 176$$ , $$A_4(7,3)\le 596$$ , $$A_4(7,4)\le 155$$ , $$A_5(7,4)\le 489$$ , and $$A_5(7,5)\le 87$$ .

LetA(n,d) be the maximum number of 0, 1 words of lengthn, any two having Hamming distance at leastd. It is proved thatA(20,8)=256, which implies that the quadruply shortened Golay code is optimal. Moreover, it is shown thatA(18,6) ≤ 673,A(19,6) ≤ 1237,A(20,6) ≤ 2279,A(23,6) ≤ 13674,A(19,8) ≤ 135,A(25,8) ≤ 5421,A(26,8) ≤ 9275,A(27,8) ≤ 17099,A(21,10) ≤ 47,A(22,10) ≤ 84,A(24,10) ≤ 268,A(25,10) ≤ 466,A(26,10) ≤ 836,A(27,10) ≤ 1585,A(28,10) ≤ 2817,A(25,12) ≤ 55, andA(26,12) ≤ 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 forA(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 ofnandd.

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).

Let G be a directed planar graph of complexity n , each arc having a nonnegative length. Let s and t be two distinct faces of G let s 1 ,…, s k be vertices incident with s let t 1 ,…, t k be vertices incident with t . We give an algorithm to compute k pairwise vertex-disjoint paths connecting the pairs ( s i , t i ) in G , with minimal total length, in O ( kn log n ) time.

Let $G$ be a directed planar graph of complexity~$n$, each arc having a nonnegative length. Let $s$ and~$t$ be two distinct faces of~$G$; let $s_1,ldots,s_k$ be vertices incident with~$s$; let $t_1,ldots,t_k$ be vertices incident with~$t$. We give an algorithm to compute $k$ pairwise vertex-disjoint paths connecting the pairs $(s_i,t_i)$ in~$G$, with minimal total length, in $O(knlog n)$ time.

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows

In previous works an upper bound on the stability number $\alpha(G)$ of a graph G based on convex quadratic programming was introduced and several of its properties were established. The aim for this investigation is to relate theoretically this bound (usually represented by $\upsilon(G)$) with the well-known Lovász $\vartheta(G)$ number. First, a new set of convex quadratic bounds on $\alpha(G)$ that generalize and improve the bound $\upsilon(G)$ is proposed. Then it is proved that $\vartheta(G)$ is never worse than any bound belonging to this set of new bounds. The main result of this note states that one of these new bounds equals $\vartheta(G)$, a fact that leads to a new characterization of the Lovász theta number.

We give a new upper bound on the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. It is based on block-diagonalizing the Terwilliger algebra of the Hamming cube. The bound strengthens the Delsarte bound, and can be calculated with semidefinite programming in time bounded by a polynomial in n. We show that it improves a number of known upper bounds for concrete values of n and d. From this we also derive a new upper bound on the maximum size A(n,d,w) of a binary code of word length n, minimum distance at least d, and constant weight w, again strengthening the Delsarte bound and yielding several improved upper bounds for concrete values of n, d, and w

We prove that for a graph G=(V,E) without bad K 4 subdivision, and for $b\in {\bf Z}_{+}^{V\cup E}$, the b-stable set polytope is determined by the system of constraints determined by the vertices, edges, and odd circuits. We also prove that this system is totally dual integral. This relates to t-perfect graphs.

We show that each graph not containing a bad subdivision of -K 4 as a subgraph is strongly t-perfect. Here a graph G=(V,E) is strongly t-perfect if, for each weight function $w:V\to\mathbb{Z}_+$, the maximum weight of a stable set is equal to the minimum (total) cost of a family of vertices, edges, and circuits covering any vertex v at least w(v) times. By definition, the cost of a vertex or edge is 1, and the cost of a circuit C is $\lfloor\frac{1}{2}|VC|\rfloor$. A subdivision of K 4 is called bad if each triangle has become an odd circuit and if it is not obtained by making the edges in a 4-circuit of K 4 . evenly subdivided, while the other two edges are not subdivided. The theorem generalizes earlier results of Gerards [J. Combin. Theory Ser. B, 47 (1989), pp. 330--348] on the strong t-perfection of odd-K 4 -free graphs and of Gerards and Shepherd [SIAM J. Discrete Math., 11 (1998), pp. 524--545] on the t-perfection of bad-K 4 -free graphs.

We show that a minimum edge coloring of a bipartite graph can be found in $O(\Delta m)$ time, where $\Delta$ and m denote the maximum degree and the number of edges of G, respectively. It is equivalent to finding a perfect matching in a k-regular bipartite graph in O(km) time. By sharpening the methods, a minimum edge coloring of a bipartite graph can be found in $O((p_{\max}(\Delta)+\log \Delta)m)$ time, where $p_{\max}(\Delta)$ is the largest prime factor of $\Delta$. Moreover, a perfect matching in a k-regular bipartite graph can be found in O(p max (k)m)time.

The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Traffic demands d i,j are given for each pair of nodes in an n-node ring; each demand must be routed one of the two possible ways around the ring. The object is to minimize the maximum load on the cycle, where the load of an edge is the sum of the demands routed through that edge. We provide a fast, simple algorithm which achieves a load that is guaranteed to exceed the optimum by at most 3/2 times the maximum demand, and that performs even better in practice. En route we prove the following curious lemma: for any x 1 ,..., x n in [0,1] there exist y 1 ,..., y n such that for each k, $|y_k|=x_k$ and $$ \left| \sum_{i=1}^k y_i - \sum_{i=k+1}^n y_i \right| \le 2. $$

It is shown that, for each fixed k, the problem of finding k pairwise vertex-disjoint directed paths between given pairs of terminals in a directed planar graph is solvable in polynomial time.

Let $D = ( V,A )$ be a directed planar graph, let $( r_1 ,s_1 ), \cdots , ( r_k ,s_k )$ be pairs of vertices on the boundary of the unbounded face, let $A_1 , \cdots ,A_k $ be subsets of A, and let H be a collection of unordered pairs from $\{ 1, \cdots ,k \}$. Given are necessary and sufficient conditions for the existence of a directed $r_i - s_i $ path $P_i $ in $( V,A_i )$ (for $i = 1, \cdots ,k$), such that $P_i $ and $P_j $ are vertex-disjoint whenever $\{ i, j \} \in H$.

Let G be a planar graph, embedded without crossings in the euclidean plane $\mathbb{R}^2 $, and let $I_1 , \cdots ,I_p $ be some of its faces (including the unbounded face), considered as open sets. Suppose there exist (straight) line segments $L_1 , \cdots ,L_t $ in $\mathbb{R}^2 $ so that $G \cup I_1 \cup \cdots \cup I_p = L_1 \cup \cdots \cup L_t \cup I_1 \cup \cdots \cup I_p $ and so that each $L_i $ has its end points in $I_1 \cup \cdots \cup I_p $. Let $C_1 , \cdots ,C_k $ be curves in $\mathbb{R}^2 \backslash ( I_1 \cup \cdots \cup I_p )$ with end points in vertices of G. Conditions are described under which there exist pairwise edge-disjoint paths $P_1 , \cdots ,P_k $ in G so that $P_i $ is homotopic to $C_i $ in $\mathbb{R}^2 \backslash ( I_1 \cup \cdots \cup I_p ),$ for $i = 1, \cdots ,k$. This extends results of Kaufmann and Mehlhorn for graphs derived from the rectangular grid.

Let $E_1 ,\cdots,E_m $ be subsets of a set V of size n, such that each element of V is in at most k of the $E_i $ and such that each collection of t sets from $E_1 ,\cdots ,E_m $ has a system of distinct representatives (SDR). It is shown that $m/n\leqq (k(k - 1)^r - k)/(2(k - 1)^r - k)$ if $t = 2r - 1$, and $m/n \leqq (k(k - 1)^r - 2)/(2(k - 1)^r - 2)$ if $t = 2r$. Moreover it is shown that these upper bounds are the best possible. From these results the “worst-case ratio” of certain heuristics for the problem of finding a maximum collection of pairwise disjoint sets among a given collection of sets of size k is derived.

Delsarte's linear programming bound (an upper bound on the cardinality of cliques in association schemes) is compared with Lov\acute{a}sz's\theta-function bound (an upper bound on the Shannon capacity of a graph). The two bounds can be treated in a uniform fashion. Delsarte's linear programming bound can be generalized to a bound\theta \prime(G)on the independence number\propto(G)of an arbitrary graphG, such that\theta \prime(G) \leq \theta(G). On the other hand, if the edge set ofGis a union of classes of a symmetric association scheme,\theta(G)may be calculated by linear programming, For such graphs the product\theta(G).\theta(G)is equal to the number of vertices ofG.