# Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

581 questions
162 views

### Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points. Let $D$ be the distance matrix between ...
126 views

### Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
2k views

### What's the relation between the dominating set and vertex cover?

I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?
94 views

### Monomial decomposition as product of smaller monomials

Is there an algorithm to get all possible decompositions of a monomial as the product of smaller monomials ? For example $x^2y^3$ is $x∗xy^3$, $x^2∗y^3$, $xy∗xy^2$, and so on. For a monomial in one ...
2k views

313 views

### Generalization of independent set

I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices. How about if you allow no more than $k$ pairs of adjacent vertices? ...
349 views

### Streaming Algorithm Lower Bounds by Communication Complexity

I am learning the methods for proving lower bounds on streaming algorithms using communication complexity. My question is about a basic technique to prove lower bounds on streaming models using the ...
116 views

### Do expander graphs have the property that with high probability an s-t cut is size min{degree(s),degree(t)}?

If we want a specific example, then how about the Erdos-Renyi random graph?
70 views

### Nonnegative Permanent and Ellipsoidal Method

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. This was based on the Ellipsoidal Method. Finding a Max Cut is the same for Bipartite Graphs as ...
240 views

### Canonical labeling of special classes of DAGs

Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known. What are some special classes of DAGs that can be ...
286 views

### Bipartite vertex separator

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph? I have a ...
297 views

### Increasing the capacity to maximize the min cut

Consider a graph with all edges having unit capacity. One can find the min cut in polynomial time. Suppose I am allowed to increase the capacity of any $k$ edges to infinity (equivalent to merging ...
360 views

### Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
407 views

### Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
94 views

### PCVRP with prizes reduced over time

Hej guys, I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows: The set of customers does not change over time, but their respective prizes ...
82 views

### Bound for the spectral norm of a boolean function [duplicate]

As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$. Is it possible to improve this bound..? Can somebody provide me an example of a Boolean ...
769 views

### Generating interesting combinatorial optimization problems

I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
616 views

### Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function. The Fourier expansion of $f$ is $$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers ...
187 views

### How can we derive this lower bound of a special cut in a graph?

I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
112 views

### Complexity of the packing

Let $(A, \leq)$ be a totally ordered alphabet. The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, ...
2k views

### Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
2k views

### Good seating arrangements for sequence of meals and tables of size k for a group of people

Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that ...
125 views

### Complexity of the standardization

Let $(A, \leq)$ be a totally ordered alphabet. The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an ...
660 views

### Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$. Define $A_k$ to be the number of permutations ...
388 views

### How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied: \$x_1 \oplus x_2 \oplus \...
352 views

### Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
2k views

### Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...