User talk:Farshadcontribs
Hypergraph Packing
A packing P is a subset of edges of hypergraph H in which there is no pair of distinct edges with a common vertex.
(D_0,\epsilon)-good hypergraph
A hypergraph H is (D_0,\epsilon)-good if there exists D\D0 such that
~Ax,y in V D(1-e)<=deg(x)<=D(1+e)
codeg(x,y)<eD
Joel Spencer addresses the problem of asymptotic hypergraph packing through a branching process. He introduced a random greedy algorithm which almost always achieves an asymptotically optimal packing of disjoint hyperegdes from a hypegraph H.
Problem: It has been shown that for a (Q+1)-uniform hypergraph under the following two assumptions
* All vertices have the degre of D(1+o(1)) in which D tends to infinity. * For every pair of vertices shares only o(D) common edges.
There exists a packing P of size at least [n/(Q+1)](1-o(1)) where n is the total number of vertices.
This claim was originally made by N. Pippenger [z] and was proved by Joel Spencer. He also provides a random greedy algorithm to achieve this goal.
Start a discussion with Farshadcontribs
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. Start a new discussion to connect and collaborate with Farshadcontribs. What you say here will be public for others to see.
