User will traves - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:55:48Z http://mathoverflow.net/feeds/user/27011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity/108882#108882 Answer by Will Traves for graphs with independence number = Shannon capacity Will Traves 2012-10-05T02:15:41Z 2012-10-05T02:15:41Z <p>@Tobias: Sorry that my answer was not clear. According to Plummer <a href="http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf" rel="nofollow">http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf</a> there are two equivalent definitions of well-covered graphs, one in terms of vertex covers and one in terms of independent sets. </p> <p>A set of vertices $S$ is called a vertex cover if every vertex is either in $S$ or is adjacent to a vertex in $S$. The set $S$ is a minimum vertex cover if it is a vertex cover and no proper subset is a vertex cover. A set of vertices $T$ is called an independent set if no two vertices in $T$ are connected by an edge of the graph. A maximal independent set is one in which each vertex outside of $T$ is adjacent to some vertex in $T$. Note that if $V$ is the set of all vertices in the graph then $T$ is a maximal independent set if and only if $V \setminus T$ is a minimum vertex cover. </p> <p>A graph is well-covered if all maximal independent sets have the same cardinality. Equivalently, a graph is well-covered if all minimum vertex covers have the same cardinality.</p> <p>Of course, if $\bar{G}$ is the complementary graph to $G$ then a set of vertices forms a maximal clique in $\bar{G}$ precisely when the same set of vertices forms an independent set in $G$. So your condition that the "complements satisfy the additional property that all maximal cliques have the same size" means that the graphs themselves are well-covered. I don't see need for the additional requirement that every edge appears in some maximal clique - it seems to me that this always occurs. </p> <p>You might find the paper by Philip Matchett helpful. It's emphasis is slightly different but it deals with operations on well-covered graphs. It can be found here: <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45" rel="nofollow">http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45</a>. </p> http://mathoverflow.net/questions/108855/max-noethers-afbg-theorem Max Noether's AF+BG theorem Will Traves 2012-10-04T20:01:15Z 2012-10-05T00:33:01Z <p>I'm looking for an example of the following situation, related to Max Noether's AF+BG Theorem (see Bill Fulton's book on algebraic curves, page 61, at <a href="http://www.math.lsa.umich.edu/~wfulton/CurveBook.pdf" rel="nofollow">http://www.math.lsa.umich.edu/~wfulton/CurveBook.pdf</a>). </p> <p>Fulton motivates the AF+BG Theorem by saying that if $F, G, H$ are curves in the projective plane with no common components then we could have the inequality of cycles $H \cdot F \geq G \cdot F$ and we might be interested in knowing when there is a curve $B$ so that $H \cdot F = B \cdot F + G \cdot F$. To produce such a curve it is enough to find forms $A$ and $B$ so that $H = AF+BG$ (here I'm using the same letter to denote a curve and its defining form) since then $H \cdot F = BG \cdot F = B \cdot F + G \cdot F$. </p> <p>Noether's fundamental theorem (the $AF+BG$ theorem) says that the condition $H = AF + BG$ is equivalent to the local conditions that say that for each $P \in F \cap G$, we have $H \in (F,G)\mathcal{O}_P(\mathbb{P}^2)$. Many uses of the theorem rely on being in a situation where the local conditions are obviously met and so we obtain the global fact $H = AF + BG$ and hence $H \cdot F = B \cdot F + G \cdot F$. </p> <p>My question is to find an example where the local conditions are NOT met but we still have $H \cdot F = B \cdot F + G \cdot F$. If this is impossible, please explain. </p> http://mathoverflow.net/questions/108851/graphs-with-independence-number-shannon-capacity/108857#108857 Answer by Will Traves for graphs with independence number = Shannon capacity Will Traves 2012-10-04T20:25:00Z 2012-10-04T20:25:00Z <p>I believe that graphs in which all maximal cliques have the same size and every edge is contained in a maximal clique are called well-covered graphs. Sorry that I can't shed light on any of the serious questions that you raise. </p> http://mathoverflow.net/questions/109334/which-homogeneous-polynomials-split-into-linear-factors/109337#109337 Comment by Will Traves Will Traves 2012-10-11T15:26:56Z 2012-10-11T15:26:56Z @Fernando: Can't we view the set of completely reducible homogeneous polynomials of degree n in d variables as the image of the multiplication map sending (P(S1))n to P(Sn), where S=C[x0,…,xd−1]? The image of this morphism should be a projective subvariety of P(Sn), in particular it is a Zariski-closed set. The affine cone over this subvariety gives the affine variety that Jeurgen described.