84 research outputs found
Approximating the maximum consecutive subsums of a sequence
No full textWe present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ(n2) procedure. We show how to construct a (1+ε)-approximate index for all Parikh vectors of a binary string in O(nlog^2n/log(1+ε), for any constant ε>0.
Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time
Asymptotic multipartite version of the Alon–Yuster theorem
No full textIn this paper, we prove the asymptotic multipartite version of the Alon–Yuster theorem, which is a generalization of the Hajnal–Szemerédi theorem: If k≥3 is an integer, H is a k -colorable graph and γ>0 is fixed, then, for every sufficiently large n , where |V(H)| divides n, and for every balanced k-partite graph G on kn vertices with each of its corresponding View the MathML source bipartite subgraphs having minimum degree at least (k−1)n/k+γn, G has a subgraph consisting of kn/|V(H)| vertex-disjoint copies of H. The proof uses the Regularity method together with linear programming
A Common Extension of the Erdős–Stone Theorem and the Alon–Yuster Theorem for Unbounded Graphs
No full textAbstractThe Erdős–Stone theorem (1946, Bull. Am. Math. Soc., 52, 1089–1091) and the Alon–Yuster theorem (1992, Graphs Comb., 8, 95–102 ) are both very fundamental in extremal graph theory. We give a common extension of them, which states as follows: For everyϵ> 0 and r≥ 2, there exists c=cϵ, r> 0 such that, for any 0 ≤θ≤ 1, if H is a graph of order | H | ≤clogn and with chromatic number r then every n -vertex graph G with minimum degree at least ( 1 − 1 __ r−1 +θ ____ r(r−1)) n contains at least (θ−ϵ)n/| H | vertex-disjoint copies of H.When θ=ϵr (r− 1) or θ= 1, it would imply the two theorems.The important point is that our theorem enables us to deal with a larger graph H of order | H | →∞(as n→∞), while | H | was fixed in the Alon–Yuster theorem (and in another common extension by Komlós (2000, Combinatorica,20, 203–218)).The bounds clogn and ( 1 − 1 __ r−1 +θ ____r (r−1)) n are both essentially the best possible
Independent transversals in r-partite graphs
No full textAbstractLet G(r,n) denote the set of all r-partite graphs consisting of n vertices in each partite class. An independent transversal of G ∈ G(r,n) is an independent set consisting of exactly one vertex from each vertex class. Let Δ(r,n) be the maximal integer such that every G ∈ G(r,n) with maximal degree less than Δ(r,n) contains an independent transversal. Let Cr = limn→∞ Δ(r,n)/n. We establish the following upper and lower bounds on Cr, provided r > 2: 2⌊log r⌋−12⌊log r⌋−1⩾Cr⩾max{12e, 12⌈log(r3)⌉, 13 · 2⌈log r⌉−3}. For all r > 3, both upper and lower bounds improve upon previously known bounds of Bollobás, Erdős and Szemerédi. In particular, we obtain that C4 = 23, and that limr→∞ Cr ⩾ 1/(2e), where the last bound is a consequence of a lemma of Alon and Spencer. This solves two open problems of Bollobás, Erdős and Szemerédi
Two problems on cycles in random graphs
No full textWe prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Disproving a conjecture of R. Yuster [40], we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4. Second, write C(G) for the cycle space of a graph G, Cκ(G) for the subspace of C(G) spanned by the copies of Cκ in G, Tκ for the class of graphs satisfying Cκ(G) = C(G), and Qκ for the class of graphs each of whose edges lies in a Cκ. We prove that for every odd κ ≥ 3 and G = Gn,p, max p Pr(G ∈ Qκ Tκ) → 0; so the Cκ’s of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [12]. Third, we extend the seminal van den Berg–Kesten Inequality [9] on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding upper tail probabilities for event counts in a product probability space.Ph.D.Includes bibliographical referencesby Jacob D. Baro
Hardness and Algorithms for Rainbow Connectivity
No full textAn edge-colored graph is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connectivity} of a connected graph , denoted , is the smallest number of colors that are needed in order to make rainbow connected. In addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first proof that computing is NP-Hard. In fact, we prove that it is already NP-Complete to decide if , and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every , a connected graph with minimum degree at least has bounded rainbow connectivity, where the bound depends only on , and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented
Fractional decompositions of dense hypergraphs
No full textLet H0 be a fixed hypergraph. A fractional H0-decomposition of a hypergraph H is an assignment of nonnegative real weights to the copies of H0 in H such that for each edge e ∈ E(H), the sum of the weights of copies of H0 containing e is precisely one. Let k and r be positive integers with k> r> 2, and let Kr k denote the complete r-uniform hypergraph with k vertices. We prove that there exists a positive constant α = α(k, r) such that every r-uniform hypergraph with n (sufficiently large) vertices in which every (r − 1)-set is contained in at least n(1 − α) edges has a fractional Kr k-decomposition. Using our result together with a recent result of Rödl, Schacht, Siggers and Tokushige, we obtain the following corollary. For every r-uniform hypergraph H0, there exists a positive constant α = α(H0) such that every r-uniform hypergraph H in which every (r − 1)-set is contained in at least n(1 − α) edges has an H0-packing that covers |E(H)|(1 − on(1)) edges
Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
No full textRyser's Conjecture states that for any r-partite r-uniform hypergraph the vertex cover number is at most r−1 times the matching number. This conjecture is only known to be true for r≤3. For intersecting hypergraphs, Ryser's Conjecture reduces to saying that the edges of every r-partite intersecting hypergraph can be covered by r−1 vertices. This special case of the conjecture has only been proven for r≤5. \ud
\ud
It is interesting to study hypergraphs which are extremal in Ryser's Conjecture i.e, those hypergraphs for which the vertex cover number is exactly r−1 times the matching number. There are very few known constructions of such graphs. For large r the only known constructions come from projective planes and exist only when r−1 is a prime power. Mansour, Song and Yuster studied how few edges a hypergraph which is extremal for Ryser's Conjecture can have. They defined f(r) as the minimum integer so that there exist an r-partite intersecting hypergraph H with τ(H)=r−1 and with f(r) edges. They showed that f(3)=3,f(4)=6, f(5)=9, and 12≤f(6)≤15. \ud
\ud
In this paper we focus on the cases when r=6 and 7. We show that f(6)=13 improving previous bounds. We also show that f(7)≤22, giving the first known extremal hypergraphs for the r=7 case of Ryser's Conjecture. These results have been obtained independently by Aharoni, Barat, and Wanless
A Generalization of an Addition Theorem for Solvable Groups
No full textThe “sets” in this paper are actually multi-sets. That is, we allow an element to occur several times in a set and distinguish between the number of elements in a set and the number of distinct elements in the set. On the few occasions when we need to avoid repetition we will use the term “ordinary set.“Definition. Let G be a group and let S a set of elements of G. An r-sum in S is an ordered subset of S of cardinality r; the result of that r-sum is the product of its elements in the designated order.Definition. If S is a set, r(x, S) denotes the number of times x appears in S and [x, S] is a set consisting of r(x, S) copies of x. An n-set or n-subset is a set consisting of n elements. Hence [x, S] is an r(x, S)-subset of S.</jats:p
On the Maximum Number of Spanning Copies of an Orientation in a Tournament
No full textFor an orientation H with n vertices, let T(H) denote the maximum possible number of labelled copies of H in an n-vertex tournament. It is easily seen that T(H) ≥ n!/2e(H), as the latter is the expected number of such copies in a random tournament. For n odd, let R(H) denote the maximum possible number of labelled copies of H in an n-vertex regular tournament. In fact, Adler, Alon and Ross proved that for H=Cn, the directed Hamilton cycle, T(Cn) ≥ (e−o(1))n!/2n, and it was observed by Alon that already R(Cn) ≥ (e−o(1))n!/2n. Similar results hold for the directed Hamilton path Pn. In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results, and prove that they hold for a larger family of orientations H which includes all bounded-degree Eulerian orientations and all bounded-degree balanced orientations, as well as many others. One corollary of our method is that for any fixed k, every k-regular orientation H with n vertices satisfies T(H) ≥ (ek−o(1))n!/2e(H), and in fact, for n odd, R(H) ≥ (ek−o(1))n!/2e(H).</jats:p
- …
