# 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,658 questions
0answers
16 views

1answer
52 views

### Intersection of quadratic equations with planted solutions?

Suppose we have two quadratic equations in $\mathbb R[x_1,\dots, x_n]$. What is the expected dimension of their intersection? In general what can we say about intersection of $k$ quadratics? How many ...
1answer
81 views

1answer
341 views

0answers
55 views

### Kac-Moody groups for non-crystallographic root systems

Given a finite-dimensional crystallographic root system, we can construct an associated Kac-Moody group, with a corresponding flag variety and Littlewood-Richardson coefficients. Between a pair of ...
1answer
221 views

### Counting the forests obtainable by removing subtrees from binary trees

Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level). For any ...
0answers
57 views

### Minimize number of lattice paths below a given path

Every north-east lattice path (NE-path) $v$ from $(0,0)$ to $(k, a)$ can be identified with a sequence $0 \le \lambda_1 \le \lambda_2 \le . . . \le \lambda_k\le a$, that represent the hight of each ...
1answer
22 views

### Coloring cliques of a clique decomposition of the complete graph

Let $G=K_k$, the complete graph on $k$ vertices. Consider the cliques induced by the sets of edges of a clique decomposition of $G$. Can you $k$-color the edges of $G$ so that each of the cliques in ...
0answers
26 views

### Counting triangles with small intersection in a complete graph

Let $G=K_k$ be the complete graph on $k$ vertices. Consider triangles (subgraphs induced by three vertices) which intersect pairwise in at most one vertex. What is the maximum number of these that ...
1answer
69 views

### The expectation of partition times needed separate two elements in a set

I met a problem which can be formulated as set partition. Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set ...
2answers
292 views

### How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\cdots,\log(n)$?

How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\dotsc,\log(n)$? Data for $n=1,2,3,\dotsc$ computed with Sage: 1, 1, 1, 2, 2, 5, ...
0answers
26 views

### Metric conversion in trees?

Say you have a balanced binary decision tree with depth $L$ and we know the sequence $p_1$ of $0/1$ decisions we need to make from root to one of the leaves $\ell_1$. This $0/1$ string is what I call ...
0answers
75 views

### Coloring triples in trees

Definitions Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...
1answer
126 views

### Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...
1answer
93 views

### Uniform partitioning of regular graphs

Consider a symmetric or arc-transitive graph except the odd cycle. Then, is it true that the graph could be partitioned into distinct parts such that each part has equal number of vertices except for ...
1answer
128 views

### Generating bitstring combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...
2answers
86 views

### How to use probability to find a matching in a family of graphs?

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...