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

7,290 questions
Filter by
Sorted by
Tagged with
4answers
2k 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 ...
1answer
607 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 ...
1answer
214 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 ...
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 ...
1answer
689 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-...
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 ...
0answers
476 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 ...
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 ...
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 ...
0answers
261 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 ...
3answers
2k views

2answers
2k 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 ...
1answer
187 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 ...
1answer
507 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(...
6answers
20k 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 ...
17answers
95k 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: ...
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 ...
1answer
385 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 ...
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 (...
5answers
5k 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 ...
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. ...
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 ...
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 ...
1answer
977 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 ...
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 ...
1answer
735 views

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 ...
2answers
945 views

17answers
11k 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, ...
0answers
165 views

1answer
332 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 ...
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: ...
1answer
352 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 ...
3answers
1k views

4answers
323 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, ...
4answers
3k views

### longest consecutive subsequence of a random permutation

What is the expected length of the longest consecutive subsequence of a random permutation of the integers 1 to N? To be more precise we are looking for the longest string of consecutive integers in ...
3answers
580 views