Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

59
votes
5answers
4k views

The origin of the notion of treewidth

My question today is (as usual) a bit silly; but I would request you to kindly consider it. I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
54
votes
13answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
52
votes
1answer
1k views

A combinatorial version for the polynomial Hirsch conjecture

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
48
votes
11answers
2k views

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a ...
44
votes
10answers
3k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
42
votes
12answers
3k views

Applications of representation theory of the symmetric group

Inspired by this question and in particular the final paragraph of Or's answer, I have the following question: Do you know of any applications of the representation theory of the symmetric group in ...
39
votes
13answers
2k views

Using error-correcting codes in theory

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
39
votes
2answers
888 views

How many distinct colors are needed to lower-bound the choosability of a graph?

A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\...
38
votes
17answers
4k views

Conjectures implying Four Color Theorem

Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
38
votes
3answers
8k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
37
votes
6answers
3k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
29
votes
2answers
838 views

Polynomial method for complexity results

Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
28
votes
8answers
4k views

What is the minimum number of bits required to store a sudoku puzzle?

Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved ...
28
votes
4answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
28
votes
4answers
805 views

Proofs obtained only through spectral graph theory

I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have. However, ...
28
votes
4answers
2k views

What is simplest polynomial algorithm for PLANARITY?

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
28
votes
1answer
495 views

Good codes decodable by linear-sized circuits?

I'm looking for error-correcting codes of the following type: binary codes with constant rate, decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of ...
27
votes
5answers
5k views

Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
26
votes
4answers
3k views

Counting words accepted by a regular grammar

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
26
votes
2answers
1k views

Maximal/maximum independent sets

Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs? For example, take a set of points in ...
26
votes
1answer
853 views

Coloring complexity of graphs

Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
26
votes
1answer
594 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
26
votes
4answers
2k views

Complexity of applying a permutation in-place

To my surprise, I was not able to find papers about this - probably searched the wrong keywords. So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation. How do ...
25
votes
2answers
3k views

Exact number of comparisons to compute the median

Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element ...
25
votes
2answers
616 views

The complexity of determining if a fixed graph is a minor of another

The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic: 1) It appears that there ...
25
votes
1answer
710 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
25
votes
1answer
1k views

An edge partitioning problem on cubic graphs

Has the complexity of the following problem been studied? Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$ Question: is there a partition of $E$ into $|E|/3$ parts of size $...
24
votes
5answers
5k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
24
votes
2answers
2k views

Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
24
votes
2answers
785 views

Computational complexity of counting induced subgraphs which admit perfect matchings

Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ ...
24
votes
1answer
541 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
23
votes
3answers
1k views

Representing OR with polynomials

I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such: $p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\...
23
votes
6answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings. ...
23
votes
8answers
3k views

graphs from real-life problems

Where can I find graphs relevant to real-life problems? Two repositories I know of are: University of Florida's Sparse Matrix Collection Bodlaender's TreewidthLib
23
votes
3answers
1k views

What is known about solutions to sparse integer linear programming problems?

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what ...
23
votes
5answers
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 ...
23
votes
1answer
449 views

How big is the variance of the treewidth of a random graph in G(n,p)?

I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$ and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(...
23
votes
1answer
341 views

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...
23
votes
0answers
548 views

Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...
22
votes
3answers
1k views

Number of distinct nodes in a random walk

Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
22
votes
2answers
666 views

Are there local maxima in the number of moves required to solve a Rubik's Cube?

Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive ...
21
votes
5answers
2k views

Reasons for which a graph may be not $k$ colorable?

While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
21
votes
4answers
1k views

Social choice, arrow's theorem and open problems ?

Last few months I started to lecture myself on social choice, arrow's theorem and related results. After reading about the seminal results, I asked myself about what happens with partial order ...
21
votes
2answers
679 views

Are shift-chains two-colorable?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ${\...
21
votes
1answer
511 views

Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

I encountered the following result during my research. $$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$$ where $m=\omega(\sqrt n)$ and $a_1,\...
21
votes
2answers
926 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
21
votes
1answer
340 views

Consensus clustering using set union

I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it. Problem ...
20
votes
5answers
2k views

About properties of adjacency matrix when a graph is planar

1- Is there any specific properties for adjacency matrix when a graph is planar? 2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?
20
votes
2answers
1k views

Coloring Planar Graphs

Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can ...