Stack Exchange Network

Stack Exchange network consists of 174 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]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

13
votes
0answers
1k views

Finding a chromatic polynomial by polynomial fitting

I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...
5
votes
2answers
262 views

Bounds on a partition theorem with ambivalent colors

I've been running into the following type of partition problem. Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n ...
37
votes
5answers
4k views

Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable. This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...
9
votes
4answers
1k views

Uniqueness in Composition of Polynomials

The following situation came up in my research: Suppose two functions $f$ and $g$ map $[0,\infty)$ to (a subset of) itself. The function $f$ is linear and $g$ is quadratic, but $g$ is one-to-one on ...
13
votes
1answer
588 views

Where do stable Kronecker coefficients live “in nature”?

Background: For a partition $\lambda$, let $\lambda[N] = (N - |\lambda|, \lambda_1, \lambda_2, \lambda_3, \dots)$, also let $\chi_\lambda$ be the corresponding irreducible character of the symmetric ...
2
votes
1answer
211 views

Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?

This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a ...
15
votes
3answers
5k views

Number of invertible {0,1} real matrices?

This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$. My question is: how many such matrices ...
7
votes
1answer
660 views

Counting Eulerian Orientation in a 4-regular undirected graph

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
6
votes
2answers
1k views

Is there a known formula for the number of SSYT of given shape with partition type?

