Abstract. Suppose a committee consisting of three members is tasked with matching [Formula: see text] candidates to [Formula: see text] different positions. However, all of the committee members disagree on the job placement for every candidate, i.e., every candidate is matched to three different positions according to three committee members. All three committee members are competitive and want to push through as many of their placements as possible. Can they find a compromise which allows each committee member to be responsible for a third of all the candidate placements? In this paper we will consider an asymptotic version of this question and several other variants of a similar problem. As an application we will consider an embedding question—which hypertrees does a large Steiner system always contain?

We show that 3-uniform hypergraphs with the property that all vertices have a quasirandom link graph with density bigger than 1/3 contain a clique on five vertices. This result is asymptotically best possible.

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and $k\in o(\sqrt{m})$. Furthermore our algorithm solves the corresponding #CSP-SAT and Max-CSP-SAT of these CSPs. We also show that CNF representations of unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation.

We prove that any Steiner triple system $\mathcal{S}$, with $n = v(\mathcal{S})$ sufficiently large, admits a packing by almost spanning paths that covers almost all edges. More formally, for any $\mu > 0$, we obtain a family of $(1-\mu)n/3$ pairwise edge-disjoint paths, with $(1-\mu)n$ vertices each, all contained in $\mathcal{S}$.

We investigate the smallest possible minimum degree of $r$-color minimal Ramsey graphs for the $k$-clique. In particular, we obtain a bound of the form $O(k^2\log^2 k\big)$, which is tight up to a $(\log^2 k)$-factor whenever the number $r\geq2$ of colors is fixed. This extends the work of Burr, Erdös, and Lovász, who determined this extremal value for two colors and any clique size, and complements that of Fox, Grinshpun, Liebenau, Person, and Szabó, who gave essentially tight bounds when the order $k$ of the clique is fixed. As a side product our result also yields an improved upper bound on the vertex Folkman number $F(r,k, k+1)$ of the $k$-clique. The proof relies on a reformulation of the corresponding extremal function by Fox et al. and combines and refines methods used by Dudek, Eaton, and Rödl.

A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with $s_1$, $s_2\in S$ and $s_1\leq s_2$ are distinct. Let constants $\alpha>0$ and $0<\delta<1$ be fixed, and let $p_m=\min\{1,\alpha m^{-1+\delta}\}$ for all positive integers $m$. Generate a random set $R\subset {\mathbb N}$ by adding $m$ to $R$ with probability $p_m$, independently for each $m$. We investigate how dense a Sidon set $S$ contained in $R$ can be. Our results show that the answer is qualitatively very different in at least three ranges of $\delta$. We prove quite accurate results for the range $0<\delta\leq2/3$, but only obtain partial results for the range $2/3<\delta\leq1$.

Szemerédi's Regularity Lemma [22, 23] is a powerful tool in graph theory. It asserts that all large graphs G admit a bounded partition of E(G), most classes of which are bipartite subgraphs with uniformly distributed edges. The original proof of this result was non-constructive. A constructive proof was given by Alon, Duke, Lefmann, Rödl and Yuster [1], which allows one to efficiently construct a regular partition for any large graph. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl [3] gave one such extension to 3-uniform hypergraphs, and Rödl and Skokan [19] extended this result to k-uniform hypergraphs. W.T. Gowers [4, 5] gave another such extension. Similarly to the graph case, all of these proofs are non-constructive. We present an efficient algorithmic version of the Hypergraph Regularity Lemma for k-uniform hypergraphs.

