# Tagged Questions

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

0answers
59 views

### bounded degree graph colouring.

I was wondering if anyone could provide references on the following: Is determining the chromatic number of a bounded degree graph APX-complete? 2.I've seen the result that states it is NP-hard ...
0answers
73 views

### Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
1answer
83 views

1answer
179 views

### A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...
0answers
59 views

### Terminology and technique for repeated pairwise removal of elements of posets: “Collapsibility” of a “face poset”

Let $P$ be a poset, or partially ordered set. Let $\le$ denote the reflexive order on $P$, and $<$ the corresponding irreflexive order. Let the phrase "a maximal pair" in $P$ refer to an ordered ...
1answer
66 views

### Separate a special poset by function

Assume $A = \prod_{i=1}^n\{0,1\}$, i.e. element $(a_1,\cdots,a_n)=a\in A$ is n-tuples like $(1,0,1,\cdots)$. There is an obvious partial order on the $A$: say $a < b$ for $a,b\in A$ if and only ...
0answers
74 views

### Relating face polytopes of permutohedra to integer partitions

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
1answer
124 views

### Union-closed family generated by n 2-sets

I asked this question on Stackexchange, but I got no answer, so I ask it here. Let us define a $2$-set as a set with exactly $2$ elements. For a natural number $n$, let $l(n)$ denote the least ...
0answers
65 views

### Lower bound the ratio of the combinatorial quantities

Suppose $p < q$, $s = p^{d}$ for some fixed $d \in (0,1)$, let $p$ goes to infinity, define the following quantity, \begin{aligned} \quad f(j) = \sum_{i = 0}^{\min(j,s)}{s \choose i}{p-s \choose i}{...
2answers
225 views

### sum over all integer partitions, of the product of the factorials of the terms

I'm looking for something making tractable the sum, over all partitions into k terms of an integer n, of the product of the factorials of all the terms. Thanks,
0answers
71 views

### connectedness of semi algebraic sets

We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...
1answer
154 views

### Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
1answer
113 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices. Analogously, what is the ...
1answer
140 views

### Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution

Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where $$Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.$$ To ...
0answers
183 views

### First to note/document the relation between permutohedra and multiplicative inversion

The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...
1answer
135 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...
1answer
138 views

### “Small” simplicial complex with torsion trees

I am giving an expository talk soon about Duval-Klivans-Martin's paper Simplicial Matrix Tree Theorems, and I've been struggling to find a good example to do at the board. An important aspect of the ...
1answer
165 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...
1answer
287 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
1answer
191 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...
0answers
81 views

1answer
70 views

2answers
253 views

1answer
58 views