Discrete Mathematics
New submissions
[ showing up to 2000 entries per page: fewer | more ]
New submissions for Tue, 28 May 24
- [1] arXiv:2405.16149 [pdf, other]
-
Title: Small unsatisfiable $k$-CNFs with bounded literal occurrenceComments: full version of a paper to appear in the proceedings of SAT 2024Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO)
We obtain the smallest unsatisfiable formulas in subclasses of $k$-CNF (exactly $k$ distinct literals per clause) with bounded variable or literal occurrences. Smaller unsatisfiable formulas of this type translate into stronger inapproximability results for MaxSAT in the considered formula class. Our results cover subclasses of 3-CNF and 4-CNF; in all subclasses of 3-CNF we considered we were able to determine the smallest size of an unsatisfiable formula; in the case of 4-CNF with at most 5 occurrences per variable we decreased the size of the smallest known unsatisfiable formula. Our methods combine theoretical arguments and symmetry-breaking exhaustive search based on SAT Modulo Symmetries (SMS), a recent framework for isomorph-free SAT-based graph generation. To this end, and as a standalone result of independent interest, we show how to encode formulas as graphs efficiently for SMS.
- [2] arXiv:2405.16938 [pdf, other]
-
Title: Remote control system of a binary tree of switches -- I. constraints and inequalitiesAuthors: Olivier GolinelliSubjects: Discrete Mathematics (cs.DM)
We study a tree coloring model introduced by Guidon (2018), initially based on an analogy with a remote control system of a rail yard, seen as a switch tree. For a given rooted tree, we formalize the constraints on the coloring, in particular on the minimum number of colors, and on the distribution of the nodes among colors. We show that the sequence $(a_1,a_2,a_3,\cdots)$, where $a_i$ denotes the number of nodes with color $i$, satisfies a set of inequalities which only involve the sequence $(n_0,n_1,n_2,\cdots)$ where $n_i$ denotes the number of nodes with height $i$. By coloring the nodes according to their depth, we deduce that these inequalities also apply to the sequence $(d_0,d_1,d_2,\cdots)$ where $d_i$ denotes the number of nodes with depth $i$.
- [3] arXiv:2405.16968 [pdf, other]
-
Title: Remote control system of a binary tree of switches -- II. balancing for a perfect binary treeAuthors: Olivier GolinelliSubjects: Discrete Mathematics (cs.DM)
We study a tree coloring model introduced by Guidon (2018), initially based on an analogy with a remote control system of a rail yard, seen as switches on a binary tree. For a given binary tree, we formalize the constraints on the coloring, in particular the distribution of the nodes among colors. Following Guidon, we are interested in balanced colorings i.e. colorings which minimize the maximum size of the subsets of the tree nodes distributed by color. With his method, we present balanced colorings for trees of height up to 7. But his method seems difficult to apply for trees of greater height. Also we present another method which gives solutions for arbitrarily large trees. We illustrate it with a balanced coloring for height 8. In the appendix, we give the exact formulas and the asymptotic behavior of the number of colorings as a function of the height of the tree.
- [4] arXiv:2405.17120 [pdf, ps, other]
-
Title: Dual VC Dimension Obstructs Sample Compression by EmbeddingsSubjects: Discrete Mathematics (cs.DM); Machine Learning (cs.LG)
This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddings necessarily require a significant increase in dimension. In particular, we prove that for every $d$ there is a class with VC dimension $d$ that cannot be embedded in any extremal class of VC dimension smaller than exponential in $d$.
In addition to its independent interest, this result has an important implication in learning theory, as it reveals a fundamental limitation of one of the most extensively studied approaches to tackling the long-standing sample compression conjecture. Concretely, the approach proposed by Floyd and Warmuth entails embedding any given VC class into an extremal class of a comparable dimension, and then applying an optimal sample compression scheme for extremal classes. However, our results imply that this strategy would in some cases result in a sample compression scheme at least exponentially larger than what is predicted by the sample compression conjecture.
The above implications follow from a general result we prove: any extremal class with VC dimension $d$ has dual VC dimension at most $2d+1$. This bound is exponentially smaller than the classical bound $2^{d+1}-1$ of Assouad, which applies to general concept classes (and is known to be unimprovable for some classes). We in fact prove a stronger result, establishing that $2d+1$ upper bounds the dual Radon number of extremal classes. This theorem represents an abstraction of the classical Radon theorem for convex sets, extending its applicability to a wider combinatorial framework, without relying on the specifics of Euclidean convexity. The proof utilizes the topological method and is primarily based on variants of the Topological Radon Theorem.
Cross-lists for Tue, 28 May 24
- [5] arXiv:2405.16586 (cross-list from math.CO) [pdf, other]
-
Title: Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color TheoremComments: Abstract shortened. Github this https URLSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (non-trivial) snark that can be embedded in the projective plane is the Petersen graph.
This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph.
This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability.
An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Peteren-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane.
Some of our proofs require extensive computer verification. The necessary source codes, together with the input and output files and the complete set of more than 6000 reducible configurations are available on Github (https://github.com/edge-coloring) which can be considered as an Addendum to this paper. Moreover, we provide pseudocodes for all our computer verifications. - [6] arXiv:2405.16618 (cross-list from math.OC) [pdf, other]
-
Title: An efficient optimization model and tabu search-based global optimization approach for continuous p-dispersion problemSubjects: Optimization and Control (math.OC); Discrete Mathematics (cs.DM); Mathematical Software (cs.MS)
Continuous p-dispersion problems with and without boundary constraints are NP-hard optimization problems with numerous real-world applications, notably in facility location and circle packing, which are widely studied in mathematics and operations research. In this work, we concentrate on general cases with a non-convex multiply-connected region that are rarely studied in the literature due to their intractability and the absence of an efficient optimization model. Using the penalty function approach, we design a unified and almost everywhere differentiable optimization model for these complex problems and propose a tabu search-based global optimization (TSGO) algorithm for solving them. Computational results over a variety of benchmark instances show that the proposed model works very well, allowing popular local optimization methods (e.g., the quasi-Newton methods and the conjugate gradient methods) to reach high-precision solutions due to the differentiability of the model. These results further demonstrate that the proposed TSGO algorithm is very efficient and significantly outperforms several popular global optimization algorithms in the literature, improving the best-known solutions for several existing instances in a short computational time. Experimental analyses are conducted to show the influence of several key ingredients of the algorithm on computational performance.
- [7] arXiv:2405.16693 (cross-list from cs.AI) [pdf, other]
-
Title: Detection of decision-making manipulation in the pairwise comparisons methodComments: 19 pages, 5 figures, 2 tablesSubjects: Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)
Most decision-making models, including the pairwise comparison method, assume the decision-makers honesty. However, it is easy to imagine a situation where a decision-maker tries to manipulate the ranking results. This paper presents three simple manipulation methods in the pairwise comparison method. We then try to detect these methods using appropriately constructed neural networks. Experimental results accompany the proposed solutions on the generated data, showing a considerable manipulation detection level.
- [8] arXiv:2405.17172 (cross-list from math.CO) [pdf, other]
-
Title: Partitioning complete geometric graphs into plane subgraphsComments: 10 pages, 4 figuresSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
A \emph{complete geometric graph} consists of a set $P$ of $n$ points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant $c<1$, such that every complete geometric graph on $n$ points can be partitioned into at most $cn$ plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set $P$ is \emph{dense}, which means that the ratio between the maximum and the minimum distances in $P$ is of the order of $\Theta(\sqrt{n})$.
Replacements for Tue, 28 May 24
- [9] arXiv:2207.04514 (replaced) [pdf, ps, other]
-
Title: Large independent sets in recursive Markov random graphsComments: minor updates to Introduction with some new references to other works on random graphs. Accepted to Mathematics of Operations ResearchSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Optimization and Control (math.OC); Probability (math.PR)
- [10] arXiv:2312.03975 (replaced) [pdf, ps, other]
-
Title: The classification of Boolean degree $1$ functions in high-dimensional finite vector spacesAuthors: Ferdinand IhringerComments: 12 pages; version accepted by the AMS ProceedingsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
- [11] arXiv:2405.07666 (replaced) [pdf, other]
-
Title: New Solutions to Delsarte's Dual Linear ProgramsSubjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM)
[ showing up to 2000 entries per page: fewer | more ]
Disable MathJax (What is MathJax?)
Links to: arXiv, form interface, find, cs, recent, 2405, contact, help (Access key information)