# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

667 questions
Filter by
Sorted by
Tagged with
111 views

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 ...
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)$ ...
1 vote
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), ...
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 ...
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 ...
1 vote
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 vote
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 ...
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 ...
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)$ ...
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, ...
1 vote
197 views

175 views

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$. ...
48 views

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 $... 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 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 ... 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 ... 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 ... 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 ... 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$\... 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 ...
294 views

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 ...
### 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 ...
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 ...