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,566
questions
6
votes
1
answer
77
views
Looking for the name or reference regarding a bipartite graph parameter
I'm writing a paper about a math puzzle and the thing I'm studying ends up equivalent to finding the following parameter of a bipartite graph G with parts X and Y:
The largest $k$ such that any $k$ ...
- 255
6
votes
1
answer
491
views
Induced matching number
Definition:
A matching in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an induced matching. The largest size of an induced ...
- 393
6
votes
1
answer
391
views
Is an $O(n^{d-1})$ bound known for the maximum number of edges in an ordered $n$-vertex hypergraph avoiding a fixed $d$-permutation hypergraph?
By a $d$-permutation hypergraph, I mean, for some fixed integer $k$, a $d$-uniform hypergraph on $[dk]$ with $k$ disjoint edges such that every edge has exactly one vertex from each of $\{1,\ldots,k\}$...
6
votes
1
answer
323
views
Expanding into monomials
Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$
Define the functions $f_n=...
- 41.8k
6
votes
1
answer
369
views
Maximum size of minimal sequence of transpositions whose product is a given permutation
Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...
- 291
6
votes
4
answers
551
views
Literature about a property of union closed families?
Trying to solve a problem, I fell on the following statement :
If $k$ and $r$ are natural numbers such that $r \leq k$, if a union closed family of sets ("union closed" means that the union of two ...
- 1,215
6
votes
1
answer
327
views
Zero-sum sets in union-closed families
The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ ...
- 1,169
6
votes
2
answers
603
views
Generalized cycle index polynomial for the symmetric group
The answer to a particular calculation in quantum information theory gives me the following expression:
Given $M$ specific elements of the symmetric group $S_n$, define the polynomial
$$Z_n(\pi_1, \...
- 163
6
votes
2
answers
339
views
extremal bipartite graph
I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number of ...
- 161
6
votes
2
answers
2k
views
How can I prove that these two graph coloring problems are polynomial time equivalent?
Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...
- 225
6
votes
2
answers
353
views
Is this algebra isomorphic to an incidence algebra?
This question is motivated by trying to establish a converse to Theorem 7.8 of our paper.
I have a finite poset $P$ with the following properties:
$P$ has binary meets (and hence a least element).
$...
- 37.4k
6
votes
1
answer
199
views
Sum identities with immanants
For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show
$$
\sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} \chi(...
- 93
6
votes
1
answer
399
views
What is/are the best bound/s on the sum of squares of degrees in a graph?
Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq e(\frac{2e}{...
- 6,882
6
votes
1
answer
658
views
Probability that a random edge coloring of the complete graph is proper
This is a repost of this math.se question that I am posting here since it received no attention there.
What is the probability that a random edge coloring of $K_n$ with
$m \geq n$ colors ...
- 3,433
6
votes
1
answer
768
views
Interesting behaviour of Brion's formula under a degenerate change of variables
This is, probably, a question for those knowledgeable on the subject of Brion's theorem and its applications.
Lately, I've been dealing with situations of the following sort. Suppose we are given a ...
6
votes
1
answer
322
views
Almost all loops have a trivial automorphism group; almost all groups have a non-trivial automorphism group. What goes on in between?
NB: For this question, everything is finite.
Recently I've been fascinated by the following two observations:
Almost all loops have a trivial automorphism group (McKay & Wanless, 2005, in the ...
- 4,209
6
votes
2
answers
448
views
Equidecomposable graphs, unimodality and asymptotics
I will call two graphs $G$ and $H$, $r$-equidecomposable (in analogy with Hilbert's third problem) if they can be written as unions of disjoint subgraphs
$$G\cong \bigsqcup_{i=1}^r G_i\quad ,\quad H\...
- 85.1k
6
votes
2
answers
6k
views
Proving that the complement of a bipartite graph has chromatic number equal to clique number
I'm teaching an undergraduate combinatorics class, using Harris et al.'s book ``Combinatorics and Graph Theory''. In Section 1.6 there is an exercise asking to show that for the complement of a ...
- 1,112
6
votes
2
answers
3k
views
Max cut value in a random graph
Let $G = G(n, 1/2)$ be an Erdos-Renyi graph in which each edge $e = (u,v)$ is present in the graph independently with probability $1/2$. For a subset of the vertices $S$, the cut value $c(S)$ is equal ...
- 794
6
votes
1
answer
321
views
Asymptotics for forbidden subwords
Fix an alphabet $A$ and consider words of length $n$ over $A$. Fix a set $B$ of $k$ forbidden subwords (subword is not necessarily connected, i.e. $abb$ is a subword of $abcb$). Can anything be said ...
- 3,301
6
votes
1
answer
300
views
Orbits in commutative groups.
Let A be finite commutative group say $(Z_m)^h$. I will say that $S \subset A$ is an orbit if exist group $H$
which acts on A such that $S$ is an orbit of $H$.
Can one give a simple characterization ...
- 2,149
6
votes
1
answer
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 ...
- 161
6
votes
1
answer
339
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
6
votes
1
answer
217
views
Sequence A76132 eventually periodic modulo $2,3$ and $5$
Sequence A76132 starting as $1,1,2,4,10,36,218,\ldots$ of the OEIS is recursively defined by $a(1)=1$
and $a(n)=\sum_{k=1}^{n-1}a(n-k)^k$ for $n\geq 2$.
It is eventually periodic of period 1,1 and 34 ...
- 17.5k
6
votes
1
answer
632
views
Combinatorics and symmetry in matrices under row and column swaps
Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...
6
votes
1
answer
381
views
Pairwise combinations of distinct elements
Consider a set of four elements
$$
Y^0 = \{ y_1, y_2, y_3, y_4 \}
$$
Let $Y^1$ be the set that includes all pairwise combinations of distinct elements of $Y^0$
$$
Y^1 = \{ y^1_1, \dots, y^1_6 \} := \{ ...
- 189
6
votes
1
answer
278
views
On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$
Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...
- 3,555
6
votes
2
answers
643
views
Multivariate Lagrange inversion with zero powers
(Also asked on MSE)
The multivariate Lagrange inversion formula, which I found in a couple of papers (such as this and this), is as follows. If $f_i=t_ig_i(f)$, $1\le i\le k$, then
$$ [t^n]h(f(t))=\...
- 1,417
6
votes
1
answer
393
views
Ramsey-Kuratowski numbers
A simple graph is an ordered pair of sets $\,\Gamma:=(V\,E)\,$ such that
$\,E\subseteq\binom V2.\ $ Kuratowski graph of the first kind is
$\,K_n:=\left(V\,\,\binom V2\right),\,$ where $\,n:=|V|.\,$ ...
- 4,686
6
votes
1
answer
353
views
An inequality for rearrangement-style sums
The following is a holdover from my math contest days that I never got around
to solve.
We will use the notation $\left[ k\right] $ for the set $\left\{
1,2,\ldots,k\right\} $ whenever $k$ is a ...
- 33.2k
6
votes
2
answers
262
views
Nonlinear boolean functions
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...
- 313
6
votes
1
answer
251
views
Subsets of a group with special property
Let $G$ be a finite group. We say a subset $A$ of $G$, $|A|=m$, is $(m,i)$-good, $m\geq 1$ and $0\leq i\leq m$, if there exist $g_A\in G$ such that we have $|gA\cap A|=m-i$.
I need some groups such ...
- 4,748
6
votes
1
answer
125
views
How rich is the class of vertex- and edge-transitive polytopes?
There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions.
The class of vertex-...
- 12.6k
6
votes
1
answer
393
views
Binary weight of shifted integers
Suppose $n_2$ denotes the binary representation of the integer number $n$. Let $X_2(n)=[1_22_2\ldots n_2]$,$n\geq3$, be a binary vector which is obtained by concatenating of binary representation of ...
- 4,748
6
votes
1
answer
439
views
Upper bound on the number of permutations in a set during an algorithm
Fix $n\geq 2$ and let $S_n$ be the symmetric group on $n$ letters with identity $e$. We consider elements of $S_n$ to be bijections $[n]\to [n]$ as well as sequences (one line notation). For $1\leq i&...
- 2,038
6
votes
1
answer
439
views
Rational generating function and recursion
Let $\lambda$ denote a hook of size $d$ and $c(\Box)$ the content of $ \Box \in \lambda $. Let $ \text{Hooks}(d) $ be the set of hooks with $d$ boxes. Define
\begin{align}
B(d)&=
\frac{1}{d!} \...
- 685
6
votes
1
answer
258
views
are endomorphisms "small" compared to the full transformations?
$\DeclareMathOperator\End{End}$Let $T_n$ be the full transformation semigroup/monoid of $[n]=\{1,\dots,n\}$. Let $\End(T_n)$ be the set of [endomorphisms][1] of $T_n$. Then, $\# T_n=n^n$ and
$$\# \End(...
- 41.8k
6
votes
1
answer
285
views
Combinatorics of integral over simplices
Let $\Delta_N := \{0 \leq \tau_1 \leq \dots \leq \tau_N \leq 1\}$ be the $N$-simplex. Let $a_j: [0, 1] \rightarrow \mathcal{A}$, $j=1, \dots, N$ be continuous functions with values in some (non-...
- 9,591
6
votes
2
answers
326
views
Multiplication in universal enveloping algebra in terms of PBW isomorphism
Let $\mathfrak g$ be a Lie algebra. Consider the multiplication map $m:\mathfrak g\otimes U(\mathfrak g)\to U(\mathfrak g)$ and $i:S(\mathfrak g)\to U(\mathfrak g)$ -- Poincare-Birkhoff-Witt ...
- 7,027
6
votes
1
answer
297
views
Is the exponent $2$ sharp in the Balog-Szemerédi-Gowers Theorem?
The Balog-Szemerédi-Gowers theorem can be stated in the following form: let $A,B$ be subsets of $\mathbb{Z}/n\mathbb{Z}$ (say) with equal cardinality, such that
$$
\|1_A*1_B\|_2 \ge K^{-1} \|1_A\|_1 \|...
- 4,620
6
votes
1
answer
632
views
A different equivalence relation on partizan combinatorial games
The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...
- 30.2k
6
votes
1
answer
325
views
Young-Fibonacci lattice and purely periodic continued fractions
The Fibonacci lattice $\mathcal{F}$ is the poset of all finite words consisting of 1's and 2's where a word $v$ covers a word $u$ if $v$ is obtained from $v$ by either (a) inserting a 1 in $u$ prior ...
- 1,847
6
votes
1
answer
250
views
A natural Lascoux-Schützenberger involutions on plane partitions
The Lascoux-Schützenberger involutions, $s_i$, that permute the weight of semi-standard Young tableaux are fairly known.
They satisfy some nice Coxeter relations, for example, if $v$ and $w$ are ...
- 15.6k
6
votes
1
answer
741
views
Dimension of the span of all partial derivatives of a given homogeneous symmetric polynomial $f$ and the polynomial $E(f)$
I need some help about the problem below.
Let $d\geq 4$ and $f$ a symmetric polynomial, homogeneous of degree $d$, in $n$ variables $x_1,\dots,x_n$, with real coefficients. We set
$$ E(f):=\sum_{j=1}^{...
- 307
6
votes
1
answer
820
views
How to visualise Bollobas' 1965 theorem?
Theorem
$[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} \frac{...
- 323
6
votes
1
answer
397
views
Small remarkable matroids
Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...
- 741
6
votes
2
answers
413
views
Intuition for Freiman dimension
Let $A\subset G$ and $B\subset H$ be subsets of abelian groups. We say that a map $f\colon A\to B$ is a Freiman homomorphism if for all $a_1,\dots, a_4\in A$ one has
$$f(a_1)+f(a_2)=f(a_3)+f(a_4),\...
- 311
6
votes
1
answer
185
views
Maximizing ratio volume/diameter^n by an affinity
Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant $\...
- 4,761
6
votes
2
answers
1k
views
Generalisations of Petersen's 2-factor theorem?
Petersen's 2-Factor Theorem (1891): A $(2r)$-regular graph can be decomposed into $r$ edge-disjoint $2$-factors.
I'd like to use this theorem (or a more general version of this theorem) to imply the ...
- 4,209
6
votes
1
answer
1k
views
Simple lower bounds for Bell numbers (number of set partitions)?
The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements.
It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, ...
- 2,330