An official website of the United States government
Abstract A graph is said to be ‐free if it does not contain any subdivision of as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.
more »
« less
Realizing the s-Permutahedron via Flow Polytopes
In 2019, Ceballos and Pons introduced the s-weak order on s-decreasing trees, for any weak composition s. They proved its lattice structure and conjectured that it could be realized as the 1-skeleton of a polyhedral subdivision of a zonotope of dimension n-1. We answer their conjecture in the case where s is a (strict) composition by providing three geometric realizations of the s-permutahedron. The first one is the dual graph of a triangulation of a flow polytope of high dimension. The second, obtained using the Cayley trick, is the dual graph of a fine mixed subdivision of a sum of hypercubes that has the conjectured dimension. The third, obtained using tropical geometry, is the 1-skeleton of a polyhedral complex for which we can provide explicit coordinates of the vertices and whose support is a permutahedron as conjectured.
more »
« less
- Award ID(s):
- 2154019
- PAR ID:
- 10543268
- Publisher / Repository:
- Séminaire Lotharingien de Combinatoire
- Date Published:
- Volume:
- 91B
- Page Range / eLocation ID:
- 60
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper presents procedures to generate truss topologies as an input form for polyhedral graphic statics and develops an algebraic formulation to construct their force diagrams. The study's ultimate goal is to extend the authors' previous research in 2D [1] to generate 3D strut-and-tie models and stress fields for reinforced concrete design. The recent algebraic formulation constructs reciprocal polyhedral diagrams of 3D graphic statics with either form or force as input [2]. However, the input is usually a set of polyhedrons or self-stressed networks [3]. Another implementation of polyhedral graphic statics [4] includes general truss topologies. But the starting geometry is usually the global force diagram, and based on its modification or subdivision, a form diagram is constructed. Therefore, currently, there exists no formulation to analyze a spatial truss using polyhedral graphic statics. This paper develops an algorithm to build upon the algebraic 3D graphic statics formulation and notation [2, 5] to construct the force diagram for input geometries that do not include all closed cells. The article also shows how the proper definition of the external spaces between the applied loads and reaction forces and the tetrahedral subdivision of the truss makes it possible to construct the reciprocal force diagram. This technique can be further explored to generate various truss topologies for a given volume and identify an optimized solution as the strut-and-tie model for reinforced concrete. Figure 1 illustrates an example of a spatial truss with two vertical applied loads and four vertical supports, the subdivision of the inner and outer space, the constructed force diagram, and the Minkowski sum of the dual diagrams (i.e., the geometrical summation of the form and scaled force diagram).more » « less
-
A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.more » « less
-
Abstract It was conjectured by Hajós that graphs containing no ‐subdivision are 4‐colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called Hajós graph, is 4‐connected but not 5‐connected. In this paper, we show that if a Hajós graph admits a 4‐cut or 5‐cut with a planar side then the planar side must be small or contains a special wheel. This is a step in our effort to reduce Hajós' conjecture to the Four Color Theorem.more » « less
-
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
