跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

arXiv 最近完成扫描:2026-11-22 14:51 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-21 16:09 — 2026-11-22 16:09(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-22 14:51最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

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

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

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

找到 307 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-22 14:49(北京时间)
版本更新 · v3arXiv:2502.07769

禁用子图复杂性框架 V:超越简单图

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs

Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith

AI 速读 基于摘要

将 C123 框架推广到允许自环和多边的伪图,并利用多个测试问题揭示伪图与简单图在禁用子图类上的复杂性差异。

math.CO · cs.CC

查看原文摘要

We investigate how allowing self-loops and multi-edges (i.e. moving from simple graphs to pseudographs) impacts the complexity of graph problems on finitely defined monotone graph classes. We do this by extending the C123-framework beyond simple graphs. We use several testbed problems to illustrate some of the new and varied behaviours introduced by the transition to pseudographs. We show that Pseudograph Matching Cut and Pseudograph d-Cut are C123-problems. Consequently, for every finite set HH of simple graphs, we obtain a complete complexity classification for these problems on HH-subgraph-free graphs. This sharply contrasts with their simple-graph counterparts, which are not C123-problems and their complexity remains open even for classes defined by a single forbidden subgraph H. We also show that Pseudograph Stable Cut is not a C123-problem. Nevertheless, for graph classes defined by a single forbidden subgraph, the problem mirrors the C123 classification; this correspondence already fails for sets of size 2. This gives the first example of a problem that aligns with C123-problems for a single forbidden subgraph but not for larger sets. Motivated by the interpretation of Stable Cut as a surjective homomorphism to a partially reflexive path, we also study surjective homomorphisms to partially reflexive cycles on k vertices with one irreflexive vertex. These problems share structural similarities with Pseudograph Stable Cut. We prove that for k at least 6, they are NP-complete on triangle-free pseudographs. However, unlike Pseudograph Stable Cut, they are polynomial-time solvable on all graph classes with bounded-degree.

新论文 · v1arXiv:2611.23109

去随机化向日葵引理与根式下界

Derandomized Sunflowers and Radical Lower Bounds

Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff

AI 速读 基于摘要

作者通过矩方法证明O(w)阶独立分布下的去随机化稳健向日葵引理,并据此构造显式多项式族,得到非单调算术电路与单调电路根式之间更强的分离。

cs.CC · math.CO

查看原文摘要

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for $O(w)$-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials $P_n$ that have small non-monotone arithmetic circuits such that any power of $P_n$ cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

版本更新 · v3arXiv:2604.17509

Rado's covering problem for cubes and balls: a survey

Gian Maria Dall'Ara, Adrian Dumitrescu

原文摘要

What is the largest constant $c\in [0,1]$ with the property that every finite collection $\mathcal{C}$ of axis-parallel squares in the plane admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $c$ of the area covered by $\mathcal{C}$? This problem was first raised by T.~Radó in 1928, who was motivated by a classical covering lemma in real analysis due to Vitali. R.~Rado later generalized the problem from axis-parallel squares in the plane to homothetic copies of any given convex body $K$ in $\mathbb{R}^d$, where now we are looking for an optimal constant $F(K)$. In this paper we survey the literature on this problem, with a focus on the case where $K$ is a cube or a ball in the high-dimensional regime $d\rightarrow \infty$. The estimates that we currently have for cubes are much more precise than those for balls: namely if $Q^d$ is a $d$-dimensional cube, then \[ (e^{-1}+o(1))\frac{2^{-d}}{d \log{d}} \leq F(Q^d)\leq 2^{-d}, \] while denoting $B^d$ a $d$-dimensional Euclidean ball, then \[ 2.910^{-d} \leq F(B^d) \leq 2.447^{-d}.\] Except for the upper bound for cubes, which is classical, the other estimates are due to the authors.

math.MG · cs.DM · math.CA · math.CO

新论文 · v1arXiv:2611.22780

Heap-type permutation generation with a prescribed final arrangement

Luís M. S. Russo

原文摘要

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

math.CO · cs.DM · cs.DS

新论文 · v1arXiv:2611.22760

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou

原文摘要

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

math.CO · cs.DM

版本更新 · v2arXiv:2610.03704

Non-isomorphic graphs have distinct vertex-Ramsey classes

Maria Axenovich, Patrick Schmitteckert

原文摘要

For a graph $H$, its $k$-colour vertex Ramsey class is the set of all graphs $G$ such that any colouring of the vertices of $G$ in $k$ colours results in a monochromatic (induced) copy of $H$. We prove that for any $k$, the $k$-colour vertex Ramsey classes of any non-isomorphic graphs are distinct. Moreover, we show that this property does not hold when individual graphs are replaced with families of graphs.

math.CO · cs.IT

新论文 · v1arXiv:2611.22552

On (Pathwidth, Clique)-boundedness

Amir Nikabadi

原文摘要

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

math.CO · cs.DM

新论文 · v1arXiv:2611.22205

More lower bounds for Hales--Jewett and van der Waerden numbers

Younes Mouhib

原文摘要

We give explicit colourings improving the comparison lower bounds assembled here for several Hales--Jewett and van der Waerden numbers. The main algebraic tool generalises Rabung's power-residue colouring from arithmetic progressions to arbitrary sets. If every translate of a t-element set S in F_p meets at least two classes of the r-th power character, and the integer weights have both parities, then a period-2p one-weight colouring of [t]^p has no monochromatic combinatorial line. The 19 displayed algebraic certificates comprise 18 improvements and one closed-form reproduction; they include HJ(4,3)>=164, HJ(5,4)>=7418, and HJ(5,6)>=34034. The underlying period-p construction also proves kappa_ow(t,r)>=p-1 for the one-weight bracket ceiling, in particular kappa_ow(5,4)>=7416 and kappa_ow(5,6)>=34032. Warm breakout-weighted tabu search on the type simplex gives HJ(3,4)>=51. Whole-colouring local search gives W(8,3)>522, W(11,3)>1193, and W(17,3)>3620. All accepted certificates are available separately and are checked by direct enumeration; unresolved searches are reported as UNKNOWN, not UNSAT.

math.CO · cs.DM

新论文 · v1arXiv:2611.22023

Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

Daniel Skachkov, Yuriy Dorn

原文摘要

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a $(1-\varepsilon)$-approximation within $\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ))$ steps with probability at least $1-δ$. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size $r$ in at most $2r$ moves, with temporary loss $O_H(\sqrt r)$. We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

