• Fermeture de la BCU-Centrale suite au déménagement: 4 juillet – 16 août : La BCU-Centrale est fermée pour déménagement. Les commandes en magasins ainsi que les demandes de prêt entre bibliothèques ne seront pas possibles.

17 août : Réouverture de la BCU à Beauregard (rue de la Carrière 22)
• Hors campus: Membres de la communauté universitaire ou de la HES-SO: n'oubliez pas d'utiliser le VPN de votre institution pour bénéficier de tous les accès.

Cette recherche s'applique uniquement aux ressources en bibliothèque.
206 résultats
Trier par:
Ajouter à la liste:
Étendre à toutes les références (sans texte intégral)
• Article
Sélectionner

Removing Degeneracy in LP-Type Problems Revisited

Matoušek, Jiří
Discrete & Computational Geometry. - 2009/42/4/517-526
Disponible
Titre: Removing Degeneracy in LP-Type Problems Revisited
Auteur: Matoušek, Jiří
Description: LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. In Matoušek and Škovroň (Theory Comput. 3:159-177, 2007), it is proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+ε with a certain small positive constant ε. The proof goes by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here by a short topological argument we prove that the dimension sometimes has to increase at least twice. We also construct 2-dimensional LP-type problems with −∞ for which removing degeneracies forces arbitrarily large dimension increase
Publication en relation: Discrete & Computational Geometry. - 2009/42/4/517-526
Document hôte: Discrete & Computational Geometry
Identifiant: 10.1007/s00454-008-9085-7 (DOI)
• Article
Sélectionner

A Combinatorial Proof of Kneser'sConjecture*

Matoušek, Jiří
Combinatorica. - 2004/24/1/163-170
Disponible
Titre: A Combinatorial Proof of Kneser'sConjecture*
Auteur: Matoušek, Jiří
Description: Kneser's conjecture, first proved by Lovász in 1978, states that the graph with all k-element subsets of {1, 2, . . . , n} as vertices and with edges connecting disjoint sets has chromatic number n−2k+2. We derive this result from Tucker's combinatorial lemma on labeling the vertices of special triangulations of the octahedral ball. By specializing a proof of Tucker's lemma, we obtain self-contained purely combinatorial proof of Kneser's conjecture
Publication en relation: Combinatorica. - 2004/24/1/163-170
Document hôte: Combinatorica
Identifiant: 10.1007/s00493-004-0011-1 (DOI)
• Article
Sélectionner

Blocking Visibility for Points in General Position

Matoušek, Jiří
Discrete & Computational Geometry. - 2009/42/2/219-223
Disponible
Titre: Blocking Visibility for Points in General Position
Auteur: Matoušek, Jiří
Sujet: Visibility - Visibility-blocking set - Behrend's construction
Description: For a finite set P in the plane, let b(P) be the smallest possible size of a set Q, Q∩P=∅, such that every segment with both endpoints in P contains at least one point of Q. We raise the problem of estimating b(n), the minimum of b(P) over all n-point sets P with no three points collinear. We review results providing bounds on b(n) and mention some additional observations
Publication en relation: Discrete & Computational Geometry. - 2009/42/2/219-223
Document hôte: Discrete & Computational Geometry
Identifiant: 10.1007/s00454-009-9185-z (DOI)
• Article
Sélectionner

Near-Optimal Separators in String Graphs

MATOUŠEK, JIŘÍ
Combinatorics, Probability and Computing. - 2014/23/1/135-139
Disponible
Titre: Near-Optimal Separators in String Graphs
Auteur: MATOUŠEK, JIŘÍ
Sujet: Primary 05C62 - Secondary 05C10
Description: Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m)$ vertices
Publication en relation: Combinatorics, Probability and Computing. - 2014/23/1/135-139
Document hôte: Combinatorics, Probability and Computing
Identifiant: 10.1017/S0963548313000400 (DOI)
• Article
Sélectionner

New Constructions of Weak ε-Nets

