共查询到20条相似文献,搜索用时 62 毫秒
1.
Noga Alon 《Graphs and Combinatorics》1986,2(1):95-100
Forn ≥ r ≥ 1, letf r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf 2(n) =n ? 1. Here we observe thatf 3(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc 1(r) andc 2(r) such thatc 1(r) ≤f r (n)?n ?[r/2] ≤n 2(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra. 相似文献
2.
It is known that for all monotone functions f : {0, 1}n → {0, 1}, if x ∈ {0, 1}n is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability ? = n?α, then P[f(x) ≠ f(y)] < cn?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying P[fn(x) ≠ fn(y)] ≥ δ, where 0 < δ < 1/2, required ? ≥ c(δ)n?α, where α = 1 ? ln 2/ln 3 = 0.36907 …, and c(δ) > 0. We improve this result by achieving for every 0 < δ < 1/2, P[fn(x) ≠ fn(y)] ≥ δ, with:
- ? = c(δ)n?α for any α < 1/2, using the recursive majority function with arity k = k(α);
- ? = c(δ)n?1/2logtn for t = log2 = .3257 …, using an explicit recursive majority function with increasing arities; and
- ? = c(δ)n?1/2, nonconstructively, following a probabilistic CNF construction due to Talagrand.
3.
András Pluhár 《Random Structures and Algorithms》2009,35(2):216-221
We give a very short proof of an Erd?s conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2n, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
4.
Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let tr (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t5(n) ≤ t6(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t4(n) = 3(n ? 1) for n ≥ 3. 相似文献
5.
Edward A. Bender E. Rodney Canfield Brendan D. McKay 《Random Structures and Algorithms》1990,1(2):127-169
Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions wk ? 1. a(x) and φ(x) such that c(n, q) ? wk(qN)enφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (Nq) exp(–ne?2q/n). on the other hand, if k = o(n1/2), this formula simplifies to c(n, n + k) ? 1/2 wk (3/π)1/2 (e/12k)k/2nn?(3k?1)/2. 相似文献
6.
For a coinmutative senugoup (S, +, *) with involution and a function f : S → [0, ∞), the set S(f) of those p ≥ 0 such that fP is a positive definite function on S is a closed subsemigroup of [0, ∞) containing 0. For S = (IR, +, x* = -x) it may happen that S(f) = { kd : k ∈ N0 } for some d > 0, and it may happen that S(f) = {0} ? [d, ∞) for some d > O. If α > 2 and if S = (?, +, n* = -n) and f(n) = e?[n]α or S = (IN0, +, n* = n) and f(n) = enα, then S(f) ∪ (0, c) = ? and [d, ∞) ? S(f) for some d ≥; c > 0. Although (with c maximal and d minimal) we have not been able to show c = d in all cases, this equality does hold if S = ? and α ≥ 3.4. In the last section we give sinipler proofs of previously known results concerning the positive definiteness of x → e?||x||α on normed spaces. 相似文献
7.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n). 相似文献
8.
Let f : 2N → + be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : ΣiεNfA(i) ≥ kfA(N),?A ? N} where fA(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(nlog log n), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
9.
Let (Mr)r∈?0 be a logarithmically convex sequence of positive numbers which verifies M0 = 1 as well as Mr ≥ 1 for every r ∈ ? and defines a non quasi - analytic class. Let moreover F be a closed proper subset of ?n. Then for every function f on ?n belonging to the non quasi - analytic (Mr)-class of Beurling type, there is an element g of the same class which is analytic on ?,n F and such that Dαf(x) = Dαg(x) for every α ∈ ?n0 and x ∈ F. 相似文献
10.
J. Hu 《Transformation Groups》2010,15(2):333-370
Let V be a 2m-dimensional symplectic vector space over an algebraically closed field K. Let $ \mathfrak{B}_n^{(f)} Let V be a 2m-dimensional symplectic vector space over an algebraically closed field K. Let
\mathfrakBn(f) \mathfrak{B}_n^{(f)} be the two-sided ideal of the Brauer algebra
\mathfrakBn( - 2m ) {\mathfrak{B}_n}\left( { - 2m} \right) over K generated by e
1
e
3⋯
e
2f-1 where 0 ≤ f ≤ [n/2]. Let HTf ?n \mathcal{H}\mathcal{T}_f^{ \otimes n} be the subspace of partial-harmonic tensors of valence f in V
⊗n
. In this paper we prove that dimHTf ?n \mathcal{H}\mathcal{T}_f^{ \otimes n} and dim
\textEn\textdK\textSp(V)( V ?n \mathord