Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"Delft University of Technology" +contributor:("Vallentin, F.")`

.
Showing records 1 – 2 of
2 total matches.

▼ 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

Delft University of Technology

2. De Laat, D. Moment methods in extremal geometry.

Degree: 2016, Delft University of Technology

URL: http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473

In this thesis we develop techniques for solving problems in extremal geometry. We give an infinite dimensional generalization of moment techniques from polynomial optimization. We use this to construct semidefinite programming hierarchies for approximating optimal packing densities and ground state energies of particle systems. For this we define topological packing graphs as an abstraction for the graphs arising from geometric packing problems, and we prove results concerning convergence and strong duality. We use harmonic analysis to perform symmetry reduction and reduce to a finite dimensional variable space in the optimization problems. For this we explicitly work out the harmonic analysis for kernels on spaces consisting of subsets of another space. We show how sums of squares characterizations from real algebraic geometry can be used to reduce the infinitely many constraints to finitely many semidefinite constraints, where we focus in particular on numerical conditioning and symmetry reduction. We perform explicit computations for concrete problems: We give new bounds for binary spherical cap packings, binary sphere packings, and classical sphere packing problems. This can be used, for instance, to give a simple optimality proof of a binary spherical cap packing. We compute the second step of our hierarchy where the numerical results suggest the bound is sharp for the 5-particle case of the Thomson and related problems. This is the first time a 4-point bound has been computed for a continuous problem.
*Advisors/Committee Members: Vallentin, F., Aardal, K.I..*

Subjects/Keywords: packing problems; energy minimization; semidefinite programming; Lasserre hierarchy; Riesz energy; bounds

Record Details Similar Records

❌

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

APA (6^{th} Edition):

De Laat, D. (2016). Moment methods in extremal geometry. (Doctoral Dissertation). Delft University of Technology. Retrieved from http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473

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

De Laat, D. “Moment methods in extremal geometry.” 2016. Doctoral Dissertation, Delft University of Technology. Accessed August 05, 2020. http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473.

MLA Handbook (7^{th} Edition):

De Laat, D. “Moment methods in extremal geometry.” 2016. Web. 05 Aug 2020.

Vancouver:

De Laat D. Moment methods in extremal geometry. [Internet] [Doctoral dissertation]. Delft University of Technology; 2016. [cited 2020 Aug 05]. Available from: http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473.

Council of Science Editors:

De Laat D. Moment methods in extremal geometry. [Doctoral Dissertation]. Delft University of Technology; 2016. Available from: http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; urn:NBN:nl:ui:24-uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473 ; http://resolver.tudelft.nl/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473