In this paper we consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer $q$. Given a family $\mathscr{F}$ of $q$-multigraphs, define $ex(n,\mathscr{F})$ to be the maximum number of edges (counting multiplicities) that a $q$-multigraph on $n$ vertices can have without containing a copy of any $F \in \mathscr{F}$ (not necessarily induced). It is well known that $\tau(\mathscr{F}) = \lim_{n \to \infty} ex(n,\mathscr{F})/\binom{n}{2}$ exists for every family $\mathscr{F}$ (finite or infinite). Let $\mathscr{T} = \{\tau(\mathscr{F}) : \mathscr{F} \textrm{ is a family of $q$-multigraphs}\}$. We say the number $\alpha$, $0 \leq \alpha < q$, is a jump for $q$ if there exists a constant $c = c(\alpha,q)$ such that if $\alpha' \in \mathscr{T}$ such that $\alpha' > \alpha$, then $\alpha' \geq \alpha + c$. The Erdös--Stone theorem implies that for $q=1$, every $\alpha \in [0,1)$ is a jump. The problem of determining the set of jumps for $q \geq 2$ appears to be much harder. In a sequence of papers by Erdös, Brown, and Simonovits and, separately, Sidorenko, the authors established that every $\alpha$ is a jump for $q=2$, leaving the question of whether the same is true for $q \geq 3$ unresolved. A later result of Rödl and Sidorenko [V. Rödl and A. Sidorenko, J. Combin. Theory Ser. A, 69 (1995), pp. 347--357] gave a negative answer establishing that for $q \geq 4$ some values of $\alpha$ are not jumps. The problem of whether or not every $\alpha \in [0,3)$ is a jump for $q=3$ has remained open. We give a partial positive result in this paper proving that every $\alpha \in [0,2)$ is a jump for all $q \geq 3$. Additionally, we extend the results of Rödl and Sidorenko by showing, given any rational number $r$ with $0

The Frieze–Kannan regularity lemma is a powerful tool in combinatorics. It has also found applications in the design of approximation algorithms and recently in the design of fast combinatorial algorithms for boolean matrix multiplication. The algorithmic applications of this lemma require one to efficiently construct a partition satisfying the conditions of the lemma. R. Williams recently asked if one can construct a partition satisfying the conditions of the Frieze–Kannan regularity lemma in deterministic subcubic time. We resolve this problem by designing an $\tilde O(n^{\omega})$ time algorithm for constructing such a partition, where $\omega < 2.376$ is the exponent of fast matrix multiplication. The algorithm relies on a spectral characterization of vertex partitions satisfying the properties of the Frieze–Kannan regularity lemma.

