# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

677 questions
Filter by
Sorted by
Tagged with
48 views

### Why LOUDS is considered succinct coding?

LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc. It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
• 113
73 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
67 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
76 views

Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
• 14.1k
119 views

### How well can shortest common supersequence over small alphabet size be approximated?

Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
• 228
55 views

### Shortest sequence that contains a given list of sequences as subsequences

Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences? Very similar to the question ...
• 228
411 views

• 205
203 views

### Assignment problem for forming pairs of real numbers

Suppose I have two sets of real numbers, $X$ and $Y$, each of cardinality $N$. I would like to assign these points to pairs $(X_i, Y_j)$ such that the sum of squared intra-pair distances is minimized. ...
• 161
1 vote
66 views

### Constructing lossless conductors using zigzag product - a doubt

Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
• 91
117 views

### Shortest Common Supersequence of Permutations

For integers $k$ and $n$, let $P_{k,n}$ be the set of all size-$k$ sets of permutations of $[n]$. The Shortest Common Supersequence for Permutations (SCSP) problem is: given a set $S\in P_{k,n}$, ...
• 185
307 views

### Complexity of permanent verification

Consider the problem of permanent verification: $\bullet \$ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$? Question: Is it known to be NP-hard? Should ...
• 812
128 views

### Exploding number of homomorphisms

I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from ...
176 views

### An additive combinatoric probability question

Let $A,B \subset [d]$, where $[d] = \{0,...,d \}$, such that $A\cap B = \phi$ and $|A| = |B| = \frac{d+1}{2}$. I was studying the size of $|(2A \cup 2B) \triangle (A+B)|$, where $\triangle$ is the ...
121 views

### Cover all triangles of a graph with n subgraphs as small as possible

What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
• 63
101 views

### Influence for boolean functions on larger domains

Most of the literature on boolean function complexity considers boolean functions on $\{0,1\}^n$, but I am not finding very much about functions over larger (finite) domains. Specifically, fix a ...
• 1,242
1 vote
60 views

### What are the fastest known parameterized algorithms for Grid Tiling?

Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
• 686
233 views

### Combinatorics of a badminton tournament

Someone wants to organize a badminton tournament, where each match is a 2 versus 2, i.e. by teams. The idea is to have teams rotate, so that you can play with everyone. If there are $n$ players, where ...
• 8,903
29 views

### Bound on line with minimum zone complexity in a line arrangement

In an arrangement of $n$ (pseudo)lines, the well known Zone Theorem gives a $O(n)$ bound on the complexity of the zone of any given line (for the purpose of this question, the complexity of the zone ...
• 881
227 views

### Cover a graph with complete graphs

I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
• 63
1 vote
40 views

### Minimum vertex-separators under edge addition

I am trying to prove the following claim. Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$. Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
• 103
43 views

### Is there a name and context where function for permutation defined as f(k) = #σ({1,2,…,k})∩{1,2,…,k} appeared ? (Measure of locality)

Context: Thinking on some machine learning questions on comparing the feature importances produced by different methods - the following measure of concordance between two ordered lists seems to be ...
1 vote
218 views

### How much information does it take to specify, not each member of a group, but any one member?

It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
• 1,745
1 vote
83 views

### A bound that follows from submodularity

I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11. I got stuck on this inequality: where $f$ is a monotone submodular set ...
• 113
502 views

### Number of permutations that satisfy a given set of comparisons

We are given a set of comparisons of the form z[i] < z[j] for various i and j and an ...
• 429
47 views

### Computing a feasible exchange bijection between bases of a matroid

A base-orderable matroid is a matroid in which, for any two bases $A$ and $B$, there exists a feasible exchange bijection, that is, a bijection $f: A\to B$ such that, for all $a\in A$, both $A-a+f(a)$ ...
• 2,294
41 views

### Combinations of subsets

Problem. Let $x = (x_1,...,x_N) \in K^{N}$, i.e., each element $x_j$ of $x$ can take $K$ discrete values. Let $x_{(i)}$, for $i \in 1,...,I,$ be a vector of overlapping subsets of $x$. For example, ...
• 101
1 vote
322 views

• 1,827
220 views

• 228
117 views

### Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]

Cross-post from CS.SE In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. ...
• 2,294