User will traves - MathOverflow

Answer by Will Traves for graphs with independence number = Shannon capacity

2012-10-05T02:15:41Z

@Tobias: Sorry that my answer was not clear. According to Plummer http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf there are two equivalent definitions of well-covered graphs, one in terms of vertex covers and one in terms of independent sets.

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.

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.

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.

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: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45.

Max Noether's AF+BG theorem

2012-10-04T20:01:15Z

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 http://www.math.lsa.umich.edu/~wfulton/CurveBook.pdf).

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$.

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$.

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.

Answer by Will Traves for graphs with independence number = Shannon capacity

2012-10-04T20:25:00Z

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.

Comment by Will Traves

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.