850 Polytechnic Lane, Marietta, GA 30060

Add to calendar

Speaker: Dr. Joshua Cooper, University of South Carolina

Title: Probing the Structure of Graph Nullspaces with Zero Loci

Abstract: The adjacency nullity of graphs and hypergraphs is something of a mystery, though there are nice results for some narrow classes of graphs such as trees.  There is, however, rich structure in their nullspaces (and, for hypergraphs, their nullvarieties), visible by partitioning nullvectors according to their zero loci: vertex sets which are indices of their zero coordinates.  This set system is the lattice of flats of a ``kernel matroid'', a subsystem of which are the ``stalled'' sets closed under skew zero forcing (SZF), a graph percolation/infection model known to have connections with rank and nullity.  These set systems have interesting descriptions in terms of matchings, vertex covers, and edges’ influence on rank – especially for trees.  For a wide variety of graphs, the lattice of SZF-closed sets is also a matroid, a fact which can be used to obtain a polynomial-time algorithm for computing the skew zero forcing number.  This contrasts with the general case, where we show that the corresponding decision problem is NP-hard.  We also define skew zero forcing for hypergraphs, and show that, for linear hypertrees, the poset of SZF-closed sets is dual to the lattice of ideals of the hypergraph's nullvariety; while, for complete hypergraphs, the SZF-closed sets and the zero loci of nullvectors are more loosely related.

  • Jose Millan

1 person is interested in this event

User Activity

No recent activity