Orthonormal Representations of H -Free Graphs
- PDF / 338,598 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 192 Views
Orthonormal Representations of H-Free Graphs Igor Balla1 · Shoham Letzter2,3 · Benny Sudakov1 Received: 5 May 2019 / Revised: 23 January 2020 / Accepted: 9 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let x1 , . . . , xn ∈ Rd be unit vectors such that among any three there is an orthogonal pair. How large can n be as a function of d, and how large can the length of x1 +· · ·+xn be? The answers to these two celebrated questions, asked by Erd˝os and Lovász, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lovász ϑ-function and minimum semidefinite rank. In this paper, we study these parameters for general H -free graphs. In particular, we show that for certain bipartite graphs H , there is a connection between the Turán number of H and the maximum of ϑ(G) over all H -free graphs G. Keywords Lovász ϑ-function · Minrank · Orthonormal representation · Turán numbers
1 Introduction Given a graph G, a map f : V (G) → Rd is called an orthonormal representation of G (in Rd ) if f (u) = 1 for all u ∈ V (G) and f (u), f (v) = 0 for all distinct
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach S. Letzter: Research supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zurich Foundation. B. Sudakov: Research supported in part by SNSF Grant 200021-175573. Igor Balla [email protected] Shoham Letzter [email protected]; [email protected] Benny Sudakov [email protected] 1
Department of Mathematics, ETH Zurich, Zurich, Switzerland
2
ETH Institute for Theoretical Studies, ETH Zurich, Zurich, Switzerland
3
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK
123
Discrete & Computational Geometry
u, v ∈ V (G) such that uv ∈ / E(G). Note that every graph G on n vertices has an orthonormal representation, since we may assign each vector to a corresponding orthonormal basis vector in R|G| . Given an orthonormal representation f of a graph G with vertex set [n], we define M f to be the Gram matrix of the vectors f (1), . . . , f (n), so that (M f )i, j = f (i), f ( j). The concept of orthonormal representations goes back to a seminal paper of Lovász [26], who used them to define a graph parameter now known as the Lovász ϑ-function. The ϑ-function of a graph G has several equivalent definitions. Here we list the ones that we shall use later. Definition 1.1 Let G be a graph with vertex set [n]. The ϑ-function of G, denoted ϑ(G), can be defined in the following ways, which are shown to be equivalent in [26]. 1. ϑ(G) is the maximum, over all orthonormal representations f of the complement graph G, of the largest eigenvalue of the Gram matrix M f . 2. ϑ(G) is the maximum of 1 − λ1 (A)/λn (A), over all n × n real symmetric matrices A such that Ai, j = 0 if i j ∈ E(G) or i = j.1 3. ϑ(G) is the minimum, over all orthonormal representations f of G and all unit vectors x, of maxv∈V (G) x
Data Loading...
