Seminario di Vladimir Gurvich: n-GRAPHS, n-PERSON POSITIONAL GAMES, AND Delta-CONJECTURE
2013-05-23
Il Professor Vladimir Gurvich della Rutgers University (RUTCOR), terrà un seminario dal titolo: n-GRAPHS, n-PERSON POSITIONAL GAMES, AND Delta-CONJECTURE
An n-graph G = (V ;E_1;...;E_n) is de fined as the complete graph whose
edges are arbitrarily colored with n colors.
An n-graph is called complementary connected (CC) if for every i,
the complement G_i = (V;E_i) of the ith chromatic component of G is connected on V .
Delta is a 3-colored triangle; Pi is a 2-graph whose both chromatic components are P_4.
Pi and Delta are CC. We show that there are no others, but the trivial single-vertex graph.
Moreover, every CC n-graph distinct from the above three contains a vertex such that
after its deleting the remaining n-graph is still CC.
Based on these theorems, we construct a one-to-one correspondence between the Pi- and
Delta-free n-graphs and n-person positional games with perfect information and characterize
the normal forms of these games.
For n = 2 we obtain a characterization of the so-called read-once Boolean functions.
As another corollary, we obtain the so-called CIS (Cliques Intersect Stable sets) property
of Pi- and Delta-free n-graphs.
Characterizing the CIS n-graphs is a dicult problem already for n = 2. For example,
every 2-graph is a subgraph of a CIS 2-graph. We give more partial results in this direction.
Yet, whether might be a subgraph of a CIS n-graph?
Delta-conjecture (1978): asserts that NO.
It would suffice to prove Delta-conjecture for n = 3.
We also recall Tibor Gallai's (1967) decomposition of Delta-free graphs into 2-graphs.
Delta-conjecture, if true, would reduce characterizing CIS n-graphs to the case n = 2.
Related papers available online:
D. Andrade, E. Boros, and V. Gurvich, On graphs whose maximal cliques and stable
sets intersect, RUTCOR Research Report RRR-17-2006, Rutgers University.
V. Gurvich, Decomposing complete edge-chromatic graphs and hypergraphs; Revisited,
RUTCOR Research Report, RRR-29-2006, Rutgers University, Discrete Applied Math.,
157 (2009) 3069{3085.
V. Gurvich, On exact blockers and anti-blockers, -conjecture, and related problems,
RUTCOR Research Report, RRR-10-2010, Discrete Appl. Math. 159 (2011), 311-321.
LINK: http://edges are arbitrarily colored with n colors.
An n-graph is called complementary connected (CC) if for every i,
the complement G_i = (V;E_i) of the ith chromatic component of G is connected on V .
Delta is a 3-colored triangle; Pi is a 2-graph whose both chromatic components are P_4.
Pi and Delta are CC. We show that there are no others, but the trivial single-vertex graph.
Moreover, every CC n-graph distinct from the above three contains a vertex such that
after its deleting the remaining n-graph is still CC.
Based on these theorems, we construct a one-to-one correspondence between the Pi- and
Delta-free n-graphs and n-person positional games with perfect information and characterize
the normal forms of these games.
For n = 2 we obtain a characterization of the so-called read-once Boolean functions.
As another corollary, we obtain the so-called CIS (Cliques Intersect Stable sets) property
of Pi- and Delta-free n-graphs.
Characterizing the CIS n-graphs is a dicult problem already for n = 2. For example,
every 2-graph is a subgraph of a CIS 2-graph. We give more partial results in this direction.
Yet, whether might be a subgraph of a CIS n-graph?
Delta-conjecture (1978): asserts that NO.
It would suffice to prove Delta-conjecture for n = 3.
We also recall Tibor Gallai's (1967) decomposition of Delta-free graphs into 2-graphs.
Delta-conjecture, if true, would reduce characterizing CIS n-graphs to the case n = 2.
Related papers available online:
D. Andrade, E. Boros, and V. Gurvich, On graphs whose maximal cliques and stable
sets intersect, RUTCOR Research Report RRR-17-2006, Rutgers University.
V. Gurvich, Decomposing complete edge-chromatic graphs and hypergraphs; Revisited,
RUTCOR Research Report, RRR-29-2006, Rutgers University, Discrete Applied Math.,
157 (2009) 3069{3085.
V. Gurvich, On exact blockers and anti-blockers, -conjecture, and related problems,
RUTCOR Research Report, RRR-10-2010, Discrete Appl. Math. 159 (2011), 311-321.
