Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: perfect matching

Sortuj według:

Ogranicz wyniki do:

Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles

Itsykson D., Slabodkin M., Oparin V., Sokolov D.

Fundamenta Informaticae

2016

Vol. 145, nr 3

229--242

The resolution complexity of the perfectmatching principle was studied by Razborov [1], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n)) where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n+1 and the complete bipartite graph KnO(n), that improves the lower bounds following from [1]. We show that for every graph G with n vertices that has no perfect matching there exists a resolution refutation of perfect matching principle for G of size O(n22n). Thus our lower boundsmatch upper bounds up to a multiplicative constant in the exponent. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, . . . , n} → {1, 2, . . . , d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph's edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph. Preliminary version of this paper appeared in proceedings of CSR-2015 [2].

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

Formanowicz P., Tanaś K.

International Journal of Applied Mathematics and Computer Science

2012

Vol. 22, no. 3

765-778

It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.

A note of arbitrarily vertex decomposable graphs

Marczyk A.

Opuscula Mathematica

2006

Vol. 26, no. 1

109-118

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.