3,255 reputation
11232
bio website
location sqrt(-1)
age
visits member for 4 years, 5 months
seen 7 hours ago

 
  two queens
 
 
    mathematics and death
    not cheerful not sad
    guide me through the land
    pat me on my head
 
    they live
    in my one man nation
    i follow them
    to my destination
 
 
wh,
(long ago)



  polynomials over finite Galois field
  spread so evenly across their finite affine space
  i wish for a network of friends
  to count on


wh,
1996-03-05/06



1d
comment On independent sets of graph
$\alpha(G)\ $ and $\ N(G)\ $ have to be balanced to get an objectively good inequality, however possibly not as good as you'd like it--it has to be seen.
1d
comment On independent sets of graph
Yes, as an upper bound. These are trivially equivalent (sorry to inertially waste time on my talking).
1d
comment On independent sets of graph
I think that only my accidental conclusion was wrong (a result of a mistaken thinking at that moment--my concentration gave up when I mixed the general definition and the peculiarities of my construction). Another equivalent formulation: $\ m:=M(G)\ $ is the largest integer such that there exists $\ W\subseteq V\ $ such that $\ |W|=\alpha(G)\cdot m\ $ and W is a union of $\ m\ $ maximal independent sets (i.e. od independent sets $\ J\subseteq V\ $ such that $\ |J|=\alpha(G)$).
1d
comment On independent sets of graph
I slightly and equivalently reformulated you definition of $\ M(G)\ $ ok. In my comment I got confused only about its conclusion. Of course, as you've written, $\ M(G)\le\frac n{\alpha(G)}$.
1d
comment On independent sets of graph
The last portion of the general part was wrong (the two preceding portions, and the small example, were fine).
1d
revised On independent sets of graph
The last traces of the error removed.
1d
comment On independent sets of graph
Thank you. But at least what I called my small EXAMPLE was fine, I was not confused at that stage.
1d
revised On independent sets of graph
An unfortunate Error removed.
1d
comment On independent sets of graph
Turbo, about def. of $\ M(G).\ $ Is $\ M(G)\ $ the maximal cardinality of a family of pairwise disjoint independent sets of cardinality $\ \alpha(G)\ $? -- so we would have $\ M(G)\ \le\ \binom n{\alpha(G)}\ $ (where $\ n\ $ is the number of vertices).
1d
revised On independent sets of graph
mth typo (x2)
2d
comment On independent sets of graph
Your notion $\ f(\alpha(G)\ N(G))\ :=\ \max(\alpha(G)\ N(G)),\ $ and similar functions $\ f(\alpha(G)\ N(G))\ $ introduce an interesting internal pressure to the graphs, and it should lead to a whole subtopic.
2d
comment On independent sets of graph
Perhaps. This and variations were on my mind, but I wanted to finish first step to answer properly on your question. Just to establish the $\ \LaTeX\ $ phrases was hard to me (I am slow). Now wider possibilities are open.
2d
comment On independent sets of graph
No yet, but there should be more fun ahead of us :-)
Jan
25
comment On independent sets of graph
This general (:-) example is done; it's time for a more dramatic one, hey!
Jan
25
revised On independent sets of graph
Corollary
Jan
25
revised On independent sets of graph
More complete (THEOREM)
Jan
25
revised On independent sets of graph
smoother
Jan
25
comment On independent sets of graph
I fixed $\ M(G)$--now it's perfect! (every k-subset is used). In particulat the small example got improved as the result.
Jan
25
revised On independent sets of graph
A typo in Remark 2.
Jan
25
revised On independent sets of graph
REMARK 0 added