跳到正文
研踪PaperTrail

论文库

检索计算机领域论文，按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+93新增 AI 导读

arXiv 最近完成扫描：2026-11-16 01:34 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-15 02:07 — 2026-11-16 02:07（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-16 01:34最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

每分钟刷新已保存的数据。空检查不代表采集异常；新收录可能包含历史论文。AI 导读按新增版本计数。

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →

找到 206 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33（北京时间）
新论文 · v1arXiv:2611.12034

The Power of Migration on Identical Machines is Two

Nicole Megow, Bart Zondervan

原文摘要

We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on $m$ machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that $6m-5$ machines suffice and gave a polynomial-time construction using $12m-5$ machines, whereas $2m-1$ machines may be necessary. We close this gap, which has been open for more than 25 years: $2m-1$ machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on $m$ machines is $(2m-1)$-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe exchanges to compute a coloring in polynomial time. Second, we construct a supercanonical schedule with polynomially many processing blocks by shrinking job windows as far as possible while preserving feasibility and solving a min-cost flow problem.

cs.DS · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2501.12565

The Maximum Number of Sets for 12 Cards is 14

Justin Stevens, Duncan Wilson, Richard Kelley

原文摘要

We analyze a mathematical property of the popular card game SET. We present a revised geometric and computer-assisted proof that the maximum number of sets for 12 cards is 14 using finite field geometry, combinatorics, and graph theory. We present several computer algorithms for finding or approximating the maximum number of sets. We show a complete computer proof that iterates over all possible board configurations. We use this method to compute the maximum number of sets with 4 properties for a small number of cards, but it is generally too inefficient. With this method, we compute the maximum number of sets for 3 properties for all possible numbers of cards. Finally, we compare this to an existing approximation algorithm for finding maximal sets.

math.CO · cs.DM · math.NT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11444

Tight B-Trees for Adjacency Labeling

Noy Rotbart

原文摘要

We show that planar graphs admit adjacency labels of size $\log n+O(\log\log n)$: every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the $\log n+O(\sqrt{\log n\log\log n})$ of Dujmović et al. (J. ACM 2021) and the $\log n+O(\sqrt{\log n})$ of Gawrychowski and Janczewski (SOSA 2022). Equivalently, $n$-vertex planar graphs have an induced-universal graph with $n(\log n)^{O(1)}$ vertices, down from $n2^{O(\sqrt{\log n})}$. The same holds for graphs of bounded genus, apex-minor-free graphs and $k$-planar graphs. For every proper minor-closed class we get $\log n+O(\sqrt{\log n\log\log n})$, down from the $\log n+O((\log n)^{3/4})$ of Dujmović et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor $1\pm O(1/\log n)$ of its target size, and a root-to-leaf path loses only $O(\log\log n)$ bits.

cs.DS · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11376

Fractional distance-edge-monitoring in lexicographic products

Xiumin Wang, Minglei Mao, Yaping Mao, Ralf Klasing

原文摘要

We give an exact formula for the fractional distance-edge-monitoring number of $G\circ H$, where $G$ is connected of order $m\ge2$ and $H$ has order $n\ge2$. By the previously established endpoint-monitoring property, the fractional monitoring program reduces to fractional vertex cover, whose linear-programming dual is fractional matching. Writing $d_c(H)$ for the critical difference of $H$, we obtain $\operatorname{dem}_{f}(G\circ H)=(mn-D(G,H))/2$, where $D(G,H)=\max_{A\in\mathcal{I}(G)}\bigl(d_c(H)|A|-n|N_G(A)|\bigr)$ and $\mathcal{I}(G)$ denotes the family of all independent sets of $G$, including the empty set, while $N_G(A)$ is the open neighborhood of $A$. This formula characterizes the products attaining $mn/2$ and gives an equality criterion for the fractional matching lower bound of Ma, Cheng, Mao and Wang. Under the stated hypotheses, the lower bound of Ma et al. is attained if and only if either factor has a fractional perfect matching or $H$ is edgeless. Two outer trees show that the factor orders and fractional matching numbers do not determine the product value.

cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11375

Linear Objective Problems: A Complexity Framework for Bilevel Optimization

Christoph Grüne, James B. Orlin, Lasse Wulf

