Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
0
votes
0answers
103 views
Star seperators to explain computational complexity of algorithms on a class of graphs?
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
0
votes
0answers
110 views
Decomposition for a certain class of graphs
Suppose a graph, $G = (V,E)$ is characterized as a lattice/network of cliques as in the picture below. Does there exist some decomposition principle (i.e. on the right) for $G$, that yields some ...
0
votes
0answers
84 views
Maximum Weight Independent Set on a Changing Graph?
Suppose I have an optimal solution to the maximum weight independent/stable set problem on an arbitrary graph. If I were to induce a clique among a subset of its vertices (and perhaps add in some ...
0
votes
0answers
52 views
Internal information is at most expected number of bits
I am freely using known terms from communication complexity.
Let $u$ be a distribution on $X\times Y$, and $P$ a randomized
(private randomness) communication protocol.
We define $IC(u,P) = I(P;X|Y)...
4
votes
1answer
78 views
Stable order on binary strings
I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the ...
0
votes
1answer
120 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
107 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
74 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
114 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
130 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
67 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
115 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
69 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
97 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
39 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
179 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
113 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
73 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
2k 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
95 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
188 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
67 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
208 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
64 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
173 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
150 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
93 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
451 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
189 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
457 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 ...