Let $s_{\lambda}$ and $m_{\lambda}$ be the Schur and monomial symmetric functions indexed by an integer partition $\lambda$ ($\ell(\lambda)$ is the number of parts of $\lambda$ and $m_i(\lambda)$ is ...
5
votes
0answers
468 views

Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way? Edited to add: For the benefit of illustration, here's a few face posets: the boundary of a ...
18
votes
3answers
4k views

Number of unique determinants for an NxN (0,1)-matrix

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...
5
votes
1answer
2k views

Maximum bipartite graph (1,n) “matching”

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...
3
votes
0answers
260 views

Algebraic Kneser conjecture?

Recall that Kneser conjecture (now Lovasz theorem) claims that if the family of $k$-subsets (subsets of cardinality $k$) of given $(2k+d)$-set $M$, $d\geq 1$ are colored into $d+1$ colors, then there ...
7
votes
3answers
2k views

What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

A friend of mine and I were wondering what relationship exists between the partition numbers $p_{n}$ and the Bell numbers $B_{n}$ (and also possibly the Bell polynomials $B_{n,k}(x_1,x_2,\dots,x_{n-k+...
7
votes
4answers
3k views

Examples of inductive proofs that can be generalized by transfinite induction

Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...
4
votes
2answers
410 views

Generalization of permanent definition based on number of permutation cycles

Let $A$ be an $n$ by $n$ matrix and $x$ a free parameter. Define $$p(A,x)=\sum_{\pi \in S_n} x^{n(\pi)}A_{1\pi(1)}\ldots A_{n\pi(n)},$$ where $\pi$ ranges over the permutation group $S_n$ and $n(\pi)$ ...
3
votes
5answers
381 views

Strings and “co-subsequences”

Let $S$ be a string over some alphabet $\Sigma$. It is well known that a substring of $S$ is commonly defined as a sequence of contiguous elements from $S$, while a subsequence of $S$ is a sequence ...
7
votes
1answer
662 views

Combinatorics of lattice walks with forbidden points

If I'm not in error, the number of walks on a 2-dimensional integer lattice of length 2n steps from the origin to a point (x,y) has a nice closed form: ${2n \choose n + (x + y)/2}{2n \choose n + (x - ...
20
votes
2answers
1k views

Lifting matrices mod 2 to integers.

The following question was motivated by my research. Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs ...
1
vote
1answer
180 views

Some extremal problem for uniform hypergraph with fixed number of edges.

Let S = {1, .. ,n}. Let H = (S, E) be the m-uniform hypergraph with r edges. Let F(H, k) = #{B | |B| = k, $\exists R \in E, B \cap R = \emptyset$ } - a number of k-subsets, that doesn't intersect ...
4
votes
1answer
498 views

Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S=\{013,026,045,124,156,235,346\}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below. \[L=\left(...
43
votes
6answers
17k views

Is the Jaccard distance a distance?

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...
79
votes
17answers
87k views

Google question: In a country in which people only want boys [closed]

Hi all! Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is: ...
23
votes
5answers
2k views

What (if anything) happened to Viennot's theory of Heaps of pieces?

In 1986 G.X. Viennot published "Heaps of pieces, I : Basic definitions and combinatorial lemmas" where he developed the theory of heaps of pieces, from the abstract: a geometric interpretation of ...
5
votes
1answer
377 views

How to optimize student happiness in group work?

There are $n$ students in a class, and they must be divided into, say, $k$ groups. Each student ranks the other students in order of preference of working together. Is there a way to generally ...
27
votes
5answers
2k views

Small simplicial complexes with torsion in their homology?

Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology? For example, when $p=2$, there is a complex with 6 vertices (...
11
votes
5answers
4k views

infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
5
votes
9answers
2k views

Are there any important mathematical concepts without discrete analog?

In "continuous" mathematics there are several important notions such as covering space, fibre bundle, Morse theory, simplicial complex, differential equation, real numbers, real projective plane, etc. ...
15
votes
1answer
1k views

Making a non-monotone function monotone

Consider a function $f: \{0,1\}^n \rightarrow \{1..R\}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors. We say there is a ...
35
votes
5answers
3k views

Why do wedges of spheres often appear in combinatorics?

Robin Forman writes in "A User's Guide to Discrete Morse Theory": The reader should not get the impression that the homotopy type of a CW complex is determined by the number of cells of each ...
6
votes
1answer
948 views

Finding a cycle of fixed length in a bipartite graph

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...
5
votes
5answers
1k views

Let $G$ be a graph such that for all $u, v ∈ V (G)$, $u \ne v$, $|N (u) ∩ N (v )|$ is odd. Then show that the number of vertices in $G$ is odd

After working for sometime I figured out the following course of action. (from a few sample cases on 4 and 5 vertices) i) I wanted to prove that the graph had no odd degree vertex. ii) There exists ...
10
votes
1answer
726 views

Counting colored rook configurations in the cube - when is it even?

Informal Statement In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
13
votes
1answer
625 views

Bipartite Nim-Geography

Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...
72
votes
11answers
51k views

Sum of 'the first k' binomial coefficients for fixed n

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
29
votes
4answers
3k views

How does this relationship between the Catalan numbers and SU(2) generalize?

This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then. As ...
2
votes
2answers
2k views

Algorithmic aspects of maximizing a convex function over a convex set

Motivation The problem I am facing can be considered a variant of the standard set packing problem. However; instead of being given a list of sets, I am given a function $\nu : 2^N \rightarrow \{0,1\}...
12
votes
1answer
1k views

Combinatorial proof that large-girth graphs are sparse?

Theorem. Fix $\epsilon > 0$; for sufficiently large n, any graph with n vertices and $\epsilon \binom{n}{2}$ edges contains many (nondegenerate) cycles of length 4. The proof is simple; put an ...
4
votes
2answers
806 views

On the Bell Numbers

Edit (first version was incorrectly stated. Thank you Douglas and others for your corrections) Let $B_n$ be the $n$th Bell number (the number of partitions of a set with $n$ members). For each $n &...
4
votes
2answers
475 views

Counting distinct undirected, partially labelled graphs

Suppose I have a hexagonal tile. Each edge can be connected to any subset of the other edges (including none). Connections are undirected, so a->b implies b->a, but they're not necessarily transitive -...
36
votes
5answers
3k views

Factorials in Pascals Triangle

Hi, I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\...
38
votes
17answers
10k views

Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
4
votes
0answers
158 views

Coloring Cartesian Products with Constraints

Let $X$ and $Y$ be finite sets, and let $T_X$ (resp. $T_Y$) be a subset of the power set of $X$ (resp. of $Y$). (I think of the elements of $T_X$ as the tolerable subsets of $X$.) A strict $(T_X,T_Y)...
11
votes
0answers
646 views

A number theoretic identity

Let $n$ be a positive integer such that $2n+1$ is prime. The elements of the factor group $G = \mathbb{F}^\times_{2n+1}/\{\pm 1\}$ can be represented by the integers $1,2,\ldots,n$. For every $x \in \...
2
votes
1answer
329 views

Transitivity-related property of finite permutation groups

Let $\cal F$ denote the group of all finitely-supported permutations of $\mathbb N$. Say that a finite subgroup $G$ of $\cal F$ is singular if $G$ acts transitively on $\lbrace 1,2,3 \rbrace$ but ...
4
votes
2answers
1k views

Polya Enumeration Formula with color indifference

Polya Enumeration Formula gives us 6 equivalence classes of 2-colorings of a square. But, in the Polya coloring, the following 2 colorings belong to 2 different equivalence classes: ...
1
vote
1answer
351 views

Tournament formats

I'm looking for a format for a 4 vs. 4 tournament where the green team and blue team each has 6 players but two different people sit out each competition. How many match ups must occur before everyone ...
20
votes
3answers
994 views

The probability for a sequence to have small partial sums

The question Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that $|a_1+a_2+\dots ...
61
votes
7answers
6k views

Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes: Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
7
votes
4answers
299 views

How can I produce 'canonical' forms for rooted bipartite graphs?

The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, ...