原文摘要

Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these elements. We define tight solution-embedding reductions, which map the optimal solutions of one problem element by element onto the optimal solutions of another, without having to recognize optimal solutions, which is coNP-hard in general. This gives a notion of LOP-completeness, with Satisfiability as the canonical complete problem, even with unit weights. We show that many classical problems are LOP-complete, including Vertex Cover, Dominating Set, TSP, Knapsack, and Steiner Tree, and we introduce a duality that transfers LOP-completeness between minimization and maximization problems. As our main application, we prove a meta-theorem for min-max regret optimization under interval uncertainty: for every LOP-complete problem, the min-max regret version is $Σ_2^p$-complete. Instead of a separate proof for each nominal problem, it suffices to show that the nominal problem is LOP-complete. This recovers known results for the interval min-max regret versions of Knapsack and Maximum Benefit Set Cover and yields completeness for over 50 further problems.

cs.CC · cs.DM · math.CO · math.OC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11280

Impropriety and resilience of the chromatic number

Ross J. Kang, Colin McDiarmid

原文摘要

We show that, for $p$ bounded away from $1$ and $np\to\infty$, the chromatic number of the binomial random graph $G_{n,p}$ is resilient to removal of a subgraph $H$ with $o(n \log(np))$ edges. It follows that the same assertion holds with $H$ being a subgraph of maximum degree $o(\log(np))$; and both these results are best possible up to a constant factor. We also prove corresponding results for the random $r$-regular graph $G_{n,r}$, when $r\to\infty$ and $r/n$ is bounded away from $1$, where $H$ has $o(n\log r)$ edges or maximum degree $o(\log r)$. Our results rely on a natural connection between chromatic resilience to edge removal and improper graph colouring. This work provides counterpoint to the work of Sudakov and Vu (2008) and Alon and Sudakov (2010), which treated chromatic resilience for $G_{n,p}$ subject to the addition, rather than removal, of edges.

math.CO · cs.DM · math.PR

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11126

Lower bound on the size of splitting systems

Fan Chung, Namiko Matsumoto, Arya Mazumdar

原文摘要

For even $t$ and an $n$-set $X$, an $(n,t)$-splitting system is a family ${\mathbb{B}} \subseteq 2^X$ with the property that for each subset $Y \in {X \choose t}$, there exists $B \in \mathbb{B}$ such that $|B \cap Y| = t/2$. The problem of interest is to determine the minimum size of such splitting systems. We show that any $(n,t)$-splitting system has size at least of order $t$, improving the previous lower bound of $\sqrt t$ while the best known upper bound is of order $t^{3/2}$.

math.CO · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.11093

Does Pose Encoding Matter? Analyzing Geometric Representations for Discrete Motion Vocabulary Learning

Amir Kimiyaie, Nahal Mafi, Hamed Tabkhi

原文摘要

Compressing continuous human motion into a finite vocabulary of discrete tokens is now the first stage of many motion understanding and generation pipelines. Vector quantization partitions a latent space into Voronoi cells around a finite codebook, but the geometry of that latent space is inherited from the input pose encoding, and it is unclear which encoding admits an efficient discretization. We study four encodings that place skeletal motion in different geometric spaces: Gaussian joint heatmaps on the pixel lattice, which we show to be a morphological dilation of the joint point set by a quadratic structuring function; root-relative joint positions in Euclidean space; local joint rotations on $\SO$ through a continuous 6D embedding; and a redundant full kinematic encoding. For each, we train VQ-VAE tokenizers whose codebooks lie on the unit hypersphere, varying codebook size, temporal stride, and code dimension. Beyond reconstruction, we measure codebook utilization and the effective vocabulary size, i.e., the number of equiprobable spherical Voronoi cells with the same entropy as the observed token distribution. Rotation and position encodings keep converting additional codewords into effective vocabulary, whereas the full kinematic encoding saturates at a few hundred effective cells and heatmaps at fewer than sixty. The smallest code dimension gives the highest utilization for three of the four encodings, and the effect of temporal stride depends on the encoding. Encodings of the same pose family can thus yield effective vocabularies differing by an order of magnitude, a difference that reconstruction loss alone does not reveal, which points to input geometry as a first-order design choice in motion tokenization.

cs.CV · cs.AI · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.17100

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

Yuan Li, Jing Zhang

原文摘要

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

math.CO · cs.CC · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.17006

Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces

Yuan Li, Jing Zhang

原文摘要

