An official website of the United States government
Abstract A spline is an assignment of polynomials to the vertices of a graph whose edges are labeled by ideals, where the difference of two polynomials labeling adjacent vertices must belong to the corresponding ideal. The set of splines forms a ring. We consider spline rings where the underlying graph is the Cayley graph of a symmetric group generated by a collection of transpositions. These rings generalize the GKM construction for equivariant cohomology rings of flag, regular semisimple Hessenberg and permutohedral varieties. These cohomology rings carry two actions of the symmetric group$$S_n$$whose graded characters are both of general interest in algebraic combinatorics. In this paper, we generalize the graded$$S_n$$-representations from the cohomologies of the above varieties to splines on Cayley graphs of$$S_n$$and then (1) give explicit module and ring generators for whenever the$$S_n$$-generating set is minimal, (2) give a combinatorial characterization of when graded pieces of one$$S_n$$-representation is trivial, and (3) compute the first degree piece of both graded characters for all generating sets.
more »
« less
Trimming Graphs Using Clausal Proof Optimization
We present a method to gradually compute a smaller and smaller unsatisfiable core of a propositional formula by minimizing proofs of unsatisfiability. The goal is to compute a minimal unsatisfiable core that is relatively small compared to other minimal unsatisfiable cores of the same formula. We try to achieve this goal by postponing deletion of arbitrary clauses from the formula as long as possible---in contrast to existing minimal unsatisfiable core algorithms. We applied this method to reduce the smallest known unit-distance graph with chromatic number 5 from 553 vertices and 2720 edges to 529 vertices and 2670 edges.
more »
« less
- Award ID(s):
- 1813993
- PAR ID:
- 10120529
- Date Published:
- Journal Name:
- International Conference on Principles and Practice of Constraint Programming
- Volume:
- 11802
- Page Range / eLocation ID:
- 251-267
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A subset of vertices of a graph is minimal if, within all subsets of the same size, its vertex boundary is minimal. We give a complete, geometric characterization of minimal sets for the planar integer lattice $$X$$. Our characterization elucidates the structure of all minimal sets, and we are able to use it to obtain several applications. We show that the neighborhood of a minimal set is minimal. We characterize uniquely minimal sets of $$X$$: those which are congruent to any other minimal set of the same size. We also classify all efficient sets of $$X$$: those that have maximal size amongst all such sets with a fixed vertex boundary. We define and investigate the graph $$G$$ of minimal sets whose vertices are congruence classes of minimal sets of $$X$$ and whose edges connect vertices which can be represented by minimal sets that differ by exactly one vertex. We prove that G has exactly one infinite component, has infinitely many isolated vertices and has bounded components of arbitrarily large size. Finally, we show that all minimal sets, except one, are connected.more » « less
-
Abstract We study the problem of fitting a piecewise affine (PWA) function to input–output data. Our algorithm divides the input domain into finitely many regions whose shapes are specified by a user-provided template and such that the input–output data in each region are fit by an affine function within a user-provided error tolerance. We first prove that this problem is NP-hard. Then, we present a top-down algorithmic approach for solving the problem. The algorithm considers subsets of the data points in a systematic manner, trying to fit an affine function for each subset using linear regression. If regression fails on a subset, the algorithm extracts a minimal set of points from the subset (an unsatisfiable core) that is responsible for the failure. The identified core is then used to split the current subset into smaller ones. By combining this top-down scheme with a set-covering algorithm, we derive an overall approach that provides optimal PWA models for a given error tolerance, where optimality refers to minimizing the number of pieces of the PWA model. We demonstrate our approach on three numerical examples that include PWA approximations of a widely used nonlinear insulin–glucose regulation model and a double inverted pendulum with soft contacts.more » « less
-
Grandoni, Fabrizio; Herman, Grzegorz; Sanders, Peter (Ed.)Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)-spanners, for n points in ℝ^d, are known, where the resulting graph has 𝒪(n log n log log⁶n) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical - replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with 𝒪(n log log²n log log log n) edges.more » « less
-
Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let [Formula: see text] and [Formula: see text] be two polygonal curves in [Formula: see text] with [Formula: see text] and [Formula: see text] vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in [Formula: see text] time, (3) a linear-time [Formula: see text]-approximation algorithm, and (4) a data structure that supports [Formula: see text]-time decision queries, where [Formula: see text] is the number of vertices of the query curve and [Formula: see text] the number of vertices of the preprocessed curve.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-30048-7_15
