Zobrazeno 1 - 10
of 408
pro vyhledávání: '"Cardinal, Jean"'
We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watchman routes that guard the facets of a polytope. We consider the exist
Externí odkaz:
http://arxiv.org/abs/2411.02172
We survey the complexity class $\exists \mathbb{R}$, which captures the complexity of deciding the existential theory of the reals. The class $\exists \mathbb{R}$ has roots in two different traditions, one based on the Blum-Shub-Smale model of real c
Externí odkaz:
http://arxiv.org/abs/2407.18006
Autor:
Cardinal, Jean
We consider the complexity of the recognition problem for two families of combinatorial structures. A graph $G=(V,E)$ is said to be an intersection graph of lines in space if every $v\in V$ can be mapped to a straight line $\ell (v)$ in $\mathbb{R}^3
Externí odkaz:
http://arxiv.org/abs/2406.17504
Autor:
Cardinal, Jean, Pilaud, Vincent
Rectangulations are decompositions of a square into finitely many axis-aligned rectangles. We describe realizations of $(n-1)$-dimensional polytopes associated with two combinatorial families of rectangulations composed of $n$ rectangles. They are de
Externí odkaz:
http://arxiv.org/abs/2404.17349
Autor:
Cardinal, Jean, Pournin, Lionel
The expansion of a polytope is an important parameter for the analysis of the random walks on its graph. A conjecture of Mihai and Vazirani states that all $0/1$-polytopes have expansion at least 1. We show that the generalization to half-integral po
Externí odkaz:
http://arxiv.org/abs/2402.14343
A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes
Externí odkaz:
http://arxiv.org/abs/2402.01483
Given a function $f$ from the set $[N]$ to a $d$-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of $f$, without explicitly storing it. We show that, if $f$ is of the form $[N
Externí odkaz:
http://arxiv.org/abs/2311.12471
Autor:
Cardinal, Jean, Steiner, Raphael
Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form $\mathbf{e}_i - \mathbf{e}_j$. We consider the following computational problem: Given two vertices of a generalized
Externí odkaz:
http://arxiv.org/abs/2311.00779
In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. Firstly, we describe Gray codes
Externí odkaz:
http://arxiv.org/abs/2212.03915
Autor:
Cardinal, Jean, Sharir, Micha
In the classical linear degeneracy testing problem, we are given $n$ real numbers and a $k$-variate linear polynomial $F$, for some constant $k$, and have to determine whether there exist $k$ numbers $a_1,\ldots,a_k$ from the set such that $F(a_1,\ld
Externí odkaz:
http://arxiv.org/abs/2212.03030