Rotation symmetric Boolean functions are important structured families in the theory of Boolean functions, where cyclic invariance permits compact algebraic descriptions while retaining nontrivial local behavior. We investigate their sensitivity through binary necklaces and monomial orbit sums. In the necklace quotient of the Boolean cube, ordinary adjacency does not record the number of coordinate flips: we give a directed flip-multiplicity formula involving stabilizers and distance-two near-periods, and derive exact local sensitivity formulas when the number of variables is an odd prime. For monomial rotation symmetric functions we determine sensitivity for all odd degrees and for quadratic orbit sums. For the consecutive-monomial family of every even degree $d\ge4$, we prove a run-cluster inequality and obtain the eventual exact formula $s(F_{d,n})=n-\min\{r,d+2-r\}$, where $n\equiv r\pmod{d+2}$, under the stated length hypothesis. The consecutive quartic case follows explicitly. We also evaluate sensitivity for cyclic run-threshold functions. Our results provide exact combinatorial and complexity-theoretic information about cyclic Boolean functions and clarify how cyclic symmetry governs local sensitivity.

math.CO · cs.CC · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.10920

Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational Functions

Fugen Hagihara

原文摘要

We study the positivity of sequences $f$ that satisfy a third-order holonomic recurrence $f(n+3)= P_2(n) f(n+2) + P_1(n) f(n+1) + P_0(n) f(n)$ whose coefficients $P_0$, $P_1$ and $P_2$ are rational functions in $\R(x)$. We provide a sufficient condition on $P_0$, $P_1$ and $P_2$ for the recurrence to admit a solution all but finitely many terms of which are positive, and whose positivity is robust under small perturbations of the initial values. This sufficient condition is also a necessary condition for a subclass of the recurrences. By developing the proof of this sufficient condition, for another subclass of the recurrences, we show that it is decidable whether all the terms of a given sequence are positive for any initial values outside an exceptional plane. It is common to construct a positivity certificate, which guarantees the positivity of a solution, to show this kind of decidability. In this paper, we construct a new type of positivity certificate via the $S$-scaled difference $f(n+1) - S(n) f(n)$ for a suitable $S \in \R(x)$. This result partially improves the work by Ibrahim and Salvy.

cs.DM · cs.SC · math.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2610.14099

Symmetric, rational and infinitely many $(23_4)$ configurations, and the end of the existence problem for geometric $(n_4)$ configurations

Wenhao Lu

原文摘要

A geometric $(n_4)$ configuration is a set of $n$ points and $n$ lines in the real projective plane such that every point lies on exactly four of the lines and every line contains exactly four of the points. The question of which $n$ admit such a configuration was posed by Grünbaum in 2000, and successive work of Bokowski, Grünbaum, Schewe, Pilaud and Cuntz settled every case but $n=23$. We settle this last case by bounding the symmetry of such configurations and classifying the most symmetric ones exactly. We prove that for every prime $n\equiv3\pmod4$ the group of projective symmetries of a geometric $(n_4)$ configuration has order at most four, explaining why symmetric constructions failed at $n=23$, and the same argument bounds the symmetry of $(n_5)$ configurations for primes $n\not\equiv1\pmod5$. Reducing the Klein four-group case to 4021 bilinear polynomial systems and solving all of them exactly with Gröbner bases, we show that exactly two $(23_4)$ configurations reach this bound up to projective equivalence and that there are no others even over $\mathbb{C}$. Both are self-polar; the first has integer coordinates and the second is defined over $\mathbb{Q}(\sqrt{17})$ but not over $\mathbb{Q}$. Consequently geometric $(n_4)$ configurations exist if and only if $n\ge18$ and $n\ne19$. The same classification recovers Cuntz's $(22_4)$ and $(26_4)$ configurations and finds three new combinatorial types at $n=22$ and $94$ at $n=26$. Among self-polar $(23_4)$ configurations with a single involution we find $50$ more, defined over number fields of degree at most $7$. Four of them deform in one-parameter families, and computing three of these exactly, one birational to the modular curve $X_1(11)$, we prove that there are infinitely many geometric $(23_4)$ configurations, among them infinitely many with rational coordinates that are self-polar and have no projective symmetry.

math.CO · cs.CG · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2606.29553

An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket

Chakshu Gupta

原文摘要