We prove that asymptotically (as $n\to\infty$) almost all graphs with n vertices and $C_dn^{2-\frac{1}{2d}} \log^{\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

A set A of non-negative integers is called a Sidon set if all the sums a1 + a2, with a1 ≤ a2 and a1, a2 ∊ A, are distinct. One of the best studied problems on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of [n] = {0, 1, …, n − 1}. Thanks to results of Chowla, Erdős and Turán from the 1940s, it is known that F(n) = (1 + o(1))√n. In this paper we study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ [n] by a sparse, random subset R of [n], and ask how large a subset S ⊂ R can be, if we require that S should be a Sidon set. Let R = [n]m be a random subset of [n] of cardinality m = m(n), with all the subsets of [n] equiprobable. We investigate the random variable F([n]m) = max |S|, where the maximum is taken over all Sidon subsets S ⊂ [n]m, and obtain quite precise information on F([n]m) for the whole range of m. An abridged version of our results states as follows. Let 0 < a < 1 be a fixed constant and suppose m = m(n) = (1 + o(1))na. We show that there is a constant b = b(a) such that, almost surely, we have F([n]m) = nb+o(1). As it turns out, the function b = b(a) is a continuous, piecewise linear function of a that is non-differentiable at two points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function b = b(a) is constant.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”

Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. Their concepts of quasi-randomness match the notion of ∊-regularity from the earlier Szemerédi regularity lemma. In contrast, there exists no “natural” hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors. We study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rödl, Gowers and Haxell, Nagle and Rödl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl–Rödl (a special case thereof) and Gowers as corollaries. As a further corollary, we obtain that the special case of the Frankl–Rödl lemma (which we can make algorithmic) admits a corresponding counting lemma. (This corollary follows by the equivalences and that the regularity lemma of Gowers or that of Haxell et al. admits a counting lemma.)

Extending the Szemerédi regularity lemma for graphs, P. Frankl and V. Rödl [Random Structures Algorithms, 20 (2002), pp. 131–164] established a 3-graph regularity lemma triple systems ${\cal G}_n$ admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion counting lemma [B. Nagle and V. Rödl, Random Structures Algorithms, 23 (2003), pp. 264–332] allowing one to find and enumerate subhypergraphs of a given isomorphism type in a “dense and regular” environment created by the 3-graph regularity lemma. Combined applications of these lemmas are known as the 3-graph regularity method. In this paper, we provide an algorithmic version of the 3-graph regularity lemma which, as we show, is compatible with a counting lemma. We also discuss some applications.

A graph G is r-Ramsey-minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. In this paper we show that for any integer $k \geq 3$ and $r \geq 2$, there exists a constant $c>1$ such that for large enough n, there exist at least $c^{n^2}$ nonisomorphic graphs on at most n vertices, each of which is r-Ramsey-minimal with respect to the complete graph $K_k$. Furthermore, in the case $r=2$, we give an asymmetric version of the above result.

Property testers are efficient, randomized algorithms which recognize if an input graph (or other combinatorial structure) satisfies a given property or if it is "far" from exhibiting it.Generalizing several earlier results, Alon and Shapira showed thathereditary graph properties are testable (with one-sided error). In this paper we prove the analogous result for hypergraphs.This result is an immediate consequence of a (hyper)graph theoretic statement, which is an extension of the so-called removal lemma. The proof of this generalization relies on the regularity method for hypergraphs.

Recently Alon and Shapira [Every monotone graph property is testable, New York, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, ACM Press, 2005, pp. 128–137] have established that every monotone graph property is testable. They raised the question whether their results can be extended to hypergraphs. The aim of this paper is to address this problem. Based on the recent regularity lemma of Rödl and Schacht [Regular partitions of hypergraphs, Combin. Probab. Comput., to appear], we prove that any monotone property of 3‐uniform hypergraphs is testable answering in part the question of Alon and Shapira. Our approach is similar to the one developed by Alon and Shapira for graphs. We believe that based on the general version of the hypergraph regularity lemma the proof presented in this article extends to k‐uniform hypergraphs.

We investigate the threshold probability for the property that every r-coloring of the edges of a random binomial k-uniform hypergraph ${\mathbb G }^{(k)}(n,p)$ yields a monochromatic copy of some fixed hypergraph G. In this paper we solve the problem for arbitrary $k\geq 3$ and k-partite, k-uniform hypergraphs G.

Extending the Szemeredi Regularity Lemma for graphs, P. Frank and Rodl [2002] stablished a 3-graph Regularity Lemma guaranteeing that all large triple systems admit partitions of their edge sets into constantly many classes where most classes consist of regularly distributed edges. Many applications of this lemma require a companion Counting Lemma [Nagle and Rodl, 2003] allowing one to estimate the number of copies of K/sub k//sup 3/ in a "dense and regular" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. For general k-uniform hypergraphs, Regularity and Counting Lemmas were recently established by Gowers [2005] and by Nagle et al., [2005]. We believe the arguments here provide a basis toward a general algorithmic hypergraph regularity method.

We present a deterministic algorithm ${\cal A}$ that, in O(m 2 ) time, verifies whether a given m by m bipartite graph G is regular, in the sense of Szemerédi [Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes (Orsay, 1976), Colloques Internationaux CNRS 260, CNRS, Paris, 1978, pp. 399-401]. In the case in which G is not regular enough, our algorithm outputs a witness to this irregularity. Algorithm ${\cal A}$ may be used as a subroutine in an algorithm that finds an $\varepsilon$-regular partition of a given n-vertex graph $\Gamma$ in time O(n 2 ). This time complexity is optimal, up to a constant factor, and improves upon the bound O(M(n)), proved by Alon et al. [The algorithmic aspects of the regularity lemma, J. Algorithms, 16 (1994), pp. 80-109], where M(n)=O(n 2.376 ) is the time required to square a 0--1 matrix over the integers. Our approach is elementary, except that it makes use of linear-sized expanders to accomplish a suitable form of deterministic sampling.

A bipartite graph G = (U,V;E) is called $\epsilon$-regular if the edge density of every sufficiently large induced subgraph differs from the edge density of G by no more than $\epsilon$. If, in addition, the degree of each vertex in G is between $(d-\epsilon)n$ and $(d+\epsilon)n$, where d is the edge density of G and |U|=|V|=n, then G is called super $(d,\epsilon)$-regular. In [Combinatorica, 19 (1999), pp. 437--452] it was shown that if $S \subset U$ and $T \subset V$ are subsets of vertices in a super-regular bipartite graph G = (U,V;E), and if a perfect matching M of G is chosen randomly, then the number of edges of M that go between the sets S and T is roughly |S||T|/n. In this paper, we derandomize this result using the Erdos--Selfridge method of conditional probabilities. As an application, we give an alternative constructive proof of the blow-up lemma of $\komlos$, $\sarkozy$, and $\szemeredi$ (see [Combinatorica, 17 (1997), pp. 109--123] and [Random Structures Algorithms, 12 (1998), pp. 297--312]).

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].

