We continue the study of the natural polytope $\mathcal{D}$ in $\mathbb{R}^{n+d}$ associated with the disjunction of a set of $n+1$ polytopes in $\mathbb{R}^d$, managed by $n$ binary variables. Already $\mathcal{D}$ had been characterized for arbitrary $n\geq 1$ and (i) $d\in\{1,2\}$, and (ii) for a broad generalization of hyper-rectangles. In both cases, the complete characterization employs full optimal big-M lifting. Here, we give a complete description of $\mathcal{D}$ for the case of $n=1$ and arbitrary $d$, when the (two) polytopes are arbitrary generalized cross polytopes. Furthermore, we characterize when our complete description employs only optimal big-M lifting. For $n>1$, we generalize the family of facet-describing inequalities used for $n=1$. Finally, we carry out some computational experiments demonstrating the value of our theoretical results.
We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{\ge0}^n$, we construct an $\epsilon$-Cover of the joint value set $\{(f_1(x), \dots, f_m(x)) : x \in {H}\}$ in the $\ell_\infty$-norm. This cover is of size $n^{O(\log(mn)/\epsilon^2)}$, provided the polynomials have constant range over the smallest $\ell_1$-ball inscribing ${H}$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest $\ell_1$-ball containing ${H}$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to ${H}$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli et al.· arXiv.org· 1 citation
We consider $0/1$ packing problems $\max\{c^T x \colon Ax \leq 1, \, x \in \{0,1\}^n\}$, with $A \in \mathbb{R}_{\geq 0}^{m \times n}$. A way to solve such problems is via tightening the linear programming relaxation $P$ with Gomory \emph{cutting-planes}. The Gomory-closure $P'$ of $P$ is the intersection of $P$ with all its cutting planes. The optimization problem over $P'$ is NP-hard. Mastrolilli (2020) has shown that for fixed ${\epsilon}>0$, the Lasserre hierarchy yields a polynomial-size convex but non-polyhedral extended formulation that approximates $P'$ up to a factor of $1+{\epsilon}$. Our main result is the construction of a polyhedral and polynomial extended formulation that approximates $P'$ with the same approximation guarantee. Our construction is based on first principles. Like Mastrolilli's approach, ours also applies to higher iterates $P^{(t)}$ for fixed $t$ and ${\epsilon}>0$. In contrast to an explicit construction, communication complexity provides an alternative way to describe extended formulations. Using this approach we obtain a quasi-polynomial polyhedral extended formulation for the above problem that is superior in some parameter regimes. To achieve this, we describe a communication protocol extending Yannakakis'protocol to decide whether the clique of Alice and the stable set of Bob intersect.
Friedrich Eisenbrand, S. Fiorini, Lars Rohwedder et al.· 0 citations
Put $q=r-1$, $t=k-1$, and $D=tq+1$. For an edge $e$ of a linear $C^r_{1,k}$-free $r$-uniform hypergraph, define \[ \delta_H(e)=\sum_{v\in e}\frac{1}{d_H(v)}-\frac{r}{D}. \] The defect satisfies $\delta_H(e)\ge 0$. At equality, every vertex of $e$ has degree $D$, and the petal trace at $e$ is a disjoint union of $t$ affine planes of order $q$. Equivalently, restoring the base line gives $t$ projective planes of order $q$ with common line $e$. For growing crowns, the equality structure is stable in the following sense. If $q_j\to\infty$, $2\le t_j\le q_j$, and $e_j$ is an edge of a finite linear $C_{1,t_j+1}^{q_j+1}$-free hypergraph satisfying \[ \frac{t_j^2}{q_j}\to0, \qquad t_j^3\delta_{H_j}(e_j)\to0, \] then, for every fixed $0<\theta<1$, \[ \frac{ |\{f\ne e_j:f\cap e_j\ne\varnothing,\ \delta_{H_j}(f)\ge\theta/t_j^2\}| }{(q_j+1)(t_jq_j)} \to1. \] Thus an edge close to equality is adjacent almost entirely to edges with defect of order at least $t_j^{-2}$. A uniform form gives absolute constants $Q_0,\varepsilon_0,c_0>0$ such that, whenever $q\ge Q_0t^2$ and $\delta_H(e)<\varepsilon_0/t^3$, at least $\tfrac12(q+1)tq$ neighbors of $e$ have defect at least $1/(100t^2)$. Consequently, \[ c^{\mathrm{lin}}_{q+1,t+1}\le t-\frac{c_0}{t}, \] where $c^{\mathrm{lin}}_{r,k}$ denotes the asymptotic linear Tur\'an coefficient for $C^r_{1,k}$.
A subset $S$ of a group $G$ is said to be sum-free (resp. $\Delta$-free) if there are no solutions to $a+b=c$ (resp. $a+b+c=0$) with $a,b,c\in S$. For a convex region $R\subset\mathbb{R}^d$, let $\sigma(R)$ denote the maximal proportion of the volume of $R$ that a sum-free subset of $R$ can occupy. We prove that $\sigma([-1,1]^d)=1/2$. Our proof employs a careful application of the Brunn-Minkowski inequality. Moreover, for the $d$-dimensional Euclidean ball $\mathbb{B}^d(0,1)$, we show that $\sigma(\mathbb{B}^d(0,1))\leq 1/2+o_d(1)$. We present two arguments for this. The first combines some routine harmonic analysis on the sphere with known bounds on values of the ultraspherical polynomials. The second more elementary argument proceeds by establishing that the maximal $\Delta$-free subset of the unit sphere $\mathbb{S}^{d-1}$ occupies $1/2+O(d^{-1})$ of the sphere's surface measure. This answers a question raised by Bukh.
A family $\mathcal{F}$ of subsets of $[n] := \{1,2,\ldots, n\}$ is called maximal $k$-wise intersecting if every collection of at most $k$ members of $\mathcal{F}$ has a non-empty intersection, and adding any other set to $\mathcal{F}$ breaks this property. An old question by Erd\H{o}s and Kleitman from 1974 asks for the minimum size of a maximal $k$-wise intersecting family. The case $k = 3$ is known for all sufficiently large $n$, but the problem remains open for all $k \geqslant 4$. The previous best-known upper bound is by Janzer, which has a leading term $(k-1)2^{k-3}2^{n/(k-1)}$ for sufficiently large $n$ divisible by $k-1$. In this note, we improve this bound to $(4k-10)2^{n/(k-1)}$, which reduces the dependence on $k$ in the leading coefficient from exponential to linear and is within a factor of $4$ of the known lower bound.
Let $P$ be a finite nonempty poset with $n$ elements, let $f:P\to\{1,\ldots,n\}$ be a uniformly random order-preserving bijection, and put $h_P(x)=\mathbb{E}[f(x)]$. Aires and Kahn (2025) introduced $\operatorname{gap}(P)$ as the largest difference between consecutive values in the ordered list consisting of $0$, $n+1$, and all the expected ranks $h_P(x)$. Write ${w}(P)$ for the largest size of a pairwise incomparable subset. We prove three results. First, we prove a weighted strengthening of an ideal inequality conjectured by Kahn and obtain the explicit gap-width bound $\operatorname{gap}(P)\le 2 {w}(P)-1$. Second, for every $L>0$ we construct a width-two poset such that the expected-rank list of every maximal chain has a gap of at least $L$, with $0$ and $|P|+1$ added as endpoints. Finally, for every $r\in\mathbb{N}$, we construct a poset $P_r$ for which the relative order induced on every nonempty selected set $X$ has base-two entropy below $3|X|$, while $\operatorname{gap}(P_r)\ge(3/2)^r$. Thus the gap can be arbitrarily large while the induced order on every selected set has relatively small entropy. The key ideas behind all three results were found by ChatGPT 5.6 Sol.
Alireza Haqi· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