The independence number $α$ of a finite simple graph lies between the polynomial-time computable Havel-Hakimi residue $R$ and annihilation number $a$. The Caro-Wei sum $W$ gives another lower bound and the known upper bound $α\le(Δ+1)W/2$ for maximum degree $Δ\ge1$. This upper bound does not by itself control the larger quantity $a$. This note proves $a\le(Δ+1)W/2$ for $Δ\ge1$, with equality attained, for example, by regular graphs of positive degree and even order. Together with $R\ge W$, this bound shows that the interval from $R$ to $a$ improves or matches both Caro-Wei endpoints. Its sharp worst-case endpoint ratio remains $(Δ+1)/2$, even among connected graphs. For maximum degree at least three, the bound also proves the inequality $α\ge(a+R)/Δ$ conjectured by TxGraffiti, an automated conjecturing program. A direct calculation handles connected graphs of maximum degree two. Together these cases resolve the conjecture for every connected graph with at least three vertices. The single edge is the only nontrivial connected exception. Equality holds for exactly eight connected graphs up to isomorphism. For maximum degree at least three, the conjectured lower bound never exceeds the residue, so it gives no stronger independence estimate.

math.CO · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.10701

Weighted Matroid Intersection under Minimum Rank Oracle

Taihei Oki

原文摘要

We consider matroid intersection under the minimum rank oracle model, in which two matroids are accessible only through an oracle that returns the minimum of the ranks of a given set in the two matroids. By Edmonds' theorem, this oracle determines the matroid intersection polytope, although it does not reveal the exchangeability graphs on which classical algorithms rely. Recent work by Bárász, Bérczi, Király, Oki, Yamaguchi, and Yokoi (2025) showed that unweighted matroid intersection is polynomially solvable in this model. In this paper, we present a strongly polynomial-time algorithm for weighted matroid intersection in this model. The key to our algorithm is a polynomial-size extended formulation of tangent cones of common base polytopes that can be constructed using the minimum rank oracle. We also give min-max theorems in terms of the minimum rank function via 1/3-submodularity, and present a strongly polynomial-time algorithm to compute an optimal dual solution.

cs.DM · math.CO · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2505.06169

On the Depth of Monotone ReLU Neural Networks and ICNNs

Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, Amir Yehudayoff

原文摘要

We study two models of $\mathsf{ReLU}$ neural networks: monotone networks ($\mathsf{ReLU}^+$) and input convex neural networks ($\mathsf{ICNN}$). Our focus is on expressivity, mostly in terms of depth, and our motivation is to gain a better understanding of the depth required to exactly represent functions using neural networks with ReLU activations, a subject that has received a lot of attention lately. We prove several lower bounds on the depth required to represent functions by monotone ReLU networks and $\mathsf{ICNN}$. For the maximum function $\mathsf{MAX}_n$ computing the maximum of $n$ real numbers, we show that $\mathsf{ReLU}^+$ networks cannot compute $\mathsf{MAX}_n$, or even approximate it. We prove a sharp lower bound of $n-1$ on the $\mathsf{ICNN}$ depth complexity of $\mathsf{MAX}_n$. We also prove depth separations between $\mathsf{ReLU}$ networks and $\mathsf{ICNN}$s; for every $k$, there is a depth-$2$ $\mathsf{ReLU}$ network of size $O(k^2)$ that cannot be simulated by a depth-$k$ $\mathsf{ICNN}$. The proofs are based on deep connections between neural networks and polyhedral geometry, and also use isoperimetric properties of triangulations.

cs.LG · cs.DM · cs.NE · math.CO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.10624

A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel Scheduling

Hiroshi Fujiwara, Grzegorz Gutowski, Katsuhisa Ouchi, Alexander Wolff

原文摘要

