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

6,443 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

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 ...
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 ...
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(...
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 ...
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: ...
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 ...
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 ...
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 (...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
726 views

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 ...
806 views

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, ...
158 views

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