A new proof of Balinski's theorem on the connectivity of polytopes
- Authors: Pineda-Villavicencio, Guillermo
- Date: 2021
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 344, no. 7 (2021), p.
- Full Text:
- Reviewed:
- Description: Balinski (1961) proved that the graph of a d-dimensional convex polytope is d-connected. We provide a new proof of this result. Our proof provides details on the nature of a separating set with exactly d vertices; some of which appear to be new. © 2021 Elsevier B.V.
The linkedness of cubical polytopes: the cube
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Electronic Journal of Combinatorics Vol. 28, no. 3 (2021), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is [(d + 1)/2]-linked, for every d ≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d ≥ 1, a cubical d-polytope is [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is strongly k-linked if it has at least 2k + 1 vertices and, for every vertex v of G, the subgraph G − v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d ≥ 1, d-dimensional cubes are strongly
Polytopes close to being simple
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 64, no. 1 (2020), p. 200-215
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that d-polytopes with at most d- 2 nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and d- 2 , showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for d-polytopes with d+ k vertices and at most d- k+ 3 nonsimple vertices, provided k
On the reconstruction of polytopes
- Authors: Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2019
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
The excess degree of a polytope
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2018
- Type: Text , Journal article
- Relation: SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046, http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d ot = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0 vertices and f1 edges, are determined.
Nonmeasurable subgroups of compact groups
- Authors: Hernández, Salvador , Hofmann, Karl , Morris, Sidney
- Date: 2016
- Type: Text , Journal article
- Relation: Journal of Group Theory Vol. 19, no. 1 (2016), p. 179-189
- Full Text:
- Reviewed:
- Description: In 1985 S. Saeki and K. Stromberg published the following question: Does every infinite compact group have a subgroup which is not Haar measurable? An affirmative answer is given for all compact groups with the exception of some metric profinite groups which are almost perfect and strongly complete. In this spirit it is also shown that every compact group contains a non-Borel subgroup. © 2016 by De Gruyter 2016 Generalitat Valenciana PROMETEO/2014/062 We are grateful for our referee's useful comments. In particular, the suggestion that originally we had overlooked [Pacific J. Math. 116 (1985), 217-241] shortened the proof of Theorem 4.3 considerably.
Constructions of large graphs on surfaces
- Authors: Feria-Purón, Ramiro , Pineda-Villavicencio, Guillermo
- Date: 2014
- Type: Text , Journal article
- Relation: Graphs and Combinatorics Vol. 30, no. 4 (2014), p. 895-908
- Full Text: false
- Reviewed:
- Description: We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface
The weights of closed subgroups of a locally compact group
- Authors: Hernández, Salvador , Hofmann, Karl , Morris, Sidney
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of Group Theory Vol. 15, no. 5 (2012), p. 613-630
- Full Text: false
- Reviewed:
- Description: Let G be an infinite locally compact group and let n be a cardinal satisfying n 0 ≤ n ≤ w(G) for the weight w(G) of G. It is shown that there is a closed subgroup N of G with w(N) = n. Sample consequences are: (1) Every infinite compact group contains an infinite closed metric subgroup. (2) For a locally compact group G and n a cardinal satisfying n 0 ≤ n ≤ w
- Description: 2003010570
An algorithm for the optimization of multiple classifers in data mining based on graphs
- Authors: Kelarev, Andrei , Ryan, Joe , Yearwood, John
- Date: 2009
- Type: Text , Journal article
- Relation: The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 65-85
- Full Text: false
- Reviewed:
- Description: This article develops an efficient combinatorial algorithm based on labeled directed graphs and motivated by applications in data mining for designing multiple classifiers. Our method originates from the standard approach described in [37]. It defines a representation of a multiclass classifier in terms of several binary classifiers. We are using labeled graphs to introduce additional structure on the classifier. Representations of this sort are known to have serious advantages. An important property of these representations is their ability to correct errors of individual binary classifiers and produce correct combined output. For every representation like this we develop a combinatorial algorithm with quadratic running time to compute the largest number of errors of individual binary classifiers which can be corrected by the combined multiple classifier. In addition, we consider the question of optimizing the classifiers of this type and find all optimal representations for these multiple classifiers.
- Description: 2003007563
On the nonexistence of graphs of diameter 2 and defect 2
- Authors: Miller, Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo
- Date: 2009
- Type: Text , Journal article
- Relation: The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 5-20
- Full Text: false
- Reviewed:
- Description: In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.
- Description: 2003007893
New constructions of A-magic graphs using labeling matrices
- Authors: Sugeng, Kiki Ariyanti , Miller, Mirka
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008), p. 147-151
- Full Text: false
- Reviewed:
On antimagic labelings of disjoint union of complete s-partite graphs
- Authors: Dafik , Miller, Mirka , Ryan, Joe , Baca, Martin
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008 2008), p. 41-49
- Full Text:
- Reviewed:
- Description: By an (a, d)-edge-antimagic total labeling of a graph G(V, E) we mean a bijective function f from V(G) u E(G) onto the set. { 1, 2, ... ,ǀV(C)ǀ+IE(G)I} such that the set of all the edge-weights, w(uv) ,.... f(u) + f(uv) + f(v), uv C E (G), is {a, a+ d, a+ 2d, . . . , a + (lE(G)I-1)d}, for two integers a > 0 and d
On antimode graphs
- Authors: Marshall, Kim , Ryan, Joe
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 65, no. (May 2008 2008), p. 51-60
- Full Text: false
- Reviewed:
- Description: The term mode graph was introduced by Boland, Kauffman and Panroug [2] to defiue a connected graph G such that, for every pair of vertices v, w in G, the number of vertices with eccentricity e(v) is equal to the number of vertices with eccentricity e(w). As a natural extension to this work, the concept of an antimode graph was introduced to describe a graph for which if e(v) ≠ e(w) then the number of vertices with eccentricity e(v) is not equal to the number of vertices with eccentricity e(w). ln this paper we determine the existence of some classes of antimode graphs, namely equisequential and (a, d)-antimode graphs.
On graphs of maximum degree 3 and defect 4
- Authors: Pineda-Villavicencio, Guillermo , Miller, Mirka
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of combinatorial mathematics and combinatorial computing Vol. 65, no. (May 2008), p. 25-31
- Full Text: false
- Reviewed:
- Description: It is well known that apart from the Petersen graph there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and