In pinwheel scheduling with real periods, an instance consists of $n$ tasks with real periods $1\le a_1\le a_2\le\cdots\le a_n$. The goal is to find a schedule that assigns one task to each day indefinitely such that, for every task $i\in\{1,\dots,n\}$ and every positive integer $\ell$, task $i$ occurs at least $\ell$ times in every block of $\lceil\ell a_i\rceil$ consecutive days. Given an instance $(a_1,a_2,\dots,a_n)$, its dimension is $n$, its density is $\sum_{i=1}^n1/a_i$, and its potential is $\sum_{i=1}^{n-1}1/a_i$. We prove that every real-valued instance of density at most 5/6 admits a periodic schedule of period length less than $4\cdot2^n$. For integer periods, the 5/6 density bound was a long-standing conjecture settled by Kawamura using a computer-assisted proof [STOC 2024, PNAS 2026]. Our result confirms the real-period conjecture of Fujiwara, Miyagi, and Ouchi [DMTCS 2026]. Our computer-assisted proof builds on Kawamura's ideas while using fewer explicit schedules. It combines dimension reduction by folding with nine satisfiability modulo theories (SMT) checks over linear real arithmetic. A set of 14287 explicit periodic schedules contains a schedule for every instance of dimension at most 8 and density at most 5/6, and for every instance of dimension 9 and potential at most 5/6. Folding is used to reduce every instance of larger dimension and potential at most 5/6 to an instance of dimension 9 and the same potential bound. We also prove that every real-valued instance with minimum period at least 4 and density at most 17/20=0.85 admits a periodic schedule of period length less than $19\cdot2^n$. The density bound 17/20 is tight and improves the 0.84-bound of Mishra, Rho, and Kleinberg [arXiv 2025] for integer periods. It also resolves the $a_1=4$ case of Kawamura's 2025 conjecture that integer-valued instances of density at most $1-(a_1-1)/(a_1(a_1+1))$ are schedulable.

cs.DM · cs.DS · math.CO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.12613

Maximal Linear Arrangement is NP complete on Bipartite Graphs

Aparna Das, Jonathan Needleman

原文摘要

The linear arrangement of a simple graph $G = (V,E)$ is a bijective labeling $π$ of the vertices of $G$ to the set $\{1, \ldots, n\}$. The maximum linear arrangement ($\texttt{maxLA}$) problem is to determine whether $G$ has a labeling such that the sum of labels across $G$'s edges, $\sum_{uv \in E} |π(u) - π(v)|$, is at least a given value $k$. Minimum linear arrangement ($\texttt{minLA}$) is defined analogously. Both $\texttt{maxLA}$ and $\texttt{minLA}$ are known to be NP complete for general graphs. $\texttt{minLA}$ has shown to be NP complete for bipartite graphs by Evans and Shiloah in 1975. It has been an open problem whether the same holds for $\texttt{maxLA}$. In this paper we prove that $\texttt{maxLA}$ is NP complete for bipartite graphs.

cs.DM · math.CO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.10311

Up or down by half: a family of Collatz-type maps

Oleg Vasilyev

原文摘要

Each Collatz step changes a positive integer by roughly half: odd inputs go up and even inputs go down. We vary the directions while keeping the step size. Write x=2^m k (k odd), and let S be a set of positive integers. Define T_S(x)=(3x+1)/2 if m=0, 3x/2 if m is in S, and k otherwise. The map T_S^- differs only at odd x, which it sends to (x+1)/2. The usual Collatz map is T_emptyset. Assuming the independence of 2-adic valuations along odd-to-odd steps yields random-walk models with drifts (1+rho(S))log_2(3)-2 for T_S and rho(S)log_2(3)-2 for T_S^-, where rho(S) is an explicit series. Every T_S^- is contracting; T_S is contracting exactly when rho(S)<log_3(4/3), approximately 0.2619. We prove density results, classify interval sets S, and give a criterion ensuring every T_S^- orbit reaches 1 or (2,3). For seven contracting maps T_S, three with rho(S)=1/4 just below the threshold, computations show that every n<2^34 (n<1.668*10^10 for S={1}) reaches one of at most five cycles; stopping-time statistics match the model to 3-5 digits. We study branching maps, where any member of a family may be applied at each step. Boundedness of a family implies boundedness of each member; in particular, boundedness of {T_emptyset,T_{3}} would imply that no Collatz orbit diverges. For {T_emptyset,T_{1}}, a rule depending only on x mod 32 has positive drift (10/17)log_2(9/8) for almost every 2-adic starting point. Thus almost all n have reachable sets containing values larger than n^1.05; residues modulo 2^L, L<=10, cannot prove unboundedness. Finally, we define unified maps in which valuations also determine the direction at odd inputs. The cases x=1 mod 4 govern their behavior: if they go down, every block is dominated by the corresponding Collatz map (and a census finds only the cycles (1), (2, 3) and (3, 5) with smallest element below 10^9); if they go up, the maps behave like T_S.

math.DS · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.10139

The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution

David Gamarnik

原文摘要

