Grupa permutacji wyznaczona przez hipergrafy minimalnie niedoskonałe. Normalność macierzy odpowiadających hipergrafom minimalnie niedoskonałym

• Autorzy: Szczepan Perz

Warianty tytułu

Permutation Group Derived Through Imperfect Minimal Hypergraphs. Normality of Matrices Corresponding to Minimally Imperfect Hypergraphs

• Języki publikacji: PL

Abstrakty

W artykule przedstawiono charakteryzację pary wzajemnie transwersalnych hipergrafów p-krytycznych minimalnie niedoskonałych. Twierdzenie, iż macierze A0, B0 wyznaczające parę grafów minimalnych niedoskonałych są wielomianami macierzowymi od macierzy P, takiej iż PA0 = A0T jest już bardzo bliskie do udowodnienia. Twierdzenie to nawiązuje do prac V. Chvatala. Tak samo jest z twierdzeniem, iż nie istnieją hipergrafy p-krytyczne o parzystej liczbie wierzchołków. Zdaniem autora wszystko wskazuje na to, że wtedy macierz P musi być rozkładana na cykle nieparzystej długości i ten rozkład wskazuje cykl nieparzystej długości bez przekątnych funkcjonujących w mocnym przypuszczeniu C. Berge'a.

EN

The paper does not concern the graph theory though it interprets the weak hypothesis of C. Berg concerning imperfect graphs and lead us towards strong C. Berg's hypothesis verification. It is not a paper on functional analysis though it uses some generalization of Minkovski's functional. It is not a paper on functional analysis though it interprets the weak hypothesis of C. Berg and D. Koenig's theorem as adjointness of the appropriate norms in finite-dimension linear spaces. It is not a paper on axiomatic convexity theory though it uses various cirtologies [w oryginale: cyrtologie - nigdy nie spotkałem się z takim pojęciem, nie ma go też w żadnym słowniku ani w Internecie - przyp. tłum.] in linear spaces over the fields Q, R, F2, and the ring of integers Z. It is not a paper on algebra though minimally imperfect graphs will be related to some groups of permutations of n-element set. It is not a paper on number theory though in the background it sketches out some connections between minimally imperfect hypergraphs with prime numbers. The paper concerns the problem when the unit ball for a given norm, and the unit ball for the adjoint norm have only integer extreme points. The paper concerns integer linear programming. The main result is the proof that for each of two matrices A0 and B0, describing cliques of the pairs of minimally imperfect hypergraphs, there exists the permutation matrix P, so that the equalities A0P = A0T, and B0P = B0T hold. The existence of such a matrix implies normality of the matrices A0, and B0, was well as the permutation group G, the elements of which commute with the matrices A0, and B0. This result is obtained with use of the isomorphism of the linear space Rn, and the linear space of linear functionals on the space Rn. The result seems to be difficult to obtain with combinatoric methods. (original abstract)

Słowa kluczowe

PL

Teoria grafów; Grafy; Kombinatoryka; Metody numeryczne; Algorytmy; Izomorfizm

EN

Graph theory; Graphs; Combinatorial analysis; Numerical methods; Algorithms; Isomorphism

• Czasopismo: Przegląd Statystyczny
• Rocznik: 2004
• Tom: 51
• Numer: z. 2
• Strony: 5--26

Twórcy

autor

Szczepan Perz

Bibliografia

• [1] Alexiewicz A., Analiza funkcjonalna, PWN, Warszawa 1969.
• [2] Banaszak G., Gajda W, Elementy Algebry Liniowej, część l, WNT, Warszawa 2002.
• [3] Browkin J., Teoria Ciał, PWN, Warszawa 1977.
• [4] Berge C., Graphs and hypergraphs, North Holland Publishing Company, 1976.
• [5] Chvatal V., Edmonds polytopes and a hierarchy combinatońal problems, Discrete Math 4, s. 305-337, 1973.
• [6] Chvatal V., On certain polytopes associated with graphs J. Combin. Theory B18, s. 138-154, 1975.
• [7] Chvatal V., On the strong perfect graphs conjecture J. Combin. Theroy B20, s. 139-141.
• [8] Fulkerson D.R., On the perfect graph theory, in „Mathematical Programing" (T.C. Hu aus S. Robinson, eds) s. 68-76, Academic Press, New York 1973.
• [9] Fulkerson D.R., Anti-blocking polyhedra, J. Combin. Theory 12 s. 50-71, 1972.
• [10] Golumbie M.C., Algorithmic graph theory and perfect graphs, Academic Press, New York 1980.
• [11] Ignasiak E., Badania operacyjne, PWE, Warszawa 2001.
• [12] Koenig D., Teorie der endlichen und unendlichen Graphen, Leipzig 1936.
• [13] Lancaster P., Tieorija matric, „Nauka", Moskwa 1978.
• [14] Lovasz L., Normal hypergraphs and perfect graph conjecture, Discrete Math.2, s. 252-267, 1972.
• [15] Mirsky L., Transversal Theory, Academic Press, New York 1971.
• [16] Mostowski A., Stark M., Algebra Liniowa, PWN, Warszawa 1958.
• [17] Odyniec W., Ślęzak W., Wybrane rozdziały teorii grafów, Bydgoszcz 2003.
• [18] Padberg M., Perfect zero-one matrices, Math. Programing 6, s. 180-186, 1974.
• [19] Perz Sz., Zaremba L., Twierdzenia Koeniga i Birkhoffa i ich związek z zagadnieniem minimalizacji czasu trwania pomiarów automatycznych łączy telekomunikacyjnych. Roczniki PTM, Seria III, Matematyka stosowana XIX, s. 43-50, 1982, praca z roku 1979.
• [20] Perz Sz., Normy i grafy (praca doktorska), IMPAN 1989.
• [21] Perz Sz. and Rolewicz St., Norms and Perfect Graphs, ZOR - Methods and Models of Operations Research, s. 13-27, 1990.
• [22] Perz Sz. and Rolewicz St., On inverse image of non-oriented graphs, In. Optimization, parallel processing and applications, Proc. Oberwolfach and Karlsruhe 1987. Lecture Notes in Economics and Math. Systems 304 Springer-Verlag, Berlin Heidelberg, s. 213-224.
• [23] Zaremba L.S. and Perz Sz., On a Geometrie Property of Perfect Graphs, Combinatorica 2(4), s. 395-397, 1982.
• [24] Perz Sz., Zaremba L., On a certain subclass of (a, w) - partitionable graphs; Demonstratio Mathematica Vol XXIX; No 2; s. 377-380, 1996.
• [25] Perz Sz., O pewnych związkach programowania liniowego z teorią liczb i teorią grafów, Przegląd statystyczny R.L. - Zeszyt 2, s. 133-157, 2003.
• [26] Sołtan P.S., Wwiedienije w aksjomaticzieskuju tieoriju wypukłosti, Sztinca, Kiszyniów 1986.