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

21 
Num Cols

25 
Nonzeros

74 
Pattern Entries

74 
Kind

Combinatorial Problem 
Symmetric

No 
Date

2008 
Author

S. Margulies 
Editor

J.G. Dumas 
Structural Rank 
21 
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.323205e+00 
Minimum Singular Value 
3.207570e16 
Condition Number 
1.036051e+16

Rank 
20 
sprank(A)rank(A) 
1 
Null Space Dimension 
1 
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_3_1.sms
