Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Matroids (2)
- Rigidity (2)
- Bipartite graphs (1)
- Chordal graphs (1)
- Circuit (1)
-
- Collision-free motion (1)
- Crystalline structure (1)
- Domination (1)
- Folding (1)
- Gröbner basis (1)
- Henneberg sequence (1)
- Hessenberg variety (1)
- Jeu de taquin (1)
- Kazhdan–Lusztig basis (1)
- Matroid (1)
- Pebble game (1)
- Periodic frameworks (1)
- Promotion (1)
- Reconfiguration problems (1)
- Representations of Lie algebras (1)
- Rigidity theory (1)
- Sparse graph (1)
- Sparse graphs (1)
- Spider (1)
- Springer variety (1)
- Symmetric functions (1)
- Tanisaki ideal (1)
- Tau invariant Robinson–Schensted correspondence (1)
- Unfolding (1)
- Young tableau (1)
- Publication Year
Articles 1 - 19 of 19
Full-Text Articles in Discrete Mathematics and Combinatorics
Decomposition Of Beatty And Complementary Sequences, Geremías Polanco
Decomposition Of Beatty And Complementary Sequences, Geremías Polanco
Mathematics Sciences: Faculty Publications
In this paper we express the difference of two complementary Beatty sequences, as the sum of two Beatty sequences closely related to them. In the process we introduce a new Algorithm that generalizes the well known Minimum Excluded algorithm and provides a method to generate combinatorially any pair of complementary Beatty sequences.
Relaxed Wythoff Has All Beatty Solutions, Jon Kay, Geremías Polanco
Relaxed Wythoff Has All Beatty Solutions, Jon Kay, Geremías Polanco
Mathematics Sciences: Faculty Publications
We find conditions under which the P-positions of three subtraction games arise as pairs of complementary Beatty sequences. The first game is due to Fraenkel and the second is an extension of the first game to non-monotone settings. We show that the P-positions of the second game can be inferred from the recurrence of Fraenkel's paper if a certain inequality is satisfied. This inequality is shown to be necessary if the P-positions are known to be pairs of complementary Beatty sequences, and the family of irrationals for which this inequality holds is explicitly given. We highlight several games in the …
Generalized Splines On Arbitrary Graphs, Simcha Gilbert, Julianna Tymoczko, Shira Viel
Generalized Splines On Arbitrary Graphs, Simcha Gilbert, Julianna Tymoczko, Shira Viel
Mathematics Sciences: Faculty Publications
Let G be a graph whose edges are labeled by ideals of a commutative ring. We introduce a generalized spline, which is a vertex labeling of G by elements of the ring so that the difference between the labels of any two adjacent vertices lies in the corresponding edge ideal. Generalized splines arise naturally in combinatorics (algebraic splines of Billera and others) and in algebraic topology (certain equivariant cohomology rings, described by Goresky, Kottwitz, and MacPherson, among others). The central question of this paper asks when an arbitrary edge-labeled graph has nontrivial generalized splines. The answer is “always”, and we …
The Robinson-Schensted Correspondence And A2-Web Bases, Matthew Housley, Heather M. Russell, Julianna Tymoczko
The Robinson-Schensted Correspondence And A2-Web Bases, Matthew Housley, Heather M. Russell, Julianna Tymoczko
Mathematics Sciences: Faculty Publications
We study natural bases for two constructions of the irreducible representation of the symmetric group corresponding to [n, n, n]: the reduced web basis associated to Kuperberg’s combinatorial description of the spider category; and the left cell basis for the left cell construction of Kazhdan and Lusztig. In the case of [n, n], the spider category is the Temperley-Lieb category; reduced webs correspond to planar matchings, which are equivalent to left cell bases. This paper compares the image of these bases under classical maps: the Robinson–Schensted algorithm between permutations and Young tableaux and Khovanov–Kuperberg’s bijection between Young tableaux and reduced …
Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa
Periodic Body-And-Bar Frameworks, Ciprian Borcea, Ileana Streinu, Shin-Ichi Tanigawa
Computer Science: Faculty Publications
Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell–Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.
The K-Dominating Graph, Ruth Haas, Karen Seyffarth
The K-Dominating Graph, Ruth Haas, Karen Seyffarth
Mathematics Sciences: Faculty Publications
Abstract. Given a graph G, the k-dominating graph of G, Dk(G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in Dk(G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph Dk(G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of …
Generalizing Tanisaki's Ideal Via Ideals Of Truncated Symmetric Functions, Aba Mbirika, Julianna Tymoczko
Generalizing Tanisaki's Ideal Via Ideals Of Truncated Symmetric Functions, Aba Mbirika, Julianna Tymoczko
Mathematics Sciences: Faculty Publications
Abstract. We define a family of ideals Ih in the polynomial ring Z[x1, . . . , xn] that are parametrized by Hessenberg functions h (equivalently Dyck paths or ample partitions). The ideals Ih generalize algebraically a family of ideals called the Tanisaki ideal, which is used in a geometric construction of permutation representations called Springer theory. To define Ih, we use polynomials in a proper subset of the variables {x1, . . . , xn} that are symmetric under the corresponding permutation subgroup. We call these polynomials truncated symmetric functions and …
Billey's Formula In Combinatorics, Geometry, And Topology, Julianna Tymoczko
Billey's Formula In Combinatorics, Geometry, And Topology, Julianna Tymoczko
Mathematics Sciences: Faculty Publications
In this expository paper we describe a powerful combinatorial formula and its implications in geometry, topology, and algebra. This formula first appeared in the appendix of a book by Andersen, Jantzen, and Soergel. Sara Billey discovered it independently five years later, and it played a prominent role in her work to evaluate certain polynomials closely related to Schubert polynomials. Billey's formula relates many pieces of Schubert calculus: the geometry of Schubert varieties, the action of the torus on the flag variety, combinatorial data about permutations, the cohomology of the flag variety and of the Schubert varieties, and the combinatorics of …
A Simple Bijection Between Standard 3×N Tableaux And Irreducible Webs For ����3, Julianna Tymoczko
A Simple Bijection Between Standard 3×N Tableaux And Irreducible Webs For ����3, Julianna Tymoczko
Mathematics Sciences: Faculty Publications
Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and ����2. Building on a result of Kuperberg’s, Khovanov-Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape 3 × n and irreducible webs for ����3whose boundary vertices are all sources. In this paper, we give a simple and explicit map from standard Young tableaux of shape 3 …
Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke
Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke
Computer Science: Faculty Publications
It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.
Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke
Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke
Computer Science: Faculty Publications
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming.
Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu
Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu
Computer Science: Faculty Publications
Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that "live on a cone," in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is "visible to" a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support …
Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke
Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke
Computer Science: Faculty Publications
Given n ≥ 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.
A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke
A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke
Computer Science: Faculty Publications
We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in Rd may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R2 this says that any planar map all of whose faces are triangles may be 3-colored, and in R3 it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.
Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran
Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
We define and study slider-pinning rigidity, giving a complete combinatorial characterization. This is done via direction-slider networks, which are a generalization of Whiteley’s direction networks.
Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran
Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran
Computer Science: Faculty Publications
A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V′⊂V spans more than k|V′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms …
Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke
Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke
Computer Science: Faculty Publications
The Yao graph for k = 4, Y4, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.
Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu
Pebble Game Algorithms And Sparse Graphs, Audrey Lee, Ileana Streinu
Computer Science: Faculty Publications
A multi-graph G on n vertices is (k,ℓ)-sparse if every subset of n′⩽n vertices spans at most kn′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓ edges. For integer valuesk and ℓ∈[0,2k), we characterize the (k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)-pebble games. [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.
Characterizing Sparse Graphs By Map Decompositions, Ruth Haas, Audrey Lee, Ileana Streinu, Louis Theran
Characterizing Sparse Graphs By Map Decompositions, Ruth Haas, Audrey Lee, Ileana Streinu, Louis Theran
Mathematics Sciences: Faculty Publications
A map is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into k edge-disjoint maps after: (1) the addition of any ℓ edges; (2) the addition of some ℓ edges. These graphs are identified with classes of sparse graphs; the results are also given in matroidal terms.