Bounds on Pairs of Families with Restricted Intersections

such that for any , . We are interested in the maximum product , given r and L. We give asymptotically optimal bounds for L containing only elements of s<q residue classes modulo q, where q is arbitrary (even non-prime) and s is a constant. As a consequence, we obtain a version of the Frankl–R?dl result about forbidden intersections for the case of two forbidden intersections. We also give tight bounds for L={0,...,k}. Received: August 5, 1998     

On a Construction of Infinite Families of Regular Cayley Maps

Received: February 28, 1995     

Superpolynomial Lower Bounds for Monotone Span Programs

monotone span programs computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper. Our lower bounds are based on an analysis of Paley-type bipartite graphs via Weil's character sum estimates. We prove an lower bound for the size of monotone span programs for the clique problem. Our results give the first superpolynomial lower bounds for linear secret sharing schemes. We demonstrate the surprising power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. We also show that the perfect matching function can be computed by polynomial size (non-monotone) span programs over arbitrary fields. Received: August 1, 1996     

Non-Expansive Hashing

non-expansive hashing scheme, similar inputs are stored in memory locations which are close. We develop a non-expansive hashing scheme wherein any set of size from a large universe may be stored in a memory of size (any , and ), and where retrieval takes operations. We explain how to use non-expansive hashing schemes for efficient storage and retrieval of noisy data. A dynamic version of this hashing scheme is presented as well. Received: February 5, 1996     

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

d , and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v'. The tester should determine with high probability whether the graph is bipartite or ε-far from bipartite for any given distance parameter ε. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant ε), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis. Received: February 6, 1998     

On Large Systems of Sets with No Large Weak Δ-subsystems

weak Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by R?dl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of without weak Δ-systems of size 3 with . Received: October 1, 1997     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

Testing Monotonicity

at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions. Received March 29, 1999     

NOTE The Johnson Graphs Satisfy a Distance Extension Property

G has property if whenever F and H are connected graphs with and |H|=|F|+1, and and are isometric embeddings, then there is an isometric embedding such that . It is easy to construct an infinite graph with for all k, and holds in almost all finite graphs. Prior to this work, it was not known whether there exist any finite graphs with . We show that the Johnson graphs J(n,3) satisfy whenever , and that J(6,3) is the smallest graph satisfying . We also construct finite graphs satisfying and local versions of the extension axioms studied in connection with the Rado universal graph. Received June 9, 1998     

Algorithms for Measuring Perturbability in Matroid Optimization

perturbability function of a matroid measures the maximum increase in the weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matroids in which independence can be tested in strongly polynomial time. Furthermore, for the case of transversal matroids we are able to take advantage of their special structure to design a faster algorithm for computing the perturbability function. Received: June 13, 1997     

On the Signed Domination in Graphs

G on n vertices with minimum degree r, there exists a two-coloring of the vertices of G with colors +1 and -1, such that the closed neighborhood of each vertex contains more +1's than -1's, and altogether the number of 1's does not exceed the number of -1's by more than . As a construction by Füredi and Mubayi shows, this is asymptotically tight. The proof uses the partial coloring method from combinatorial discrepancy theory. Received May 12, 1998     

Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs

Dedicated to the memory of Paul Erdős We construct a system of subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994). Received January 15, 1996/Revised August 2, 1999     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 1998     

The Size of 3-Cross-Free Families

We give a short and simple proof for the theorem that the size of a 3-cross-free family is linear in the size of the groundset. A family is 3-cross-free if it has no 3 pairwise crossing members. Received July 1, 1998 RID="*" ID="*" Research supported by the Netherlands Organization for Scientific Research (NWO) and the OTKA T 029772 project.     

Edge-Coloring Bipartite Multigraphs in O(E logD) Time

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E logD time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time. Received September 23, 1999     

On the Existence of Disjoint Cycles in a Graph

G is a graph of order at least 3k with . Then G contains k vertex-disjoint cycles. Received: April 23, 1998     

NOTE Spectral Characterization of Tree-Width-Two Graphs

) of a graph G, similar in spirit to his now-classical invariant . He showed that is minor-monotone and is related to the tree-width la(G) of G: and, moreover, , i.e. G is a forest. We show that and give the corresponding forbidden-minor and ear-decomposition characterizations. Received October 9, 1997/Revised July 27, 1999