Matrix identities and the pigeonhole principle

We show that short bounded-depth Frege proofs of matrix identities, such as PQ=IQP=I (over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since the latter principle is known to require exponential-size bounded-depth Frege proofs, it follows that the propositional version of the matrix principle also requires bounded-depth Frege proofs of exponential size.     

Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Some properties of minimal imperfect graphs

The Even Pair Lemma, proved by Meyniel, states that no minimal imperfect graph contains a pair of vertices such that all chordless paths joining them have even lengths. This Lemma has proved to be very useful in the theory of perfect graphs. The Odd Pair Conjecture, with ‘even’ replaced by ‘odd’, is the natural analogue of the Even Pair Lemma. We prove a partial result for this conjecture, namely: no minimal imperfect graph G contains a three-pair, i.e. two nonadjacent vertices u₁, u₂ such that all chordless paths of G joining u₁ to u₂ contain precisely three edges. As a by-product, we obtain short proofs of two previously known theorems: the first one is a well-known theorem of Meyniel (a graph is perfect if each of its odd cycles with at least five vertices contains at least two chords), the second one is a theorem of Olariu (a graph is perfect if it contains no odd antihole, no P₅ and no extended claw as induced subgraphs).     

Proof complexity of intuitionistic implicational formulas

We study implicational formulas in the context of proof complexity of intuitionistic propositional logic (IPC). On the one hand, we give an efficient transformation of tautologies to implicational tautologies that preserves the lengths of intuitionistic extended Frege (EF) or substitution Frege (SF) proofs up to a polynomial. On the other hand, EF proofs in the implicational fragment of IPC polynomially simulate full intuitionistic logic for implicational tautologies. The results also apply to other fragments of other superintuitionistic logics under certain conditions.In particular, the exponential lower bounds on the length of intuitionistic EF proofs by Hrube? (2007), generalized to exponential separation between EF and SF systems in superintuitionistic logics of unbounded branching by Je?ábek (2009), can be realized by implicational tautologies.     

Graphs with no M-alternating path between two vertices

Let G be a graph with a perfect matching M. In this paper, we prove two theorems to characterize the graph G in which there is no M-alternating path between two vertices x and y in G.     

Class Steiner trees and VLSI-design

We consider a generalized version of the Steiner problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with required classes of vertices and Steiner vertices, find a shortest connected subgraph containing at least one vertex of each required class. We show that this problem is NP-hard, even if there are no Steiner vertices and the graph is a tree. Moreover, the same complexity result holds if the input class Steiner graph additionally is embedded in a unit grid, if each vertex has degree at most three, and each class consists of no more than three vertices. For similar restricted versions, we prove MAX SNP-hardness and we show that there exists no polynomial-time approximation algorithm with a constant bound on the relative error, unless P = NP. We propose two efficient heuristics computing different approximate solutions in time O(¦E¦+¦V¦log¦V¦) and in time O(c(¦E¦+¦V¦log¦V¦)), respectively, where E is the set of edges in the given graph, V is the set of vertices, and c is the number of classes. We present some promising implementation results. kw]Steiner Tree; Heuristic; Approximation complexity; MAX-SNP-hardness     

Covering hypercubes by isometric paths

An isometric path is merely any shortest path between two vertices. If the vertices of the hypercube Q_n are represented by the set of 0–1 vectors of length n, an isometric path is obtained by changing the coordinates of a vector one at a time, never changing the same coordinate more than once. The minimum number of isometric paths required to cover the vertices of Q_n is at least 2ⁿ/(n+1). We show that when n+1 is a power of 2, the lower bound is in fact the minimum. In doing so, we construct a family of disjoint isometric paths which can be used to find an upper bound for additional classes of hypercubes.     

The weak pigeonhole principle for function classes in S 12

It is well known that S ¹₂ cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in S ¹₂ for provably weaker function classes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matching extension and minimum degree

Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable.     

On ringeisen's isolation game

We develop the theory of the Isolation Game on a graph G, in which two players alternately “switch” at successive vertices v not previously switched. The switching operation deletes all edges incident with v, and creates new edges between v and those vertices not previously adjacent to it. The game is won when a vertex is first isolated. Among other results, we show that n-vertex forced wins exist for all n, and that length-p forced wins exist for all p. We give generic examples of forced wins which (against best defense) can be won only very late in the game. We also prove several large classes of graphs to be unwinnable, and give a complexity results for a problem closely related to the identification of drawing strategies in I_n(G).     

Exact unprovability results for compound well-quasi-ordered combinatorial classes

In this paper we prove general exact unprovability results that show how a threshold between provability and unprovability of a finite well-quasi-orderedness assertion of a combinatorial class is transformed by the sequence-construction, multiset-construction, cycle-construction and labeled-tree-construction. Provability proofs use the asymptotic pigeonhole principle, unprovability proofs use Weiermann-style compression techniques and results from analytic combinatorics.     

Path polynomials of a circuit: a constructive approach

Let P_k denote the polynomial of the path on k vertices. We describe completely the matrix P_k (C_n), where C_n is the circuit on n vertices, using some important concepts of theory of circulant matrices. We also consider Q _k, the polynomial of the circuit on kvertices.

Using orthogonal polynomials we present constructive proofs of some results obtained recently by Bapat and Lai, Beezer and Ronghua.     

On guarding the vertices of rectilinear domains

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover.

We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem.     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

Forcing matchings on square grids

Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S M, such that S is in no other perfect matching. We show that for the 2n × 2n square grid, the forcing number of any perfect matching is bounded below by n and above by n². Both bounds are sharp. We also establish a connection between the forcing problem and the minimum feedback set problem. Finally, we present some conjectures about forcing numbers in other graphs.     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

Rank, term rank, and chromatic number

Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound and we show that this bound is sharp.     

A new upper bound for the isoperimetric number of deBruijn Networks

Delorme and Tillich found an upper bound and a lower bound for the isoperimetric number iⁿ(d) of deBruijn Networks over the alphabet {0,1,…,d − 1} using eigenvalue techniques (see [1]). We improve their upper bound for iⁿ(d) and give constructions for the sets of vertices of the deBruijn Network, which lead to our bound.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。