cs.DS · math.CO

新论文 · v1arXiv:2611.21966

Supersaturation and reconfiguration diameter of independent transversals

Wouter Cames van Batenburg, Penny Haxell, Ross J. Kang, Ronen Wdowinski

原文摘要

Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree $Δ$. It is a classic result that when all parts have size at least $2Δ$, the collection is nonempty. Recently, it was found that if the parts have size at least $2Δ+1$, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least $2Δ$, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least $4Δ$.

math.CO · cs.DM

新论文 · v1arXiv:2611.23333

Classification of Forbidden 0-1 Patterns by Their Extremal Function

Jesse Geneson, Seth Pettie

原文摘要

This paper concerns the maximum weight of $n\times n$ 0-1 matrices that avoid some pattern $P$, denoted $\operatorname{ex}(n,P)$. Furedi and Hajnal initiated a research program of classifying all patterns according to their extremal function, but to date, only the weight-4 patterns are completely understood. In this paper we make progress on several fronts of the classification problem. A pattern is light if its columns have weight 1 and linear if $\operatorname{ex}(n,P)=O(n)$. We characterize the set of weight-5 linear light patterns, and the set of weight-5 linear patterns more generally. Along the way we identify several new infinite classes of linear patterns, which support the Pettie-Tardos conjecture on characterizing all linear light patterns. It was known that there exist infinitely many minimally nonlinear patterns. We identify a specific infinite set of minimally nonlinear patterns. We also prove that there are $2^{Ω(r)}$ weight-$r$ minimally nonlinear patterns, and that every minimally nonlinear pattern has extremal function $O(n\log n)$, with the exception of the 4-cycle. We classify many of the outstanding weight-5 patterns according to their extremal function, leaving only a small set remaining. The newly classified weight-5 patterns have extremal function $Θ(n)$ or $Θ(nα(n))$. We also exhibit a large number of weight-6 patterns with extremal function $Θ(n\log n/\log\log n)$, which is notable in that this function had not been encountered before for any single pattern $P$, though it was known to be the correct extremal function for a pair of forbidden patterns.