The satisfiability conjecture was one of the most important open problems in discrete probability. It was resolved recently first by Carenini~\cite{GCarenini}, and shortly after by OpenAI~\cite{k-sat-OpenAI}, among other 370 problems solved by its internal model. The conjecture concerned the satisfiability property of random instances of the k-SAT problem. It posits the existence of a fixed value for the clause-to-variables ratio around which the probability that the formula is satisfiable drops sharply from nearly one to nearly zero as the ratio increases. While the case of large constant $k$ was resolved a decade ago by Ding, Sly and Sun~\cite{ding2015proof,ding2022proof} using the heavy machinery of the second moment method, the case of general $k$ eluded proof until ~\cite{GCarenini} and~\cite{k-sat-OpenAI}. In this short note we provide a ''human-friendly'' and detailed exposition of the OpenAI's resolution of the conjecture.

math.PR · cond-mat.stat-mech · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.09627

What remains of the planar induced minor conjectures?

Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski

原文摘要

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

cs.DM · cs.CC · cs.DS · math.CO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.00240

Bounded Relative Boundary Implies Narrow DNF Approximation

Chenghua Liu, Boning Meng

原文摘要

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

cs.CC · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.09533

Pangenome Peeling: Decomposing Weighted Adjacencies into Path-Forest Genomes

Alitzel López Sánchez, Jiazhen Leng, Natasha Ivanova, Lingling Jin, David Sankoff

原文摘要

One aspect of pangenome analysis that has received little attention is the recovery of the individual genomes that gave rise to a pangenome graph. While substantial effort has focused on constructing pangenomes from collections of genomes, the inverse problem remains largely unexplored: given a pangenome represented as a set of weighted adjacencies, can we reconstruct the constituent linear genomes that underlie it? Thus we introduce the pangenome peeling problem, which seeks to decompose a weighted adjacency graph into a collection of linear genomes whose combined adjacencies reproduce the observed edge weights. This problem is particularly relevant when considering ancestral pangenomes, where the graph structure may be known or inferred, but the underlying genomes are not. As a first step toward addressing this problem, we formally define pangenome peeling and derive a lower bound on the minimum number of genomes required to explain a given weighted adjacency graph. We then present two reconstruction methods: one based on the sequential addition of edges and a second based on extracting maximum-spanning-tree structures. Both methods produce genome collections that exactly explain the input adjacency data. To evaluate the recovered sets of genomes, we compare them to the set of input genomes using a maximum-weight matching framework based on the double-cut-and-join distance with indels. Here the maximum-spanning tree approach is superior, producing sets of constituent genomes close to the simulations while the sequential addition of edges approach yields constituent genomes increasingly divergent from the input as genomes sizes increase.

cs.DM · q-bio.GN

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2606.30118

Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards

Jung-hun Kim, Vianney Perchet

原文摘要

We study prophet inequalities for $n$ i.i.d. base rewards subject to multiplicative discounts across $S$ phases. For equal-length phases and a common discount factor $\widetildeγ$, we characterize the optimal competitive ratio of single-quantile policies as $n\to\infty$ with $S$ and $\widetildeγ$ fixed. The resulting sharp guarantee describes the dependence on the phase parameters: it recovers $1-1/e$ without discounting and approaches $1/2$ in the worst-case regime. We also establish a distribution-free comparison that bounds the discounted prophet by a fractional i.i.d. maximum with effective horizon $B$, the sum of the discount weights across all observations. The comparison yields acceptance probability $1/B$, determined only by the phase profile. This calibration attains the canonical optimum even among single-quantile policies that may choose their acceptance probability using the known base distribution. The comparison also gives guarantees for heterogeneous discounts and unequal phase lengths. A complementary optimal-stopping upper bound establishes the same limiting optimum of $1/2$ for arbitrary stopping rules in the canonical model. Finally, the same effective-horizon calibration sets acceptance probability $1-\widetildeγ$ under infinite-horizon geometric discounting. This explicit quantile rule attains Boshuizen's (1994) known optimal worst-case ratio $1/(1+\widetildeγ)$ without solving a Bellman equation.

cs.GT · cs.DM · cs.DS · econ.TH · math.OC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.25863

On Multi-label radio Labelings of Graphs

Olivier Togni

原文摘要

