Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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,...
Clay Thomas's user avatar
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. ...
calmcc's user avatar
  • 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,...
aba's user avatar
  • 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}$, ...
igel's user avatar
  • 185
9 votes
1 answer
286 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 ...
Igor Pak's user avatar
  • 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 ...
Franciszek Malinka's user avatar
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 ...
Rishabh Kothary's user avatar
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 ...
Dubstepzedd's user avatar
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 ...
walydna's user avatar
  • 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 ...
user6584's user avatar
  • 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 ...
Naysh's user avatar
  • 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 ...
Denis's user avatar
  • 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 \...
dohmatob's user avatar
  • 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 ...
Tassle's user avatar
  • 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)$ ...
walydna's user avatar
  • 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), ...
BBK's user avatar
  • 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 ...
Alexander Chervov's user avatar
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 ...
Erel Segal-Halevi's user avatar
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$ ...
Charles's user avatar
  • 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 ...
Null_Space's user avatar
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 ...
Arthur B's user avatar
  • 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)$ ...
Erel Segal-Halevi's user avatar
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, ...
Apprentice's user avatar
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/...
Keio203's user avatar
  • 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 ...
SagarM's user avatar
  • 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 ...
Vk1's user avatar
  • 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 ...
BBK's user avatar
  • 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 ...
Karagounis Z's user avatar
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{...
Claudio Moneo's user avatar
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 ...
Maesumi's user avatar
  • 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=...
aiz89's user avatar
  • 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 ...
lchen's user avatar
  • 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 ...
Karagounis Z's user avatar
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 $...
Cyriac Antony's user avatar
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{...
Cyriac Antony's user avatar
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)...
Hao S's user avatar
  • 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$. ...
Erel Segal-Halevi's user avatar
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 $...
Cyriac Antony's user avatar
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$ ...
Cyriac Antony's user avatar
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 ...
Cyriac Antony's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Cyriac Antony's user avatar
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 ...
Jack M's user avatar
  • 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 $\...
user avatar
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 ...
Shuxue Jiaoshou's user avatar
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\...
Davide Zorzenon's user avatar
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 =...
Karagounis Z's user avatar
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 ...
Karagounis Z's user avatar
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 ...
W. Mapa's user avatar
  • 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 ...
Karagounis Z's user avatar

1
2 3 4 5
14