math.CO · cs.DM

新论文 · v1arXiv:2611.21913

An upper bound on non-overlapping codes

Simon R. Blackburn

原文摘要

Non-overlapping codes (also known as bifix-free codes or strong comma-free codes) have now been studied for over 60 years as part of information theory, with regular new applications appearing and much recent interest. Let $X$ be a binary non-overlapping code of length $n$. The paper contains a self-contained proof that \[ |X|\leq \left(\frac{5}{6e} +O(n^{-1})\right)\frac{2^n}{n} \] as $n\rightarrow\infty$. This improves, by a factor of $5/6$, the best previously known bound due to Levenshtein (1970). The paper builds on work by Fimmel, Michel, Pirot, Sereni and Strüngmann (2019), and by Stanovnik, Mo\v skon and Mraz (2024).

cs.IT · math.CO

版本更新 · v5arXiv:2609.30302

Hull Games of Induced Path Convexities in Graphs

Eurinardo Costa, Leon Almeida, Rudini Sampaio

原文摘要

In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_k}$ in the path $P_n$ if and only if $n$ is odd and she wins in the cycle $C_n$ if and only if $n=3$ or $n=α\cdot (k+1)-1$ with $α\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_k}$ in $P_n$ and in $C_n$ are periodic and Alice loses (resp. wins) in $P_n$ (resp. $C_n$) with $n>k$ only when $n=3k+4$ (resp. $n\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_2}$ in paths $P_n$ is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of $n$ up to $200$ million.

cs.DM · math.CO

版本更新 · v2arXiv:2608.11056

Twisted Conjugacy and the Construction of Induced Centrosymmetric Alternant Codes

Ousmane Ndiaye, Massamba Sow

原文摘要

This paper presents a construction of induced centrosymmetric alternant codes based on the automorphism structures inherited from Generalized Reed-Solomon (GRS) codes. We introduce a twisted conjugacy relation naturally arising from projective semilinear transformations and establish its connection with ordinary conjugacy in the corresponding projective semilinear coset. By means of the Shintani norm, we show that, in the quadratic extension case, all admissible transformations inducing centrosymmetry have a trivial Shintani norm and therefore belong to a unique conjugacy class in the semilinear coset. We further characterize the explicit forms of these transformations and establish a transport theorem describing how twisted conjugation acts on the supports and multipliers of GRS codes. These results provide an algebraic framework for constructing and analyzing induced centrosymmetric alternant codes.

cs.IT · math.CO

新论文 · v1arXiv:2611.21540

完全图最小生成树中叶子权重之和

The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph

Julia Gaudio, Phawin Prongpaophan, Miklós Z. Rácz

AI 速读 基于摘要

研究随机加权完全图的最小生成树中与叶子关联的边权重之和,确定其期望极限并证明集中性,进而改进Steiner树和概率最小生成树问题的上界。

cs.DM · math.CO

查看原文摘要

Let $G_n$ be a random weighted complete graph on $n$ vertices, where edges have i.i.d. $\text{Unif}(0,1)$ weights. Let $T_n$ be the Minimum Spanning Tree (MST) of $G_n$. The expected weight of $T_n$ is known to converge to $ζ(3) = \sum_{k=1}^{\infty} \frac{1}{k^3}$ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of $T_n$, denoting this quantity by $L_n$. We give tight upper and lower bounds on $\mathbb{E}[L_n]$ and determine its limit as $n$ diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of $L_n$ around $\mathbb{E}[L_n]$ and almost sure convergence to this value. These results directly yield substantial improvements to state-of-the-art bounds for two important variants of the MST problem: (1) an improved upper bound on the weight of the optimal random instance Steiner tree, as studied by Bollobás, Gamarnik, Riordan, and Sudakov (2004); and (2) an improvement over the upper bound for the Probabilistic Minimum Spanning Tree, introduced by Bertsimas (1988).

版本更新 · v2arXiv:2611.15992

The multiplicative complexity of the three-bit low-half multiplier

Bshara Alhodali, Gregory Morse

原文摘要

