|
|
| Author |
Message |
server
science forum beginner
Joined: 24 Mar 2005
Posts: 26
|
 Posted: Tue Jul 05, 2005 9:32 pm Post subject:
graph theory
|
|
|
|
message unavailable |
|
| Back to top |
|
 |
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
Well, yeah, actually a "trivial" lower bound can be derived easily.
Consider all k-sets of [1..n], we have totally
{n choose k} such sets.
and each coloring is going to color at most
(n/k)^k
of them. Therefore another lower bound should be
{n choose k}/(n/k)^k
with stirling's approximation, we can easily get a lower bound of
e^k, when n/k is large enough.
Nice day. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
fhzhang@gmail.com wrote:
| Quote: | I tried some simple cases, your result seems correct.
I really appreciate your help. Nice weekend.
|
This problem looks like it's going to be a difficult one in general.
I did some reading through the literature earlier today (Monday), and I
found some papers related to the problem, which evidently goes by the
name of Perfect Hashing. (Colorings which color all the vertices in a
set of size k with different colors are sometimes called "Anti-Ramsey
Colorings." You may also want to search for related papers on this
subject.)
Some of the titles are incomplete, but once you find the appropriate
journal, you'll see what the rest of them are.
(1) M. Fredman, J. Komlos, "On the size of separating ...", SIAM
Journal of Algebraic and Discrete Methods 5 (1984), 61-68.
(2) J. Korner, K. Marton, "New bounds ...", European Journal of
Combinatorics 9 (1988), 523-530.
(3) J. Korner, G. Simonyi, "Trifference", Studia Sci. Math Hungar 30
(1995), 95ff.
(4) S. Blackburn, "Perfect Hash Families ...", Journal of Combinatorial
Theory Series A 92 (2000), #1, 54-60.
(5) D. Deng, D. Stinson, R. Wei, "Lovasz's local lemma ...", Designs,
Codes, and Cryptography 32 (2004), #1-3, 121-134.
Unfortunately, (3) and (5) weren't in the ASU library. Paper (4) gives
the best bounds, as well as some constructions, and (2) is also worth
checking into.
--- Christopher Heckman |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
That's what I was thinking too. This problem seems well-defined and
should have been studied.
Write to you later.
Fenghui |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
fhzh...@gmail.com wrote:
| Quote: | Great, thank you very much Mr. Heckman.
I will look into your proof carefully. Can I write to you
later?
|
Yes. My "professional" e-mail address is checkman@math.usa.edu.
(Actually, you need to reverse the orders of the letters in USA; this
is to throw off spambots.)
I can't shake the feeling that someone has answered this problem
before, though, and written a paper about it.
--- Christopher Heckman |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
I tried some simple cases, your result seems correct.
I really appreciate your help. Nice weekend. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: Combinatorics question.
|
|
|
Binesh Bannerjee wrote:
| Quote: |
But, say I wanted the number of ways to pick _3_ items
from there?
How would I get that number, with 2A's, 3B's and 4C's?
(Or more basically, for a group consisting of any number
of items, with any number of those items possibly repeated,
how do I find the number of ways of picking n items, with
order being significant.)
I can see that AABBBCCCC empirically can have 26 possible
ways of picking 3 items. I can see that's because it's
3^3-1, with the -1 being the possibility of picking 3
A's... But, I'm not sure how to genericize the calculation,
which is what I'm after. (for instance, it's less easy for
me to see how to calculate that to pick _4_ items from
there, would have 71 possible ways, even tho, I can
enumerate those...)
|
Cross-posted to alt.sci.math.combinatorics ...
(I thought I had an answer, but I realized it doesn't work.)
--- Christopher Heckman |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
Sorry I made a mistake,
ln(n/(k-1))/ln(k/(k-1))=(ln(n)-ln(k-1))/(ln(k)-ln(k-1))<ln(n)/ln(k)=log(n,k)
is not correct. But still when n=6,k=4, we have
ceil(ln(n/(k-1))/ln(k/(k-1)))=3
Three colorings are not enough do distinguish all 4-subsets of a 6-set. |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
Your analysis is fine, but I am afraid this lower bound is not tight.
Because
ln(n/(k-1))/ln(k/(k-1))=(ln(n)-ln(k-1))/(ln(k)-ln(k-1))<ln(n)/ln(k)=log(n,k)
seems a little bit too good.
Consider a simple case when n=6 and k=4, I don't think we can find two
colorings that will do the job.
Anyway your analysis is very helpful, I now know how to attach this
problem and where to find the knowledge I need.
I really appreciate your help. Nice weekend. |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
Great, thank you very much Mr. Heckman.
I will look into your proof carefully. Can I write to you later?
Fenghui |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: An interesting coloring problem, can anyone help?
|
|
|
Proginoskes wrote:
| Quote: | fhzh...@gmail.com wrote:
Sorry I didn't address the problem very clear. We
have only k colors available,
Oh, sure! I missed that ...
which means all coloring
schemes should have colored the set of elements into
exact k colors. In that case, only one scheme is not
enough.
It's similar to hashing in the sense of that in both
cases we want to find a group of maps(functions) from
[1..n] to [1..k].
I will go get a book on Hypergraph and read it.
There aren't any real restrictions on what elements can
be colored what colors, so hypergraphs may not be as
useful as I originally thought. Look up books on
combinatorics instead.
|
Actually, I think I've solved it, or at least found a non-trivial lower
bound on the number of colorings.
Here's all the background, for those who haven't read the complete
thread. (Or those who are reading alt.sci.math.combinatorics but not
sci.math.)
DEFINITION. A k-coloring [scheme] is a mapping C from {1,2,...,n} to
{1,2,...,k}.
DEFINITION. If A is a subset of {1,2,...,n} with |A| = k, then a
coloring C is perfect for A if the elements of A all receive different
colors; i.e.,
| {c(i) : i in A} | = k.
PROBLEM. Find a set D of k-colorings with minimum size, so that every
subset of {1,2,...n} with size k is perfect with respect to some
coloring in D.
And now for the lower bound ...
THEOREM. Let S = {1, 2, ..., n}, and let C_1, C_2, ..., C_c be
k-colorings of S. Then there is a subset T of S of size at least n *
((k-1)/k)^c such that ANY subset of T with k elements is not perfect
with respect to any of C_1, C_2, ..., C_c.
Proof. Induction on c. If c = 0, we can let T = S.
Now suppose that T_(c-1) is a subset of size n * ((k-1)/k)^(c-1) such
that any subset of T_(c-1) with k elements is not perfect with respect
to any of C_1, C-2, ..., or C_(c-1).
Now let U_i be the set of all j in T_(c-1) such that C_c(j) = i. Let
T_c be union of the (k-1) largest U_i's. This guarantees that T_c has
at least
(k-1)/k * | T_(c-1)| = n * ((k-1)/k)^c elements.
Any subset A of T_c which has k elements is not perfect with respect to
C_1, C_2, ..., C_(c-1), since A is a subset of T_c, which is a subset
of T_(c-1), and any subset of T_(c-1) with k elements is not perfect
with respect to C_1, C_2, ..., C_(c-1).
A can't be perfect with respect to C_c, because {C_c(j) : j is in A} is
a subset of {C_c(j) : j is in T_c}, and the latter has k-1 elements, by
construction.
This proves the theorem.
COROLLARY. If A is perfect with respect to C_1, C_2, ..., C_c, then
c >= ceiling (ln (n/(k-1)) / ln (k/(k-1))).
Proof. Let B be T_c, constructed as in the proof. If B contains at
least k elements, then some subset of B with k elements is not perfect
with respect to any of C_1, C_2, ..., C_c, contrary to assumption.
Hence
k-1 >= |B| >= n * ((k-1)/k)^c.
Solving for c finishes the proof.
I suspect the answer to your problem is the ceiling of
(ln (n/(k-1))) / (ln (k/(k-1))), or not too much above it. To construct
the colorings, follow the proof, and make the U_i's as close the same
size as each other as possible.
For instance, if k = 2 and n = 2^p, then the answer is p. (You can use
the binary expansions of 0 ... n-1 to get the colorings, as well.)
Here's an example with k = 2 and n = 7:
For coloring C1, break the set {1,2,3,4,5,6,7} into 2 sets of about the
same size: {1,2,3,4} and {5,6,7}, for instance. Make C1 color 1,2,3,4
with 1 and 5,6,7 with 2.
We now have the sets {1,2,3,4}, {5,6,7}. If x and y are both elements
of one of these sets, then C1(x) = C1(y); i.e., C1(5) = C1(6) = C1(7).
For coloring C2, break the set {1,2,3,4} (which are all colored 1) into
2 sets of about the same size: {1,3} and {2,4}, for instance. (Any
partition will do.) Make C2 color 1,3 with 1 and 2,4 with 2. You also
need to deal with {5,6,7}, which are all colored color 2 by C1; color
5,6 with 1, and 7 with 2, for instance.
coloring c(1) c(2) c(3) c(4) c(5) c(6) c(7)
C1 1 1 1 1 2 2 2
C2 1 2 1 2 1 1 2
Now, we have the sets {1,3}, {2,4}, {5,6}, and {7}. Note that C1(x) =
C1(y) and C2(x) = C2(y) for any x,y in {1,3}, or in {2,4}, or {5,6}, or
{7}.
The coloring C3 will make this last distinction. Divide {1,3} into 2
sets of about the same size, {1} and {3}, make C3 color everything in
{1} with 1, everything in {3} with 2; divide {2,4} into {2} and {4},
and make C3 color everything in {2} with 1, everything in {4} with 2,
and divide {5,6} into {5} and {6}, and make C3 color 5 with 1 and 6
with 2.
It doesn't matter how C3 colors 7. Now our colorings look like:
coloring c(1) c(2) c(3) c(4) c(5) c(6) c(7)
C1 1 1 1 1 2 2 2
C2 1 2 1 2 1 1 2
C3 1 1 2 2 1 2 x
Now we've found a set of 3 colorings with the property that for any
distinct x and y, there is a coloring C in {C1, C2, C3} such that |
{C(x), C(y)} | = 2 = k. Also, this set of colorings is minimal, since
ceiling (ln (7/(2-1)) / ln (2/(2-1))) = 3.
--- Christopher Heckman |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Jul 05, 2005 9:32 pm Post subject:
Re: graph theory
|
|
|
11.
sketch pf:
A well-known fact in graph theory is the theorem that the sum of the
degrees of the vertices of G is equal to twice the number of edges
(imagine adding the number of edges leaving each vertex. When all
vertices are accounted for, each edge has been counted twice). Then by
assumption the sum of the degrees of V(G) is greater than or equal to
3p, so p is less than or equal to 2*|E(G)|/3.
p<=2*(17)/3<=11.333...
p is an integer, so the maximum value for p is 11. |
|
| Back to top |
|
|
Woeginger Gerhard
science forum beginner
Joined: 30 Jul 2005
Posts: 5
|
| Posted: Tue Aug 16, 2005 8:30 am Post subject:
Re: Integer Optimization Problem P+p(j)/C+c(j)
|
|
|
unix68 <unix68@networld.at> wrote:
# Hi,
# I need help for solving the following problem (references to
# algorithms and papers).
#
# Given:
# P, p1,p2,...,pn all integers
# C, c1,c2,...,cn all integers
# P = constant
# C = constant
#
# Goal:
# maximize [P+sum(pj)]/[C+sum(cj)] for any j=1..n
#
# This means we have to find the optimal subset of elements
# out of a given set (1...n) such that the ratio
# [P+sum(pj)]/[C+sum(cj)] gets maximal.
In case all c1,...,cn are NON-NEGATIVE integers,
your problem is polynomially solvable. (There is
a direct solution via sorting, you do not even
need fractional programming.)
In case c1,...,cn are ARBITRARY integers,
your problem is NP-hard. (By a reduction from
subset sum.)
--Gerhard
___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |
|
| Back to top |
|
|
Matthew Roozee
science forum beginner
Joined: 22 Oct 2005
Posts: 7
|
| Posted: Sat Oct 22, 2005 5:56 pm Post subject:
Re: graph theory
|
|
|
amanda.pascoe@gmail.com wrote:
| Quote: | 11.
sketch pf:
A well-known fact in graph theory is the theorem that the sum of the
degrees of the vertices of G is equal to twice the number of edges
(imagine adding the number of edges leaving each vertex. When all
vertices are accounted for, each edge has been counted twice). Then by
assumption the sum of the degrees of V(G) is greater than or equal to
3p, so p is less than or equal to 2*|E(G)|/3.
p<=2*(17)/3<=11.333...
p is an integer, so the maximum value for p is 11.
|
This establishes the upper bound for p.
To complete the proof, all we have to show is that there exists a
solution for p = 11.
Start with an 11-gon (which uses 11 of our edges), and label the
vertices 0,...,10 in order. Ignoring the points 0,5,10 for a moment,
draw the edges that are equivalent mod 5... so 1 connects to 6, 2
connects to 7, etc. There are 4 of these so we have used 15 edges total
and each of these 8 vertices has degree 3. We then connect 0 to both 5
and 10 (17 edges total) to give 5 and 10 degree 3 and 0 degree 4.
- Matt |
|
| Back to top |
|
|
Richard Reddy
science forum beginner
Joined: 16 Nov 2005
Posts: 1
|
| Posted: Wed Nov 16, 2005 5:33 am Post subject:
Re: > Challenge
|
|
|
The statistics on child mortality for AIDS are fairly accurate, but the
"third world" depends on who you talk to. We have underdeveloped nations
in Africa, Asia and Latin America. Many developed nations also have
AIDS epidemics, including the USA. There is substantial margin for error in
the business of counting deaths for epidemics of all kinds. We also find
politics in official numbers, which are frequently wrong.
The issue of quality of life for people infected with AIDS is even
more tragic, given the high cost of drugs proven to be effective. The
poorest
nations are simply helpless in the face of this epidemic, lacking medical
infrastructure, public health education, or the ability to assist sick and
disabled people.
In my opinion, the age of AIDS victims is irrelevant. We should endeavor
to assist any nation or state unable to cope with this pandemic. It's the
human thing to do, whatever we think of particular statistics. The
suffering
is real and the AIDS epidemic is enormous. So too are millions of deaths
that might have been delayed by years or decades with appropriate medical
intervention.
I offer another challenge. Find a reputable organization and try to
be of help in some way. An organization can be in error with statistics,
but still be highly effective in delivering assistance, a process that
frequently
involves danger and hardship. There are many wonderful people stretched
out beyond reckoning in combating this global menace. You will find many
charities who hire "pros" to raise money, sometimes with questionable
tactics
or poor percentages reaching the intended recipients. By law, this
statistics
are public information.
Apathy is certainly a dangerous condition. I know little about this
organization,
but there are many putting their whole heart into the effort to fight this
epidemic.
If you want to hang your hat on some real statistical offenders, try the
antismoking crew. Prohibitionists love to exaggerate. For example, public
adds that say each cigarette shortens your life by 5 minutes.
<dsaklad@zurich.csail.mit.edu> wrote in message
news:1117871877.716280.18410@o13g2000cwo.googlegroups.com...
| Quote: | Path: grapevine.lcs.mit.edu!newsswitch.lcs.mit.edu!
bloom-beacon.mit.edu!newsfeed.stanford.edu!
postnews.google.com!news4.google.com!news.glorb.com!
sn-xit-04!sn-xit-12!sn-xit-01!sn-post-01!supernews.com!
corp.supernews.com!not-for-mail
From: "PaulKing" <aimulti at aimultimedia.com
Newsgroups: misc.health.aids
Subject: Challenge
Date: Fri, 03 Jun 2005 19:51:13 -0400
Organization: www.talkabouthealthnetwork.com
Message-ID: <431b337a0657600e87b4f777796371e2 at
localhost.talkabouthealthnetwork.com
X-Newsreader: www.talkabouthealthnetwork.com
X-Problems-To: info at talkaboutnetwork.com
X-Posted-By: USERID-7496
Content-Type: text/plain;
X-Complaints-To: abuse at supernews.com
Lines: 28
Xref: grapevine.lcs.mit.edu misc.health.aids:98998
CHALLENGE TO BELIEVERS
If anyone still believes 'AIDS' statistics, let them answer
just this one question.
The high budget apathykills.org TV commercial claims 25 million
children in the Third World have died of 'AIDS'.
The UN figures (see graph from them I posted above) says that
ONLY 3% of child mortalities in the Third World are from
'AIDS'.
If 3% = 25 million then 100% must = 832.5 million.
If nearly ONE BILLION children in the Third World have died
then how come the population growth is at an all time high.
ONE BILLION DEAD CHILDREN would almost mean every child in
Africa and India is dead.
Explain this and you can still believe 'AIDS' figures.
Fail to do so and you must admit 'AIDS' figures are TOTAL
GARBAGE.
|
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sun Nov 23, 2008 10:36 am | All times are GMT
|
|
Advertising | Mobile Phone | Loans | Debt Consolidation | Web Advertising
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