Matousek, Jirí
Wagner, Uli
Discrete & Computational Geometry. - 2004/32/2/195-206
Disponible
Titre: New Constructions of Weak ε-Nets
Auteur: Matousek, Jirí
Contributeur: Wagner, Uli
Description: A finite set $N \subset \R^d$ is a {\em weak $\eps$-net} for an $n$-point set $X\subset \R^d$ (with respect to convex sets) if $N$ intersects every convex set $K$ with $|K\,\cap\,X|\geq \eps n$. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set $X$ in $\R^d$ admits a weak $\eps$-net of cardinality $O(\eps^{-d}\polylog(1/\eps))$. Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak $\eps$-nets in time $O(n\ln(1/\eps))$
Publication en relation: Discrete & Computational Geometry. - 2004/32/2/195-206
Document hôte: Discrete & Computational Geometry
Identifiant: 10.1007/s00454-004-1116-4 (DOI)
• Article
Sélectionner

A highly non-smooth norm on Hilbert space

Matoušek, Jiří
Matoušková, Eva
Israel Journal of Mathematics. - 1999/112/1/1-27
Disponible
Titre: A highly non-smooth norm on Hilbert space
Auteur: Matoušek, Jiří
Contributeur: Matoušková, Eva
Description: We show that there exists a familyF of unit balls in the Hilbert spacel 2 such that ∪F is dense inl 2 but the complement of ∪F is large in the sense of measure. In an appendix, we present a considerable simplification of the proof due to Preiss. As a corollary, we prove that there is an equivalent normp onl 2 such that the set of points wherep is Fréchet differentiable is Aronszajn null. This disproves a conjecture of Borwein and Noll in a very strong sense
Publication en relation: Israel Journal of Mathematics. - 1999/112/1/1-27
Document hôte: Israel Journal of Mathematics
Identifiant: 10.1007/BF02773476 (DOI)
• Plusieurs versions

The number of unit distances is almost linear for most norms

Matoušek, Jiří
Advances in Mathematics, 2011, Vol.226(3), pp.2618-2628 [Revue évaluée par les pairs]

• Article
Sélectionner

String graphs and separators

Matoušek, Jiří
arXiv.org, Apr 25, 2014
© ProQuest LLC All rights reserved, Engineering Database, Publicly Available Content Database, ProQuest Engineering Collection, ProQuest Technology Collection, ProQuest SciTech Collection, Materials Science & Engineering Database, ProQuest Central (new), ProQuest Central Korea, SciTech Premium Collection, Technology Collection, ProQuest Central Essentials, ProQuest One Academic, Engineering Collection (ProQuest)
Disponible
Titre: String graphs and separators
Auteur: Matoušek, Jiří
Contributeur: Matoušek, Jiří (pacrepositoryorg)
Sujet: Separators ; Graphs ; Graphical Representations ; Combinatorics ; Computational Geometry
Description: String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities.
Fait partie de: arXiv.org, Apr 25, 2014
Identifiant: 2331-8422 (E-ISSN)
• Article
Sélectionner

String graphs and separators

Matoušek, Jiří
Cornell University
Disponible
Titre: String graphs and separators
Auteur: Matoušek, Jiří
Sujet: Mathematics - Combinatorics ; Computer Science - Computational Geometry ; 05c62
Description: String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities. Comment: Expository paper based on course notes
Identifiant: 1311.5048 (ARXIV ID)
• Article
Sélectionner

A Geometric Proof of the Colored Tverberg Theorem

Matoušek, Jiří
Tancer, Martin, Wagner, Uli
Discrete & Computational Geometry. - 2012/47/2/245-265
Disponible
Titre: A Geometric Proof of the Colored Tverberg Theorem
Auteur: Matoušek, Jiří
Contributeur: Tancer, Martin; Wagner, Uli
Sujet: Convexity - Tverberg's theorem - Colored Tverberg theorem - Continuous motion
Description: The colored Tverberg theorem asserts that for every d and r there exists t=t(d,r) such that for every set C⊂ℝ d of cardinality (d+1)t, partitioned into t-point subsets C 1,C 2, ,C d+1 (which we think of as color classes; e.g., the points of C 1 are red, the points of C 2 blue, etc.), there exist r disjoint sets R 1,R 2, ,R r ⊆C that are rainbow, meaning that |R i ∩C j |≤1 for every i,j, and whose convex hulls all have a common point. All known proofs of this theorem are topological. We present a geometric version of a recent beautiful proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological methods. The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience
Publication en relation: Discrete & Computational Geometry. - 2012/47/2/245-265
Document hôte: Discrete & Computational Geometry
Identifiant: 10.1007/s00454-011-9368-2 (DOI)