All Questions
Tagged with co.combinatorics computer-science
128 questions
1
vote
1
answer
39
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 101
6
votes
2
answers
729
views
Shifting an irrational binary sequence
Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be ...
- 6,652
1
vote
1
answer
197
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
CommunityBot
- 1
9
votes
1
answer
1k
views
35
votes
12
answers
4k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
- 1,644
0
votes
0
answers
106
views
How can I transform every graph into one with constant out-degree?
I am working on my master thesis and try to implement a new shortest path algorithm from the following paper: https://arxiv.org/abs/2203.03456
In some of the functions (for example ScaleDown), ...
- 34.3k
2
votes
0
answers
41
views
graphs which have polynomial bounded number of cycles
How does the graph class defined as those graphs which have polynomial (or quasi polynomial) bounded number of cycles look? (in number of vertices)
I suspect it will rather non-interesting as ...
- 129
0
votes
3
answers
402
views
boolean functions and averaging / counting
Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
- 18.4k
1
vote
2
answers
198
views
Topology of directed graph $G$ with non-singular adjacency matrix
Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
- 109k
1
vote
1
answer
168
views
Permutation graph with insert-and-shift
Motivation. I am working with a database software that allows
you to sort the fields of any given table in the following
peculiar way. Suppose your fields are numbered $1,\ldots, 18$.
Next to every ...
- 48.9k
0
votes
2
answers
96
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
- 23.7k
1
vote
0
answers
83
views
Interpreting multiple property tests at different values of $\epsilon,\delta$ [closed]
I am doing some work in the area of Property Testing, as in Goldreich, Goldwasser, and Ron (2008) or the textbook Introduction to Property Testing (Goldreich). In this framework, I run a test to see ...
1
vote
0
answers
66
views
Set functions satisfying if $f(X) \le f(Y)$ and $Z \cap (X \cup Y) = \emptyset$, then $f(X \cup Z) \le f(Y \cup Z)$
I am investigating set functions $f : 2^\Omega \to \mathbb{N}$ satisfying the following two properties:
(monotone) For all $X, Y \subset \Omega$, if $X \subseteq Y$, then $f(X) \le f(Y)$.
(property ...
- 151
2
votes
0
answers
111
views
Constructing Hamiltonian circuits in acyclic digraphs
Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...
- 63.9k
2
votes
1
answer
60
views
Left-shift cycle generating maps $f:\{0,1\}^{c_0}\to\{0,1\}$ for fixed length $c_0$
This is a strengthening of an older question.
Is there a positive integer $c_0$ with the following property?
For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that ...
- 23.7k
36
votes
8
answers
3k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
- 1,446
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 63.9k
0
votes
2
answers
331
views
Hypergraph cartesian join operation (over same vertex set)
Consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new ...
- 6,367
4
votes
4
answers
472
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
2
votes
0
answers
245
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
0
votes
0
answers
59
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 869
18
votes
3
answers
785
views
Automated search for bijective proofs
In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...
- 15.8k
0
votes
0
answers
118
views
Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point
In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
- 4,786
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 83
2
votes
1
answer
137
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
- 32.1k
6
votes
1
answer
527
views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
- 716
4
votes
1
answer
266
views
Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
This question is a follow-up of this question.
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.
Question: Can we compute the exact minimum $$A:=
\min_{u:\mathbb{...
CommunityBot
- 1
3
votes
4
answers
2k
views
Enumerative algorithm through inclusion-exclusion
Hello everybody !
I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...
- 2,821
4
votes
1
answer
207
views
Nearly De Bruijn sequences constructed from De Bruijn sequences
Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once. Let $x$ be a $01$-sequence of length $n$. When and ...
- 10.4k
9
votes
1
answer
425
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 656
5
votes
1
answer
230
views
Cycling through $\{0,1\}^{(2^n)}$ such that all Hamming distance appear equally frequently
Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$....
- 9,501
3
votes
1
answer
207
views
Is normalcy preserved under the swapping operation?
Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$.
Let the swapping operation $\...
- 63.9k
1
vote
1
answer
182
views
Boolean function : approximation by a linear function
Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...
- 63.9k
1
vote
1
answer
102
views
How do I fit flow values to connections in a known network?
This is not my area and I'm new to its terminology, and am posting my problem in the hope that someone will be able to direct me to where it has been solved, or who has written about it.
I have a flow ...
CommunityBot
- 1
0
votes
1
answer
2k
views
How does the greedy algorithm for CSES problem collecting numbers work? [closed]
The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds ...
- 101
7
votes
1
answer
270
views
Search algorithms with mappings/functions/sets as variables
I apologize in advance if this sounds vague but I am trying to find directions as to what to look for.
All the sets in this problem are finite.
Suppose we have two functions $f_1\colon X_1\times Y_1\...
CommunityBot
- 1
5
votes
1
answer
264
views
Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$
Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=...
- 351
2
votes
1
answer
777
views
Is there a term for a subgraph which includes all the edges of a graph?
A subgraph is called spanning when it includes all of the vertices of the given graph.
Is there a term for a subgraph which includes all the edges of a graph?
Thanks.
- 1,444
2
votes
1
answer
159
views
Largest number N for which injective mapping $f: 2^N \to 2^8 \times 2^8 \times 2^8$ which is Lipschitz-1 CT with $K\leq 3$ exists
I have a function on $h: [0,1] \to [0,1]$ whose output is smooth (polynomial of low degree), and I need to discretize it but I need to save it with three 8 bit numbers. These three 8 bit numbers need ...
CommunityBot
- 1
81
votes
4
answers
8k
views
Wanted: a "Coq for the working mathematician"
Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar with....
- 14k
9
votes
1
answer
594
views
Spanning $k$-trees
##k-trees
A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)
a) A complete graph with $k$ vertices is a $k$-tree.
b) A $k$-tree on $n$ vertices $T$ is obtained by a $...
- 24.7k
20
votes
5
answers
1k
views
Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?
Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known:
If $L$ is regular, then $f_L$ is ...
- 33
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 6,101
5
votes
1
answer
276
views
NP-hardness of a sequence problem
Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
- 6,652
5
votes
1
answer
275
views
How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?
First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
CommunityBot
- 1
1
vote
1
answer
565
views
Upper bounding VC dimension of an indicator function class
I would like to upper bound the VC dimension of the function class $ F$ defined as follows:
$$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q ...
CommunityBot
- 1
0
votes
0
answers
125
views
Lower bounds on the length of circuits, depending on the number of times it crosses itself
I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...
- 431
0
votes
1
answer
94
views
Value (not position)- based sorting; reference request
A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation.
Many sort algorithms are position based: you ...
- 24.2k
3
votes
1
answer
96
views
What is known about computing all binary error correcting codes of given parameters?
Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.
Are there any sources about using algorithms to find all given ...
- 10.4k