Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
0
votes
1answer
86 views
Subset Sum Problem and hard looking instances that are not really hard
I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
4
votes
1answer
97 views
Applications of Christol theorem
I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
1
vote
1answer
69 views
Pulling a graph across a partition
I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
9
votes
0answers
108 views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
2
votes
0answers
128 views
Smallest disjoint union chain containing a sequence of sets
Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element.
A family $\...
3
votes
0answers
64 views
Linear optimization over intersection of totally unimodular matrices
I am currently dealing with a problem of the following form
\begin{alignat}{2}
&\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\
&\text{sub to} \hspace{0.05in}&&...
1
vote
0answers
95 views
Growth of random square lattice trees
Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
6
votes
1answer
110 views
Average-case analogue of Small-bias Spaces
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-...
3
votes
0answers
68 views
Mutually exclusive replacement paths, an existing problem?
A replacement path is a simple path allocated to an edge $e \in G$
that connects the endpoints of $e$ in $G \setminus \{e\}$.
The problem
An undirected graph $G$ is given and the task is to allocate ...
4
votes
1answer
95 views
Probability of a $k$-path in a random graph
Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
1
vote
1answer
105 views
Total flow using minimum number of edges on a bipartite network
If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
1
vote
0answers
37 views
Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3
By a "chain of k nodes", I mean k nodes lined up like a linked-list: o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. ...
7
votes
1answer
254 views
Distinguishability a set of permutations
Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable''...
1
vote
0answers
28 views
Inductive definition of language operators like the set of all permutations of a word came from the shuffle operator
Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be
$$
u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \...
1
vote
2answers
177 views
Is perfect matching for bipartite graph with no cycles unique?
Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.
My question is if the balanced bipartite graph is also ...
1
vote
0answers
106 views
How to represent boolean tree + algorithm as a mathematical formula
In programming say you have a boolean tree like this:
...
-1
votes
1answer
145 views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
0
votes
0answers
48 views
Given $f \in \mathbb{Z}_2[x_1, …, x_n]$, are there properties of $f$ which can be used to bound $\mathbb{E}_{i \in [n]}|gap(f) - gap(f + x_i)$|?
Let $f \in \mathbb{Z}_2[x_1, ..., x_n]$ be arbitrary. We define $gap(f) = |f^{-1}(0)| - |f^{-1}(1)|$. I want to understand, as a function of any properties of $f$ you find relevant (number of terms, ...
1
vote
0answers
72 views
Nim-game variant - weird ending condition
the game is structured like this:
two players
the players alternate moves
4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$
at each move, the player can either remove one or two elements from ...
3
votes
2answers
278 views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
3
votes
2answers
1k views
How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once.
For a subset $S$ of nodes and a node $i\in S$, let $D[...
-3
votes
1answer
114 views
Continous work distribution algorithm with failover
Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256.
Is there an algorithm that ...
-3
votes
1answer
94 views
Proving that a random permutation generator is not fair [closed]
If I'm generating random permutations using the following algorithm:
...
3
votes
0answers
72 views
Finding the longest sub-permutation with bounded inversion number
Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\...
0
votes
0answers
46 views
Wavelet based Non linear optimization technique
I am outlining a method for solving Non Linear optimization problems.
Consider the system of equations:--------------------------------- 1
f1(a0, a1, a2, a3 ......... an) = 0
f2(a0, a1, a2, a3 ........
5
votes
1answer
1k views
Is Hartmanis-Stearns conjecture settled by this article?
The paper
"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601....
0
votes
0answers
79 views
Sum of products of all combinations with replacement
I am interesting in finding if the sum of the products of all possible tuples of positive integers with replacement is computable without simply iterating through the tuples and computing directly.
...
9
votes
1answer
185 views
Finding subgraphs with high treewidth and constant degree
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
11
votes
2answers
145 views
Does the first order theory of a finite structure have bounded quantifier rank?
Let $\mathfrak{A} $ be any finite structure.
Does its first order theory $ \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) $ have bounded quantifier rank, in the sense that there is a $ q\in\mathbb{N} $ ...
3
votes
1answer
66 views
Reference: Cancellability of the Dyck congruence
I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \...
4
votes
1answer
200 views
Relation between variance and mutual information
Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$
This bound may be ...
6
votes
1answer
122 views
Directed graph with bounded in-deg can be partitioned in a balanced way
I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
4
votes
0answers
58 views
Short supersequence for many permutations
A shortest supersequence $c_n$ of all permutations on $[n]$ has length $\Theta(n^2)$: see this question on Mathoverflow. What if we force $c_n$ to be short? How many permutations can it cover?
Let's ...
2
votes
1answer
63 views
Almost regular subhypergraph of hypergraph with large minimal degree
I am interested in knowing whether the following conjecture is true or not:
For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
...
3
votes
1answer
170 views
Existence of $d$-regular expander graph that can be represented as a bipartite graph
It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander ...
4
votes
0answers
95 views
How to construct an $(n,m,k)$ ``separating set''?
This problem is probably known under some other name, if anyone has seen it before, a reference will be great.
Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary ...
4
votes
0answers
148 views
Just how bad is the fooling set method in communication complexity?
I know that if we take a random function, it's likely that the maximal fooling set is at most $kn$ for some constant $k$, while the CC is almost $n$. What bound can I get from above on the ...
2
votes
1answer
90 views
Counting xyz-graphs in $\mathbb{Z}_n^3$
This is a followup question to: Lower bound on the largest restrained cubic subset
How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$
This question may be seen ...
1
vote
0answers
49 views
Counting multiplicative closures
Given a set $S$, its multiplicative closure is the set
$$
\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}
$$
of products of zero or more elements of $S$. So the multiplicative closure ...
7
votes
0answers
171 views
Reference request: exponential growth rates of subsequence-closed languages are integers
This question is migrated from MathOverflow, where it did not receive any answers a year ago.
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
9
votes
0answers
91 views
Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra
Consider the space $\mathbb{Q}^n$.
A convex polyhedron is defined, equivalently, by a system of linear (in)equalities (with integer coefficients) or by a system of generators: vertices, and in case ...
10
votes
0answers
448 views
How to prove “obvious” facts?
The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" ...
2
votes
1answer
187 views
Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?
It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$...
1
vote
1answer
51 views
Families of LDPC codes with constant error fraction corrected
I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.
For example, I know that Sipser and Spielman proved that there is an ...
15
votes
1answer
454 views
VC dimension of polynomials over tropical semirings?
As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the ...
5
votes
1answer
103 views
Counting subsets of given set with certain properties
Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$.
Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$,
such that when the $s_i$ are ...
4
votes
0answers
123 views
Computing the Fourier expansion of the complete quadratic function
I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$
$...
5
votes
1answer
119 views
If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$
I'm searching for a reference for the following property:
Fact. Let $u, v \in A^*$. Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v = w^c$. There are unique words $z, z'$ such ...
4
votes
3answers
286 views
Pairwise comparison of bit vectors
Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.
I am interested in the following problem:
Given $x_1,\dots,x_n \...
6
votes
0answers
103 views
Constructing a large bit-vector set with the following property
I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property:
$$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$
In ...