In this paper, we will consider the problem of designing an efficient algorithm that finds an $\epsilon$-regular partition of an l-uniform hypergraph.

A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking function was obtained in [S. Poljak, V. Rödl, and J. Spencer, SIAM J. Discrete Math., (1) 1988, pp. 372--376]. We consider the weighted versions of both problems. Our method yields a polynomial time heuristic with guaranteed lower bound for the linear ordering problem.

We investigate two methods for proving lower bounds on the size of small-depth circuits, namely the approaches based on multiparty communication games and algebraic characterizations extending the concepts of the tensor rank and rigidity of matrices. Our methods are combinatorial, but we think that our main contribution concerns the algebraic concepts used in this area (tensor ranks and rigidity). Our main results are following. (i) An $o(n)$-bit protocol for a communication game for computing shifts, which also gives an upper bound of $o(n^2)$ on the contact rank of the tensor of multiplication of polynomials; this disproves some earlier conjectures. A related probabilistic construction gives an $o(n)$ upper bound for computing all permutations and an $O(n\log\log n)$ upper bound on the communication complexity of pointer jumping with permutations. (ii) A lower bound on certain restricted circuits of depth 2 which are related to the problem of proving a superlinear lower bound on the size of logarithmic-depth circuits; this bound has interpretations both as a lower bound on the rigidity of the tensor of multiplication of polynomials and as a lower bound on the communication needed to compute the shift function in a restricted model. (iii) An upper bound on Boolean circuits of depth 2 for computing shifts and, more generally, all permutations; this shows that such circuits are more efficient than the model based on sending bits along vertex-disjoint paths.

In this paper we give an algorithm which, given a labeled graph on n vertices and a list of all labeled graphs on k vertices, provides for each graph H of this list an approximation to the number of induced copies of H in G with total error small. This algorithm has running time $O(n^{1/ \log \log n} \cdot M(n))$, where $M(n)$ is the time needed to square an n by n matrix with 0, 1-entries over the integers. The main tool in designing this algorithm is a variant of the regularity lemma of Szemerédi.

Article Free Access Share on Modified ranks of tensors and the size of circuits Authors: P. Pudlák View Profile , V. Rödl View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 523–531https://doi.org/10.1145/167088.167228Published:01 June 1993Publication History 16citation338DownloadsMetricsTotal Citations16Total Downloads338Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC/sup 1/.>

It is shown that for any graph G on n vertices, there is a number N (of order at most $n^3 (\log n)^2 $) and a graph H on N vertices such that for any ordering of the vertices of G and any ordering of the vertices of H, there is an order-isomorphism from G into H.

An $O( n^3 \log n )$ algorithm is presented that, for a given tournament on n vertices, produces a ranking with fit at least $\frac{1}{2} \begin{pmatrix} n \\ 2 \end{pmatrix} + c_1 n^{3/ 2} $, where $c_1 = \frac{1}{8}\pi ^{ - 1 / 2} $.

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

Let d = d(n) be the minimum d such that for every sequence of n subsets F1, F2, . . . , Fn of {1, 2, . . . , n} there exist n points P1, P2, . . . , Pn and n hyperplanes H1, H2 .... , Hn in Rd such that Pj lies in the positive side of Hi iff j ∈ Fi. Then n/32 ≤ d(n) ≤ (1/2 + 0(1)) · n. This implies that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. The proof of (1) combines some known geometric facts with certain probabilistic arguments and a theorem of Milnor from real algebraic geometry.