Advanced search options

You searched for `subject:(Witsenhausen problem)`

. One record found.

▼ Search Limiters

Delft University of Technology

1. DeCorte, P.E.B. The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs.

Degree: 2015, Delft University of Technology

URL: http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c

This thesis is about maximum independent set and chromatic number problems on certain kinds of infinite graphs. A typical example comes from the Witsenhausen problem: For n ≥ 2, let S^{n-1} := { x ∈ \R^{n} : \|x\|_{2} =1 } be the unit sphere in \R^{n}, and let G=(V,E) be the graph with V = S^{n-1}, in which two points in S^{n-1} are adjacent if and only if their inner product is equal to 0. What is the largest possible Lebesgue measure of an independent set in G? The problem is reminiscent of a coding theory problem, in which one asks for the size of a largest set of distinct points in some metric space so that the distance between each pair of points is at least some specified constant d. Such a problem can be framed as a maximum independent set problem: Define a graph whose vertex set is the metric space, and join two points with an edge whenever their distance is less than d. The codes of minimum distance d are then precisely the independent sets in this graph. In the Witsenhausen problem, rather than asking for a set of points in the sphere in which all the distances less than d are forbidden, we ask for a set of points in which only one distance is forbidden. And it turns out that the \emph{Delsarte} (also called \emph{linear programming}) upper bounds for the size of codes can be adjusted to give upper bounds for the measure of an independent set in the Witsenhausen graph. This was first done in and . The Witsenhausen problem was stated in , and in the same note it was shown that the fraction of the n-dimensional sphere which can be occupied by any measurable independent set is upper bounded by the function 1/n. Frankl and Wilson made a breakthrough in 1981 when they proved an upper bound which decreases exponentially in n. Despite this progress on asymptotics, the 1/3 upper bound in the n=3 case has not moved since the original statement of the problem until now. In Chapter \ref{ch:opp} we give one of the main results of the thesis, which is an improvement of this upper bound to 0.313. The proof works by strengthening the Delsarte-type bounds using some combinatorial arguments deduced in Chapters \ref{ch:opp-background} and \ref{ch:circular}. The next main result of the thesis answers a natural question about the graphs G(S^{n-1}, X), whose vertex set is S^{n-1} and where two points are joined with an edge if and only if their inner product belongs to the set X \subset [-1,1] of forbidden inner products. These graphs generalize the Witsenhausen graph, and are called \emph{forbidden inner product graphs}. One may ask, Does there exist a measurable independent set of maximum measure? There is a graph G = G(S^{2}, X) (many, in fact) having no such independent set. In Chapter \ref{ch:circular} we construct for every \e>0 an independent set in G having measure at least 1/2 - \e, but we show that there is no independent set of measure equal to 1/2. In Chapters…
*Advisors/Committee Members: Vallentin, F., Aardal, K.I..*

Subjects/Keywords: Eigenvalue method; Delsarte code bounds; Lovasz theta function; infinite graphs; harmonic analysis; orthogonality graph; Witsenhausen problem

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

DeCorte, P. E. B. (2015). The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs. (Doctoral Dissertation). Delft University of Technology. Retrieved from http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c

Chicago Manual of Style (16^{th} Edition):

DeCorte, P E B. “The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs.” 2015. Doctoral Dissertation, Delft University of Technology. Accessed August 05, 2020. http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c.

MLA Handbook (7^{th} Edition):

DeCorte, P E B. “The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs.” 2015. Web. 05 Aug 2020.

Vancouver:

DeCorte PEB. The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs. [Internet] [Doctoral dissertation]. Delft University of Technology; 2015. [cited 2020 Aug 05]. Available from: http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c.

Council of Science Editors:

DeCorte PEB. The Eigenvalue Method for Extremal Problems on Infinite Vertex-Transitive Graphs. [Doctoral Dissertation]. Delft University of Technology; 2015. Available from: http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; urn:NBN:nl:ui:24-uuid:da16eb76-4031-4350-baf3-307aa01a337c ; http://resolver.tudelft.nl/uuid:da16eb76-4031-4350-baf3-307aa01a337c