We prove that the multiplicative complexity of the three-bit low-half multiplier is six, giving a structural, enumeration-free lower-bound proof valid against unrestricted nonlinear reuse in Boolean XOR-AND circuits. The value was first established by SAT searches of the first author and independently confirmed by the second author. An explicit six-AND circuit supplies the upper bound. The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. Independent finite checks accompany the arguments. $\mathrm{MC}(M_3)=6$ is fully formalized in Lean 4, using only Lean's three standard axioms (propositional extensionality, choice and quotient soundness).

cs.CC · cs.LO · math.CO

新论文 · v1arXiv:2611.21416

Polynomial bounds for quasiplanar graphs

Aleksa Milojević, Patryk Morawski, Benny Sudakov, Istvan Tomon

原文摘要

A graph $G$ is $k$-quasiplanar if it can be drawn in the plane without $k$ pairwise crossing edges. It was a longstanding conjecture that $n$-vertex $k$-quasiplanar graphs have $O_k(n)$ edges. This was recently resolved by Sadhu and, independently, by Pach, Tardos, and Zeng, based on a theorem in topology proven by Beeker and Lazarovich. These papers showed that $k$-quasiplanar graphs have at most $k^{O(k)}n$ edges. In this note, we greatly improve the dependence on $k$ and show that every $k$-quasiplanar $n$-vertex graph has at most $O(k^2n)$ edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.

math.CO · cs.CG

版本更新 · v3arXiv:2402.18537

On the enumeration of signatures of XOR-CNF's

Nadia Creignou, Oscar Defrain, Frédéric Olive, Simon Vilmin

原文摘要