We propose and study a multi-labeling generalization of the $k$-radio labeling problem of graphs: given a graph $G$ and integers $k$ and $m$, assign to each vertex of $G$ a set of $m$ integer labels such that distinct labels assigned to a vertex differ by at least $k+1$, and the labels of any two distinct vertices $x$ and $y$ pairwise differ by at least $k+1-d(x,y)$, with $d(x,y)$ being the distance between vertices $x$ and $y$. We prove general bounds on the minimum span of such a labeling and more refined results for the case $k=1$. For paths and cycles, we derive sharp bounds on the minimum span when $k$ is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.

math.CO · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2411.02197

Matroid products via submodular coupling

Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Balázs Maga, Tamás Schwarcz

原文摘要

The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the tensor product is arguably the most important, which can be considered as an extension of the tensor product from linear algebra. However, Las Vergnas showed that the tensor product of two matroids does not always exist. Over the following four decades, matroid products remained surprisingly underexplored, regaining attention only in recent years due to applications in tropical geometry and the limit theory of matroids. In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids -- or, more generally, for submodular set functions. This operation can be viewed as a relaxation of the tensor product. Unlike the tensor product, however, we prove that a coupling always exists for any two submodular functions and can be chosen to be increasing if the original functions are increasing. As a corollary, we show that two matroids always admit a matroid coupling, leading to a novel operation on matroids. Our construction is algorithmic, providing an oracle for the coupling matroid through a polynomial number of oracle calls to the original matroids. We apply this construction to derive new necessary conditions for matroid representability and establish connection between tensor products and Ingleton's inequality. Additionally, we verify the existence of set functions that are universal with respect to a given property, meaning any set function over a finite domain with that property can be obtained as a quotient.

math.CO · cs.DM

查看论文
arXiv ↗PDF ↗
版本更新 · v23arXiv:1107.3279

Probabilistic Methods on Erdos Problems

Jesse Gilbert

原文摘要

Probability distributions and the rules of inclusion-exclusion apply to derive general results about graph theory and number theory. In order to apply the rules of inclusion-exclusion in the setting some of these problems require, it is necessary to use specific equations and make several assumptions about integration and measure of the probability distributions.

cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.09071

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi

原文摘要

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

cs.DS · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.09020

Reconfiguration of Time-Bounded Descriptions

Dimitrios Myrisiotis

原文摘要

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

cs.CC · cs.DM

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.08835

Containment Problems in Convex Sets

Prosenjit Bose, Bobby Miraftab, Tyler Tuttle

原文摘要

Let $P$ be a set of $n$ points in the plane, and let $C$ be a compact, convex subset of the plane that contains the origin in its interior. We study the problem of finding two points $p$ and $q$ of $P$ with the property that any homothet of $C$ that contains $p$ and $q$ must contain at least a constant fraction of the points of $P$. We give proofs for several cases. When $C$ is strictly convex we achieve a fraction of $1/5$, and when $C$ is a general convex region we achieve a fraction of $1/6e$. We show how the ideas of this second bound can be used to prove a lower bound for a version of the problem in $\mathbb{R}^d$ when $C$ is a $d$-ball. We also consider a few special cases. When $C$ is a triangle we get a lower bound of $1/12$, and when we allow that triangle to be rotated by $π$ radians in addition to being scaled and translated we get a lower bound of $1/768$. In proving this last result, we improve the state of the art on the version of this problem in three dimensions, where $C$ is a parallelepiped. We also consider the algorithmic aspects of finding such a pair of points.

cs.CG · cs.DM · math.CO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.08416

基于平衡分歧的低温度采样

Low-Temperature Sampling via Equilibrium Disagreements

Andreas Galanis, Daniel Stefankovic

AI 速读 基于摘要

提出利用同一相内两个独立构型的分歧几何来刻画相内收敛的新框架，并在随机正则图上为硬核、随机簇和铁磁Ising模型给出相内快速混合的保证。

cs.DM · cs.DS · math.PR

arXiv ↗PDF ↗
查看原文摘要

We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite $d$-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the non-uniqueness regime $λ>λ_c(d)$. --- For the random-cluster model on random $d$-regular graphs, for every real $q>2$, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in $n^{3/2+o(1)}$ steps for all $β\geq β_c$. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in $n^{3/2+o(1)}$ steps for $β\leq β_c$. --- For the ferromagnetic Ising model on random $d$-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in $n^{3/2+o(1)}$ steps throughout the low-temperature regime $β>β_c(d)$. We also give an $n^{2+o(1)}$-time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.