Herbert Fleischner, Stefan Szeider

Tomas Feder, Carlos Subi

We conjecture that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$

such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove this conjecture in the case where there are

two dimensions ...
more >>>

Tomas Feder, Carlos Subi

It has been shown that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching

$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove a generalization of a special case of ...
more >>>

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>