Given a CNF formula $\varphi$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $σ_\varphi(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $\varphi$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=0$ otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

cs.DS · cs.DM · math.CO

新论文 · v1arXiv:2611.21256

Odd faces as a parameter for maximum independent set in embedded graphs

Samuel Fiorini, Stefan Kober, Caleb McFarland

原文摘要

We give a polynomial-time algorithm for finding a maximum weight independent set in a graph embedded in a surface of bounded genus and with a bounded number of vertex-disjoint odd faces. In particular, we obtain an algorithm for graphs with an even-faced embedding in a torus and for planar graphs with a bounded number of odd faces, answering a question of Thomassé (2018) and a question of Choi, Gorsky, Kim, McFarland, and Wiederrecht (2025) respectively. We reduce the original problem to finding a minimum cost non-negative integer circulation with homology constraints in the dual of a certain double cover of the original graph.

math.CO · cs.DM · cs.DS · math.OC

版本更新 · v2arXiv:2603.27655

Exact Algorithms for Edge Deletion to Cactus

Sheikh Shakil Akhtar, Geevarghese Philip

原文摘要

We study two related problems on simple, un-directed graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general graphs at least since 1988. We show improved exact algorithms for the former and a polynomial time algorithm for the latter.

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

版本更新 · v2arXiv:2609.35186

Elections, Fractional Dichromatic Number and Domination in Tournaments and Digraphs

Paul Colinot, Alantha Newman

原文摘要

The dichromatic number of a digraph is the minimum number of induced acyclic sets into which its vertex set can be partitioned. The fractional dichromatic number is its fractional relaxation. Bourneuf, Charbit and Thomassé showed that the domination number of a tournament can be bounded as an (exponential) function of its fractional dichromatic number. This naturally leads to the question of finding a polynomial bound. We show that this bound is linear. To do this, we show a connection between undominated sets in elections and dominating sets in tournaments with bounded fractional dichromatic number. Within this framework, we also connect the well-known question of the existence of small Condorcet winning sets in elections to domination problems in digraphs with fractional dichromatic number less than 2. Thus, we open a new path to investigating these popular open problems in social choice from the perspective of graph theory.

math.CO · cs.DM

新论文 · v1arXiv:2611.21210

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

Florent Foucaud, Yan Gerard, Christian Laforest, Le Vu Pham

原文摘要

A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. Hedetniemi and Rall asked for the largest constant $c$ with $\mathrm{ud}^*(T) \geq c \cdot n$ for every tree $T$ of order $n$. We answer their question: the constant is $4/5$, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study $\mathrm{ud}^*$ under each of the two requirements separately, giving the Full-Cover variant $\mathrm{ud}^*_0$ and the Non-Overlapping variant $\mathrm{ud}^*_+$. The two behave very differently: on arbitrarily large graphs $\mathrm{ud}^*_0$ may remain bounded by a constant, whereas $\mathrm{ud}^*_+$ always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds $\lceil \sqrt[c]{n} \rceil$ and $4\sqrt{n}$, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

cs.DM · math.CO

新论文 · v1arXiv:2611.21187

A Polynomial Time Algorithm for Finding a Minimum 5-Partition of a Submodular Function

Yuhao Liu, Ke Shi, Chao Xu

原文摘要

Given a real-valued submodular function on a finite ground set, the minimum $k$-partition problem asks for a partition into $k$ nonempty parts minimizing the sum of their function values. We give a polynomial-time algorithm for $k=5$. The idea follows directly from the previous $k=4$ result, where there is precisely one obstruction for generalizing it to $k=5$. We show the special case can be handled by reasoning about a restricted family of $3$-partitions.

cs.DS · math.CO

新论文 · v1arXiv:2611.20804

A Recursive Construction of Perfect Arrays of Every Shape $2^{a_1}\times\cdots\times2^{a_d}$ over the Unit Quaternions

Sam Blake

原文摘要

We extend the recursive construction of perfect and odd perfect sequences over the simple unit quaternions $\Qe=\{\pm1,\pm i,\pm j,\pm k\}$ of Blake to arrays of any dimension. The three operations of that construction act on one direction of an array at a time, and are valid whenever the array is periodic in the remaining directions. Starting from a perfect array $P$ of shape $M_2\times\cdots\times M_d$ they give perfect arrays of shape $2^a\times M_2\times\cdots\times M_d$ for every $a\ge0$, with explicit index functions and with the array orthogonality property for the divisor $2$ in the lifted direction; from $a=5$ on these arrays are, in general, Kronecker products of a sequence with $P$ in neither order. Applied direction by direction, the construction gives perfect arrays over $\Qe$ in every shape $2^{a_1}\times\cdots\times2^{a_d}$, and in every shape $2^{a_1}\times\cdots\times2^{a_{d-1}}\times N$ for which a perfect sequence of length $N$ over $\Qe$ exists. The contrast with the binary alphabet is sharp: a perfect binary array of shape $2^{a_1}\times\cdots\times2^{a_d}$ exists only when $\sum a_k$ is even and $\max a_k\le\frac12\sum a_k+1$, by a theorem of Jedwab and Kraemer on Menon difference sets in abelian $2$-groups, whereas over $\Qe$ there is no constraint on the shape. We also show that, unlike the one-dimensional case, single arrays carrying a non-central twist do exist in two dimensions, and determine where the one-dimensional non-existence argument breaks.

cs.IT · math.CO

新论文 · v1arXiv:2611.20784

On homogeneous hypertournaments

Matěj Konečný

原文摘要

Sullivan recently constructed continuum many countable homogeneous $n$-hypertournaments for every $n\ge3$ by forbidding configurations he calls pair-cancelling. We show that, for every family $\mathcal F$ of pair-cancelling $n$-hypertournaments, the class of all linearly ordered finite $\mathcal F$-free $n$-hypertournaments is Ramsey and has the ordering property. In particular, freely ordered $\mathbf{H}_4$-free $3$-hypertournaments are Ramsey, answering a question of Cherlin, Hubička, Nešetřil, and the author from 2021. For every odd $n\ge3$, we give a simple Ramsey expansion with the expansion property for even $n$-hypertournaments by naming an $(n-1)$-hypertournament and a free linear order. We also show that, for $n\ge6$, no unbounded hereditary strong amalgamation class of finite $n$-hypertournaments has EPPA. Moreover, we prove the failure of EPPA for all Sullivan's classes with $n\ge4$, and for the even $5$-hypertournaments. We conjecture that even hypertournaments and classes omitting a family of pair-cancelling hypertournaments, together with the homogeneous cyclic order in arity three, are the only countably infinite homogeneous $n$-hypertournaments for $n\ge3$. We give some supporting evidence.

math.CO · cs.DM · math.LO

版本更新 · v2arXiv:2609.05771

Moments of crosscorrelation demerit factors of binary sequences

Daniel J. Katz, Harmony M. Vargas

原文摘要

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar. The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor. For each positive integer $\ell$, we endow the $2^{2 \ell}$ pairs of binary sequences of length $\ell$ with uniform probability measure and study the distribution of their crosscorrelation demerit factors. Sarwate showed that the mean value is always $1$ regardless of length $\ell$. We develop a method for finding an exact formula for the $p$th central moment (for any positive integer $p$) as a function of $\ell$. Formulae for the variance and third central moment ($p=2$ and $3$) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations. Our theory also shows that all the central moments must be strictly positive for $p\geq 2$ and $\ell \geq 3$.

cs.IT · cs.DM · eess.SP · math.CO · math.PR

新论文 · v1arXiv:2611.20554

$L$-systems on the large Witt design

Toshihiro Shimizu, Norihide Tokushige

原文摘要

Let $L=\{0,1,2,3,4,8\}$, associated with the large Witt design $S(5,8,24)$, and let $m(n,24,L)$ be the maximum size of a family of $24$-element subsets of an $n$-element set whose distinct members have intersection sizes in $L$. We prove that there are positive constants $c,C,n_0$ such that, for every $n\geq n_0$, \[ cn^{316/63}\leq m(n,24,L)\leq Cn^{169/29}. \] We also obtain similar results for the systems associated with $S(4,7,23)$, $S(3,6,22)$, and $S(3,4,14)$. The upper bounds follow from a non-Shannon information inequality and disprove conjectures of Kupavskii and Terekhov. The lower bounds follow from an algebraic construction for arbitrary Steiner systems.

math.CO · cs.IT

新论文 · v1arXiv:2611.20504

A proof of a conjecture on bipartite correspondence packing

Xin Zhang

原文摘要

A correspondence cover assigns a set of possible colors to each vertex of a graph. For each edge, a matching between the two endpoint color sets specifies the forbidden color pairs. A correspondence coloring selects one color at each vertex so that no forbidden pair is selected. A full correspondence packing is a collection of such colorings that uses every color at each vertex exactly once. We prove a conjecture of Cambie, Cames van Batenburg, Davies, and Kang [Random Structures & Algorithms 64 (2024), 62--93]. For every sufficiently large $D$, there is a positive integer $k(D)=(1+o(1))D/\log D$ such that every correspondence cover of any finite bipartite graph has a full correspondence packing if each color has at most $D$ forbidden partners and each vertex has $k(D)$ colors. More precisely, we prove this conclusion with \[ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil \] for every integer $D\ge\lceil e^{20}\rceil$.

math.CO · cs.DM

新论文 · v1arXiv:2611.20346

Canonical activation patterns and ReLU pattern varieties

Bella Finkel, Yaoying Fu, Chenxi Wu

原文摘要

A ReLU pattern variety records the polynomial relations among the coefficients of the affine maps associated with a prescribed set of activation patterns of a ReLU network. We study how the combinatorics of the canonical set of activation patterns of an unbiased ReLU network is reflected in the geometry of its pattern variety. In particular, we introduce the notion of pattern stability and characterize pattern stability and combinatorial stability for shallow networks. When the associated wall graph is connected and contains an edge of every neuron label, we resolve a problem of Alexandr and Montúfar by determining the defining ideal of the associated pattern variety explicitly. We establish a hierarchy of progressively weaker equivalence relations relating labeled combinatorial equivalence, equality and permutation equivalence of canonical pattern sets, and equivalences of the associated varieties. Finally, we relate functional dimension to the differential of the pattern map and show that it is bounded above by the dimension of the canonical pattern variety at every depth. For nondegenerate shallow networks, we give an exact formula for the functional dimension; for every shallow architecture, it equals the dimension of the canonical pattern variety on an open dense set of full Lebesgue measure.

math.CO · cs.LG · math.AG

新论文 · v1arXiv:2611.20287

Structural properties of semi-cutting sets

Bartłomiej Bosek, Oriol Serra, Lluís Vena

原文摘要

Let $G=(V,E)$ be a finite simple undirected graph, let $T\subseteq V$, and let $F\subseteq E$. We call $F$ semi-cutting for $T$ if $d_{G}(u,w)<d_{G\setminus F}(u,w)$ for every two distinct terminals $u,w\in T$. We prove the sharp bound $|F|\ge |T|-1$. The argument is structural: semi-cutting sets are first identified with edge transversals of all shortest terminal-terminal paths, and the bound then follows from a contraction step, a terminal-deletion lemma, and a lexicographic induction on $(|T|,|V|)$.

math.CO · cs.DM