Embedding and the first Laplace eigenvalue of a finite graph. (English) Zbl 07929155
Summary: Göring-Helmberg-Wappler introduced optimization problems regarding embeddings of a graph into a Euclidean space and the first nonzero eigenvalue of the Laplacian of a graph, which are dual to each other in the framework of semidefinite programming. In this paper, we introduce a new graph-embedding optimization problem, and discuss its relation to Göring-Helmberg-Wappler’s problems. We also identify the dual problem to our embedding optimization problem. We solve the optimization problems for distance-regular graphs and the one-skeleton graphs of the \(\mathrm{C}_{60}\) fullerene and some other Archimedian solids.
MSC:
| 90Cxx | Mathematical programming |
References:
| [1] | Ballmann, W.; Świa̧tkowski, J., On \(L^2\)-cohomology and property (T) for automorphism groups of polyhedral cell complexes, Geom Funct Anal, 7, 615-645, 1997 · Zbl 0897.22007 · doi:10.1007/s000390050022 |
| [2] | Boyd, S.; Vandenberghe, L., Convex optimization, 2004, Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [3] | Chung, FRK; Kostant, B.; Sternberg, S., Groups and the Buckyball, Lie Theory Geom Prog Math, 123, 97-126, 1994 · Zbl 0844.20031 · doi:10.1007/978-1-4612-0261-5_4 |
| [4] | Feit, W.; Higman, G., The nonexistence of certain generalized polygons, J Alg, 1, 114-131, 1964 · Zbl 0126.05303 · doi:10.1016/0021-8693(64)90028-6 |
| [5] | Fiedler, M., Laplacian of graphs and algebraic connectivity, Banach Center Publ, 25, 57-70, 1989 · Zbl 0731.05036 · doi:10.4064/-25-1-57-70 |
| [6] | Godsil, CD, Algebraic combinatorics, 1993, New York: Chapman & Hall, New York · Zbl 0784.05001 |
| [7] | Göring, F.; Helmberg, C.; Wappler, M., Embedded in the shadow of the separator, SIAM J Optim, 19, 472-501, 2008 · Zbl 1169.05347 · doi:10.1137/050639430 |
| [8] | Göring, F.; Helmberg, C.; Wappler, M., The rotational dimension of a graph, J Graph Theory, 66, 283-302, 2011 · Zbl 1213.05167 · doi:10.1002/jgt.20502 |
| [9] | Izeki, H.; Nayatani, S., Combinatorial harmonic maps and discrete-group actions on Hadamard spaces, Geom Dedic, 114, 147-188, 2005 · Zbl 1108.58014 · doi:10.1007/s10711-004-1843-y |
| [10] | Izeki, H.; Kondo, T.; Nayatani, S., Fixed-point property of random groups, Ann Glob Anal Geom, 35, 363-379, 2009 · Zbl 1236.20046 · doi:10.1007/s10455-008-9139-3 |
| [11] | Izeki, H.; Kondo, T.; Nayatani, S., \(N\)-step energy of maps and fixed-point property of random groups, Groups Geom Dyn, 6, 701-736, 2012 · Zbl 1337.20042 · doi:10.4171/ggd/171 |
| [12] | Ivrissimtzis, I.; Peyerimhoff, N., Spectral representations of vertex transitive graphs, Archimedean solids and finite Coxeter groups, Groups Geom Dyn, 7, 591-615, 2013 · Zbl 1277.05108 · doi:10.4171/ggd/199 |
| [13] | Pansu, P., Formules de Matsushima, de Garland et propriété (T) pour des groupes agissant sur des espaces symétriques ou desimmeubles, Bull Soc Math France, 126, 107-139, 1998 · Zbl 0933.22009 · doi:10.24033/bsmf.2322 |
| [14] | Żuk, A., La propriété (T) de Kazhdan pour les groupes agissant sur les polyédres, CR Acad Sci Paris, 323, 453-458, 1996 · Zbl 0858.22007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
