Questions tagged [co.combinatorics]
Questions related to combinatorics and discrete mathematical structures
667
questions
3
votes
0
answers
111
views
Computational complexity of finding the $n$th Dedekind Number
Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,...
- 205
3
votes
2
answers
167
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
0
answers
56
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
2
votes
1
answer
99
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
9
votes
1
answer
287
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
4
votes
0
answers
120
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 ...
0
votes
1
answer
168
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 ...
0
votes
0
answers
41
views
Designing Experiments
I have a question regarding designing experiments that i can't quite wrap my head around. The question will be posted as an image below!
So the question gives us three factors with a specified amount ...
3
votes
0
answers
109
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
3
votes
0
answers
95
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
0
answers
42
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 ...
- 576
13
votes
1
answer
211
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,598
0
votes
0
answers
35
views
Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?
Let $N \ge 1$ be an integer and let $\mathfrak S$ be a nonempty collection of subsets of $[N] := \{1,2,\ldots,N\}$. For any $n \in [N]$, define $\partial_n \mathfrak S := \{S\setminus\{n\} \mid S \in \...
- 291
3
votes
0
answers
25
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 ...
- 691
3
votes
1
answer
201
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
0
answers
37
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), ...
- 95
2
votes
0
answers
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 ...
0
votes
0
answers
56
views
Maximum-weight matroid intersection with real weights
Given a matroid with weighted elements, a basis with maximum total weight can be found in polynomial time using the greedy algorithm. This is true even when the weights are real numbers, if we assume ...
- 2,086
1
vote
2
answers
216
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,737
1
vote
1
answer
81
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
6
votes
1
answer
484
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 ...
- 419
0
votes
0
answers
39
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,086
0
votes
0
answers
38
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
1
answer
197
views
Number of stable matchings
In the stable marriage problem, is it possible to find an instance with $2^{n -1}$ stable matchings when $n$ is a power of 2 (or just even)? If yes, how? I know how to build an instance in which $2^{n/...
- 113
2
votes
1
answer
84
views
Regularity Lemma for Multi-Relational Graphs?
Is there an analogous to Szemerédi regularity lemma in the setting, where I have multi relational graph i.e. I have $n$ nodes, but instead of having edges to be in $\{0,1\}$ i.e. there is an edge or ...
- 706
1
vote
1
answer
176
views
Decomposition of a permutation into increasing subsequences
Given a permutation $P$, the goal is to decompose this permutation into $k$ increasing subsequences $L_1,L_2,\ldots,L_k$, such that every element in $P$ appears exactly once in some increasing ...
- 137
1
vote
0
answers
61
views
The "branch-depth" parameter and its use in FPT algorithms
Let $P=(v_1,\dots,v_q)$ be an induced path in the undirected graph $G(V,E)$. In [1], the authors define the branch depth of $P$ to be $b(P)=|N_G[\{v_1,\dots,v_{q-1}\}]|-1$. Further, in [1] it is shown ...
- 95
1
vote
0
answers
60
views
The tree augmentation problem, but with hyperlinks
In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
- 607
3
votes
1
answer
77
views
Sorting multiple columns of a matrix
Let $A \in \mathbb{R}^{n \times k}$ be a matrix where each column contains all of the numbers from $\{1,\dots,n\}$ in some arbitrary order. For example, if $n=3, k=2$, we could have
$$ A =
\begin{...
- 189
2
votes
2
answers
152
views
Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$
Given: a (long binary) string $\ell$, and a set of (short) strings, $s_1, s_2, ...$ . Can $\ell$ be written as concatenation of the short strings?
I am looking for references on: the name of the ...
- 121
3
votes
1
answer
166
views
Maximal uniquely decodable codes
This question is about the Kraft-McMillan inequality:
If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then
$$ \sum_{i=...
- 33
0
votes
0
answers
41
views
Multi-dimensional 0-1 Knapsack problem with a high number of dimensions
I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of ...
- 113
2
votes
1
answer
204
views
Maximize a special monotone submodular function - is it easier?
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
- 607
1
vote
0
answers
87
views
On Negami's planar cover cojecture
For this question, let us consider only simple, finite, undirected graphs.
A homomorphism $\psi$ from a graph a $G$ to a graph $H$, $\psi\colon V(G)\to V(H)$, is a Locally Bijective Homomorphism from $...
- 1,723
0
votes
1
answer
175
views
On structure of graphs with average degree equal to maximum average degree
For a simple graph $G$, the $\text{average-degree}(G)=|E(G)|/|V(G)|$ and
the maximum average degree $\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$.
If $\text{...
- 1,723
2
votes
0
answers
107
views
Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?
Given a graph $G=(V,E)$, costs $c \in \mathbb{R}^E$ the TSP problem is to compute a min cost tour of the graph. The LP is
min $ c^tx $
$x(\delta(S)) \geq 2 \ \ \ \ \forall S \subset V $
$x(\delta(v)...
- 186
2
votes
0
answers
105
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,086
3
votes
0
answers
48
views
Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?
All graph considered here are finite, simple and undirected.
We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $...
- 1,723
3
votes
1
answer
169
views
On cubic planar graphs with face boundaries of length divisible by 4
All graphs considered here are finite, simple and undirected.
Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
- 1,723
1
vote
0
answers
35
views
Cycle decompositions of locally linear 4-regular graphs
(Preface)
We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.
(Question starts)
A graph is locally ...
- 1,723
2
votes
1
answer
97
views
Bin packing with non-additive load functions
I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has ...
- 2,086
1
vote
0
answers
38
views
Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?
The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
- 1,723
6
votes
1
answer
318
views
How can we compute the VC dimension of a finite class of sets?
Let $F$ be a class of subsets of a finite set $X$ of cardinality $n$. What is the complexity of computing the VC dimension of $F$? Can we do better than looping through every subset of $X$ and ...
- 247
1
vote
0
answers
53
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
user53330
9
votes
1
answer
306
views
Does Horn SAT (Horn formula in CNF) have an integral polytope?
In some ways, my question is related to this: Is the matching polytope integral?
Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
- 113
5
votes
2
answers
294
views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
- 103
1
vote
1
answer
136
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 607
0
votes
1
answer
220
views
Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?
Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables.
Let's say we ...
- 607
7
votes
1
answer
292
views
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
My question concerns the NP-hardness of the following discrete optimization problem:
Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,
$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
- 73
1
vote
1
answer
120
views
Is there a regular bipartite graph where the minimum cuts are trivial?
My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial?
We can ...
- 607