JGD_Margulies/wheel_4_1
Combinatorial optimization as polynomial eqns, Susan Margulies, UC Davis
Name 
wheel_4_1 
Group 
JGD_Margulies 
Matrix ID 
2167 
Num Rows

36 
Num Cols

41 
Nonzeros

122 
Pattern Entries

122 
Kind

Combinatorial Problem 
Symmetric

No 
Date

2008 
Author

S. Margulies 
Editor

J.G. Dumas 
Structural Rank 
36 
Structural Rank Full 
true 
Num Dmperm Blocks

2 
Strongly Connect Components

1 
Num Explicit Zeros

0 
Pattern Symmetry

0% 
Numeric Symmetry

0% 
Cholesky Candidate

no 
Positive Definite

no 
Type

binary 
SVD Statistics 
Matrix Norm 
3.369666e+00 
Minimum Singular Value 
4.962585e17 
Condition Number 
6.790143e+16

Rank 
32 
sprank(A)rank(A) 
4 
Null Space Dimension 
4 
Full Numerical Rank? 
no 
Download Singular Values 
MATLAB

Download 
MATLAB
Rutherford Boeing
Matrix Market

Notes 
Combinatorial optimization as polynomial eqns, Susan Margulies, UC Davis
From JeanGuillaume Dumas' Sparse Integer Matrix Collection,
http://ljk.imag.fr/membres/JeanGuillaume.Dumas/simc.html
http://arxiv.org/abs/0706.0578
Expressing Combinatorial Optimization Problems by Systems of Polynomial
Equations and the Nullstellensatz
Authors: J.A. De Loera, J. Lee, Susan Margulies, S. Onn
(Submitted on 5 Jun 2007)
Abstract: Systems of polynomial equations over the complex or real
numbers can be used to model combinatorial problems. In this way, a
combinatorial problem is feasible (e.g. a graph is 3colorable,
hamiltonian, etc.) if and only if a related system of polynomial
equations has a solution. In the first part of this paper, we construct
new polynomial encodings for the problems of finding in a graph its
longest cycle, the largest planar subgraph, the edgechromatic number,
or the largest kcolorable subgraph. For an infeasible polynomial
system, the (complex) Hilbert Nullstellensatz gives a certificate that
the associated combinatorial problem is infeasible. Thus, unless P =
NP, there must exist an infinite sequence of infeasible instances of
each hard combinatorial problem for which the minimum degree of a
Hilbert Nullstellensatz certificate of the associated polynomial system
grows. We show that the minimumdegree of a Nullstellensatz
certificate for the nonexistence of a stable set of size greater than
the stability number of the graph is the stability number of the graph.
Moreover, such a certificate contains at least one term per stable set
of G. In contrast, for non3 colorability, we found only graphs with
Nullstellensatz certificates of degree four.
Filename in JGD collection: Margulies/wheel_4_1.sms
