Discrete Mathematics

New submissions

• New submissions
• Replacements

New submissions for Tue, 14 May 24

[1]  arXiv:2405.06961 [pdf, ps, other]

Title: Dimensionality and randomness

Authors: George Barmpalias, Xiaoyan Zhang

Subjects: Logic (math.LO); Discrete Mathematics (cs.DM); Information Theory (cs.IT)

Arranging the bits of a random string or real into k columns of a two-dimensional array or higher dimensional structure is typically accompanied with loss in the Kolmogorov complexity of the columns, which depends on k. We quantify and characterize this phenomenon for arrays and trees and its relationship to negligible classes.

[2]  arXiv:2405.07512 [pdf, ps, other]

Title: Separation axiom $S_3$ for geodesic convexity in graphs

Authors: Victor Chepoi

Comments: 59 pages, 2 figures

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Metric Geometry (math.MG)

Semispaces of a convexity space $(X,C)$ are maximal convex sets missing a point. The separation axiom $S_3$ asserts that any point $x_0\in X$ and any convex set $A$ not containing $x_0$ can be separated by complementary halfspaces (convex sets with convex complements) or, equivalently, that all semispaces are halfspaces. In this paper, we study $S_3$ for geodesic convexity in graphs and the structure of semispaces in $S_3$-graphs. We characterize $S_3$-graphs and their semispaces in terms of separation by halfspaces of vertices $x_0$ and special sets, called maximal $x_0$-proximal sets and in terms of convexity of their mutual shadows $x_0/K$ and $K/x_0$. In $S_3$-graphs $G$ satisfying the triangle condition (TC), maximal proximal sets are the pre-maximal cliques of $G$ (i.e., cliques $K$ such that $K\cup\{ x_0\}$ are maximal cliques). This allows to characterize the $S_3$-graphs satisfying (TC) in a structural way and to enumerate their semispaces efficiently. In case of meshed graphs (an important subclass of graphs satisfying (TC)), the $S_3$-graphs have been characterized by excluding five forbidden subgraphs. On the way of proving this result, we also establish some properties of meshed graphs, which maybe of independent interest. In particular, we show that any connected, locally-convex set of a meshed graph is convex. We also provide several examples of $S_3$-graphs, including the basis graphs of matroids. Finally, we consider the (NP-complete) halfspace separation problem, describe two methods of its solution, and apply them to particular classes of graphs and graph-convexities.

[3]  arXiv:2405.07666 [pdf, other]

Title: New Solutions to Delsarte's Dual Linear Programs

Authors: André Chailloux, Thomas Debris-Alazard

Subjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM)

Understanding the maximum size of a code with a given minimum distance is a major question in computer science and discrete mathematics. The most fruitful approach for finding asymptotic bounds on such codes is by using Delsarte's theory of association schemes. With this approach, Delsarte constructs a linear program such that its maximum value is an upper bound on the maximum size of a code with a given minimum distance. Bounding this value can be done by finding solutions to the corresponding dual linear program. Delsarte's theory is very general and goes way beyond binary codes.
In this work, we provide universal bounds in the framework of association schemes that generalize the Hamming bound and the Elias-Bassalygo bound, which can be applied to any association scheme constructed from a distance function. These bounds are obtained by constructing new solutions to Delsarte's dual linear program. We instantiate these results and we recover known bounds for $q$-ary codes and for constant-weight binary codes but which didn't come from the linear program method. Our other contribution is to recover, for essentially any $Q$-polynomial scheme, MRRW-type solutions to Delsarte's dual linear program which are inspired by the Laplacian approach of Friedman and Tillich instead of using the Christoffel-Darboux formulas. We show in particular how the second linear programming bound can be interpreted in this framework.

[4]  arXiv:2405.07843 [pdf, other]

Title: An almost complete $t$-intersection theorem for permutations

Authors: Andrey Kupavskii

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

For any $\epsilon>0$ and $n>(1+\epsilon)t$, $n>n_0(\epsilon)$ we determine the size of the largest $t$-intersecting family of permutations, as well as give a sharp stability result. This resolves a conjecture of Ellis, Friedgut and Pilpel (2011) and shows the validity of conjectures of Frankl and Deza (1977) and Cameron (1988) for $n>(1+\epsilon )t$. We note that, for this range of parameters, the extremal examples are not necessarily trivial, and that our statement is analogous to the celebrated Ahlswede-Khachatrian theorem. The proof is based on the refinement of the method of spread approximations, recently introduced by Kupavskii and Zakharov (2022).

Replacements for Tue, 14 May 24

[5]  arXiv:2402.08264 (replaced) [pdf, ps, other]

Title: On Iiro Honkala's contributions to identifying codes

Authors: Olivier Hudry, Ville Junnila, Antoine Lobstein

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[6]  arXiv:2208.07199 (replaced) [pdf, other]

Title: On the Complexity of Distance-$d$ Independent Set Reconfiguration

Authors: Duc A. Hoang

Comments: 17 pages, 8 figures, minor revisions

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[7]  arXiv:2303.13443 (replaced) [pdf, other]

Title: Cliques, Chromatic Number, and Independent Sets in the Semi-random Process

Authors: David Gamarnik, Mihyun Kang, Pawel Pralat

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)

[8]  arXiv:2307.08149 (replaced) [pdf, other]

Title: Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover

Authors: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

Comments: Shortened abstract to meet arxiv requirements. We split the original paper to keep paper length more manageable. This is the first part following an accompanying paper arXiv:2405.01344; and will be presented at ICALP 2024

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

[9]  arXiv:2307.09214 (replaced) [pdf, other]

Title: Patrolling Grids with a Bit of Memory

Authors: Michael Amir, Dmitry Rabinovich, Alfred M. Bruckstein

Subjects: Robotics (cs.RO); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Multiagent Systems (cs.MA); Combinatorics (math.CO)

[10]  arXiv:2311.01026 (replaced) [pdf, ps, other]

Title: A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus

Authors: Hao Sun

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[11]  arXiv:2402.03837 (replaced) [pdf, other]

Title: Expressivity of Geometric Inhomogeneous Random Graphs -- Metric and Non-Metric

Authors: Benjamin Dayan, Marc Kaufmann, Ulysse Schaller

Subjects: Social and Information Networks (cs.SI); Discrete Mathematics (cs.DM)

[12]  arXiv:2405.05296 (replaced) [pdf, other]

Title: A Note on Polychromatic Colorings of Shift-Chains

Authors: Torsten Ueckerdt

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

• New submissions
• Replacements