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

204 
Num Cols

181 
Nonzeros

542 
Pattern Entries

542 
Kind

Combinatorial Problem 
Symmetric

No 
Date

2008 
Author

S. Margulies 
Editor

J.G. Dumas 
Structural Rank 
175 
Structural Rank Full 
false 
Num Dmperm Blocks

11 
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.518034e+00 
Minimum Singular Value 
2.737706e16 
Condition Number 
1.285030e+16

Rank 
165 
sprank(A)rank(A) 
10 
Null Space Dimension 
16 
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/cat_ears_3_1.sms
