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.
10,559
questions
6
votes
4
answers
3k
views
How to describe a tree? (depth, degree, balance, ... what else?)
Hello,
I do have a collection of trees (mind maps, actually) and want to formally describe this collection of trees.
My first question: how can I describe a tree? Are there any metrics to express ...
- 63
6
votes
4
answers
2k
views
Examples of Super-polynomial time algorithmic/induction proofs?
In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:
-The proof moves through stages
-An invariant is shown to hold by induction from previous stages
-...
- 1,088
6
votes
1
answer
425
views
Three conjectural series for $\pi^2$ and related identities
Recently, I found the following three (conjectural) identities for $\pi^2$:
$$\sum_{k=1}^\infty\frac{145k^2-104k+18}{k^3(2k-1)\binom{2k}k\binom{3k}k^2}=\frac{\pi^2}3,\tag{1}$$
$$\sum_{k=1}^\infty\frac{...
- 14.5k
6
votes
1
answer
372
views
Algebra generated by transformation matrices
Let $T_n$ be the full transformation monoid of an $n$-set $N_n$ with elements 1,...,n consisting of all functions $f: N_n \rightarrow N_n$.
We can associate to each function $f$ a matrix $M_f$ in the ...
- 26.1k
6
votes
2
answers
279
views
Signs of Kravchuk matrix asymptotically produce a large circular region with hyperbolic sinks. Why?
The Kravchuk matrix of dimension $n+1$ is such that its entries satisfy $$K_{i,j}^{(n+1)}=[x^i](1+x)^{n-j}(1-x)^j\quad\forall0\le i,j\le n.$$ It enjoys properties such as involution and has various ...
- 803
6
votes
1
answer
329
views
Can there be an application of discrete mathematics in PDEs, mainly the ones used in hydrodynamics?
Can there be applications of graph theory, combinatorics etc. in PDEs mainly hydrodynamics?
Tried my luck with Google's search engine, didn't show much info.
I guess you can try to use these features ...
- 1,524
6
votes
1
answer
190
views
Order ideals of positive root systems and avoiding group elements in the Weyl group
Let $X$ be the poset of positive roots of a finite root system of Dynkin type $Q$.
Question 1: In Dynkin type $A_n$, is it true that the poset of order ideals of $X$ is isomorphic to the poset of [2,...
- 26.1k
6
votes
1
answer
184
views
Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three colors?
Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color ...
- 1,666
6
votes
1
answer
465
views
$a^{th}$-root of exponential generating functions
This is a quick follow up on R. Stanley's interesting post on MO in a different direction, which might be easier.
For positive integers $a$, define the family of functions (infinite series) given by
$$...
- 41.8k
6
votes
1
answer
232
views
A combinatorics problem and the probability interpretation
For a gaussian vector variable $w\sim N(0,I_{n\times n})$, the moments of square norm are $\mathbb{E} \|w\|^{2 r} = \prod_{t=0}^{r-1} (n + 2 t)$.
Based on Isserlis' theorem, $\mathbb{E} \|w\|^{2 r}$ ...
- 75
6
votes
1
answer
264
views
Limits (growth rates) of power series coefficients
Take two positive integers $m$ and $n$ and consider the rational function
$$G_{m,n}(x,t)=\frac{d}{dx}\left(\frac1{(1-x^m)(1-tx^n)}\right)$$
and the corresponding Taylor expansion as
$$G_{m,n}(x,t)=u_0(...
- 41.8k
6
votes
1
answer
271
views
Is this bound uniform in $N$?
I encountered this small combinatorial problem and do not quite know how to solve it:
Consider a set $\mathbf N:=\left\{1,2,....,N \right\}.$ This set has $\binom{N}{2}$ many subsets of cardinality $...
- 225
6
votes
1
answer
340
views
A transversal matroid whose dual is not transversal
In Oxley's Matroid Theory, Problem 14.8.5, it states that it is (or at least was in 1992) an open problem to determine when the dual matroid of a transversal matroid is also transversal. I had assumed ...
- 63
6
votes
1
answer
1k
views
Proof of Fisher's inequality in combinatorial terms
Suppose $n$ is a positive integer. Let ${\cal C}$ be a set of subsets of $X:=\{1,\ldots,n\}$ with the following properties:
all members of ${\cal C}$ contain at least $2$ elements, and $X\notin {\cal ...
- 45.4k
6
votes
1
answer
122
views
Have this generalization of Indifference graphs been studied before?
Indifference graphs are those graphs $G=(V,E)$ for which there exists a real-valued function $f$ defined on $V(G)$ such that, if $u$ and $v$ are distinct vertices, $|f(u)−f(v)| \lt 1$ if and only if $\...
- 519
6
votes
2
answers
2k
views
Convergence issues with infinite product of formal series
Question first:
Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have
$$ P(x) \equiv \prod_{j=1}^\infty (1 - ...
- 1,167
6
votes
2
answers
640
views
In a random graph which one is more probable, $k$-clique or $k$-core?
Recall that the $k$-core of a graph $G$ is the unique maximal subgraph of $G$ with minimum degree at least $k$.
In an Erdos-Renyi random graph, where the edge selection is independent with ...
- 177
6
votes
2
answers
535
views
Four Dimensional Rook Domination
Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...
- 415
6
votes
2
answers
164
views
Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?
For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
- 13.2k
6
votes
1
answer
1k
views
Parking Functions and the Binomial Theorem
Cross-post from https://math.stackexchange.com/questions/808490/parking-functions-and-the-binomial-theorem
A parking function is a function $f: \{1, \ldots n\} \rightarrow \{1, \ldots n\}$ which has ...
- 455
6
votes
2
answers
404
views
Triangulations of special polyhedra
Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
- 213
6
votes
1
answer
482
views
Are semigroups with finite-to-one right multiplication "moving"?
A semigroup $S$ is moving if $S$ is infinite, and for all finite
$F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that,
for all but finitely many $s\in S$,
$$
\{a_{...
- 3,104
6
votes
3
answers
418
views
Name for Kneser/Johnson-like graphs?
I wonder if the following simple generalization of Johnson and Kneser
graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the
set of $k$-element subsets of an $n$-set, with two $k$-sets ...
- 349
6
votes
2
answers
382
views
Overlapping sets
Consider the following problem:
Let $F \subseteq 2^{I}$ be a finite family of finite subsets of some index set $I.$
Let $F_x$ be defined as the number of elements of $F$ that contains $x.$
Assume ...
- 15.6k
6
votes
3
answers
575
views
Reference for partial Hadamard matrices
Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
- 1,985
6
votes
3
answers
2k
views
References on techniques for solving equations with discontinuous functions such as floor and ceiling?
Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...
- 524
6
votes
2
answers
378
views
Lattice-cube minimal blocking sets
Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...
- 149k
6
votes
3
answers
801
views
A simple stopping time problem.
This should be rather standard so I hope somebody with a good background in probability theory would give me a quick solution or a reference.
We are given a threshold positive integer $T>0$. Let $...
- 195
6
votes
1
answer
1k
views
Symmetric basis of harmonic homogeneous polynomials
Recently, a question about the beautiful theory of harmonic polynomials made me aware there is something
I've wanted to know for a long time.
As is well known, for any number of variables $n$ and any ...
- 56.6k
6
votes
1
answer
441
views
Orthogonal Complements of Root Lattices in E_8
I have a rather stupid lattice theory question. Suppose $L$ is a root lattice that can be primitively embedded in the $ E_8 $ lattice. Is the orthogonal complement of $ L$ in $E_8$ unique up to ...
- 309
6
votes
3
answers
10k
views
Maximum flow with negative capacities?
I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
- 83
6
votes
2
answers
461
views
What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?
This problem arose in the study of Latin squares with a large number of subsquares, although it appears interesting in its own right.
Question: What is the maximum cardinality of a family $F \...
- 4,209
6
votes
3
answers
1k
views
Online Library of Unlabeled Connected Graphs on n Vertices
Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...
- 1,314
6
votes
1
answer
389
views
Relations in symmetric group
It would be nice to find out what is known about the following problem.
First let us consider a free group $F$ with two generators $a$ and $b$. We are interested in its elements that are
not equal ...
- 1,771
6
votes
3
answers
2k
views
What is the relationship between modular forms and the Rogers-Ramanujan identities?
Let G(q) be the generating function for partitions such that if k is a part, then it occurs once and k+1 is not a part.
Let H(q) be the generating function for partitions with the same condition plus ...
- 553
6
votes
2
answers
1k
views
diameter of a graph with random edge weights
Given a weighted directed graph $G=(V,E, w)$, suppose we generate a new graph $G'=(V,E,w')$ with the same vertices and edges, but now letting the weight of edge $(i,j)$ be
an exponential random ...
- 966
6
votes
3
answers
1k
views
Is there a software package that does Schubert Calculus computations?
Is there a good software package for doing computations in the cohomology ring of Grassmannians? Things like, I can write down a polynomial in, in fact, special Schubert classes, but it's one where ...
- 15.8k
6
votes
1
answer
151
views
Approximating distance on a finite graph with Hamming distance
For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...
- 1,262
6
votes
1
answer
241
views
Pair matching between divisors less and more than $\sqrt{N}$
Let $n$ be the positive integer. Let $A$ and $B$ be sets of divisors of $n$ less and more than $\sqrt{n}$ respectively.
Consider bipartite graph $(A, B)$, where two vertices are connected when one ...
- 163
6
votes
1
answer
527
views
Does Playfair imply Proclus?
I am interested in the interplay between the Playfair and Proclus Axioms in linear spaces.
By a linear space I understand a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of ...
- 40.9k
6
votes
1
answer
197
views
Preserve validity between the two Kripke frames
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
- 63
6
votes
1
answer
482
views
A numerical matrix of power sum polynomials
Let $p_i=x_1^i+x_2^i+\cdots+x_m^i=\sum_{k=1}^mx_k^i$ be the power sum polynomials. Then, the determinant of the $m\times m$ Hankel matrix $M_m=(p_{i+j-2})$, for $1\leq i,j\leq m$, has a neat ...
- 41.8k
6
votes
1
answer
258
views
A Sauer-Shelah-like lermma for prefix tree
I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known.
Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
- 419
6
votes
1
answer
71
views
Special clique in perfect graph
It is well known that in a perfect graph, there exists a clique which intersects all maximum independent sets (stable set), as in the proof of weak perfect graph theorem. So I want to know is the ...
- 1,320
6
votes
1
answer
468
views
A question about colorings of the vertices of a p-agon, where p is prime
Let $V$ be the vertices of a regular $p$-agon in the plane, where $p$ is prime, and let $C$ be a set. Given two maps $f,g:V\rightarrow C,$ I believe it is true that either
(a) $f=g\circ r$ for some ...
- 322
6
votes
1
answer
256
views
Tanglegrams and functional equations of M. Somos
Recent references on the matter at hand include, a lecture slide The Konvalinka-Amdeberhan conjecture
and plethystic inverses and a preprint on Counting tanglegrams with species by I. Gessel; the ...
- 41.8k
6
votes
1
answer
552
views
Properties a triangulation must have in order to describe a manifold
I am mainly interested in the $3$-dimensional case. It is a well-known fact, following from the work of E. E. Moise and R. H. Bing in the 1950s, that every $3$-dimensional topological manifold (with ...
- 1,147
6
votes
1
answer
420
views
Bounding size of partial difference sets given size of partial sumsets
In this paper by Katz and Tao, the following bounds were established.
Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b)...
- 3,413
6
votes
1
answer
570
views
Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbidden minors of matroids over arbitrary finite fields?
About six years ago there was a proof announced and later outlined in a notice from AMS. However right now I can only seem to find forbidden minor characterizations for matroids linearly ...
- 2,506