## New answers tagged co.combinatorics

12

This is all worked out in the article "A class of simple Moufang loops" by L.J. Paige. The short answer is that the loop of units has size $q^3(q^4-1)(q-1)$, and is not associative for $q\notin \{2,3\}$.
The article actually shows that a certain subloop modulo its center is a simple Moufang loop. At the time before Paige's result, the only simple ...

0

There is also the (old) book of Seneta: Non-negative Matrices and Markov Chains.
First edition: 1973. See chapters 3-4.

2

Consider the following set of conditions. Before one swaps $b(k+1)$,
$b(i)$ is an increasing with $i$ sequence for $i$ less than $k+1$. (And for large enough $k$, $b(k)$ is greater than $k$.)
For $i$ larger than $k$, $b(i)$ is at most $i$.
$b(i)$ is less than $i$ exactly when $i$ is greater than $k$ and $i$ is part of the increasing sequence ($i$ is one ...

5

I'm not sure that the descriptions so far work. They seem to result in things like
$ 0, 1, 2, 0, 3, 1, 4, 0, 5, 1, 6, 0, 7, 1, 8, 0, 9, 1, 10,\cdots$
Here is something that works.
The sequence starts $0, 1, 2, 0, 3, 2, 4, 3, 1, 4, 0, 5, 4, 6, 5, 3, 6, 2, 5, 1, 6$ so the pairs visited are
$ (0, 1), (1, 2), (0, 2), (0, 3), (2, 3), (2, 4), (3, 4), (1, 3), (1, ...

1

I wonder if the probability is dependent only on $r_i$, or also dependent on
the placement of $R$ within $S$?
In these two examples,
it takes an average of $2.70$ steps to reach slicing $R$ on the left, but
$3.16$ steps on the right.
I realize I'm ignoring your condition that $s_i \gg r_i$.
Added 4Aug2020.
I include ...

answered Aug 1 at 23:00

Joseph O'Rourke

133k2222 gold badges270270 silver badges783783 bronze badges

2

This answer has been updated with an explicit example showing more conditions are needed. After the example we give some additional necessary conditions.
Let $f(x,y) = \sum_{j=0}^n a_j x^{n-j}y^j$. One other simple condition not in the question is $a_j \leq \binom{n}{j}$. But we also need some lower bounds of the coefficients $a_j$.
Consider the nonlinear ...

2

This is also too long for a comment but it shows where the real problem lies.
With the new formulation, the complementary expectation of the sum of two cut sides is just of the form
$$
\frac {\sum_i a_i^2(|\cos\theta_i|+|\sin\theta_i|)}{\max_i(a_i|\cos\theta_i|)+\max_i(a_i|\sin\theta_i|)}
$$
where $a_i$ are the sides and the angles $\theta_i$ that the sides $...

7

$\ell(v)!$ is of course even if $\ell(v)>1$, so the statement is really that $N_v$ is even for $\ell(v)>1$. We find a fixed-point free involution on the set of such Bruhat paths. Suppose that $v_2,v_3,\ldots$ are fixed. By the diamond property of Bruhat order there are exactly two possibilities for $v_1$. This gives the involution we want (in fact many ...

2

For the orthogonal case (B and D), this was developed in great detail in Elie Cartan's "Theory of Spinors" (Dover Publications Inc, Mineola N.Y., 1981); see also:
Claude Chevalley, "The Algebraic Theory of Spinors and Clifford Algebras" (Springer, 1996, Vol. 2 of collecteed works). Of special importance are the "maximal" ...

3

I got here via this question and I thought it may be worth sharing the following uncountable family of locally finite examples:
Pick an arbitrary set $S \subseteq \mathbb Z$. The vertex set of the graph $G_S$ is $\mathbb Z \times \mathbb Z$. For the edge set take all "vertical" edges from $(m,n)$ to $(m,n+1)$, horizontal edges $(m,n)$ to $(m+1,n)$ ...

2

Let the vertices of the triangle be $A$, $B$, and $C$, which we also use for the angle measures, opposite the sides of lengths $a$, $b$ and $c$ respectively.
Suppose we know that in the ideal configuration, a horizontal line cuts the triangle at $A$, and a vertical line cuts the triangle at $B$. Let $\theta$ be the angle between the horizontal line and side $...

1

A bit too long for a comment, here's one suggestion: take $a\lt b\lt c$ and use $(0,0)$ and $(c,0)$ as two points of the triangle. The third point $(x,y)$ (taking $y\gt 0$ WLOG) can be found in whatever usual way you prefer. Now, instead of rotating the triangle, rotate the lines: we can parametrize the pencils of lines as being in the directions $(\cos\...

20

@user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished:
If I understand your comment to my answer correctly, you are aiming to change your algorithm for the torus so it works with ${\rm cr}(G)$. I think the whole MO community is keeping their fingers ...

4

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.
First color the edges in the bigraph between $A$ and $...

9

The answer to your question is no. If you have an irrdeucible projective variety $X$ of dimension $d$ with an affine paving, then for all $i < d/2$, the number of $i$-cells is less than or equal to the number of $(d-i)$-cells. This is the main idea of this paper by Bjorner and Ekedahl:
https://arxiv.org/pdf/math/0508022.pdf
The proof is as follows: the ...

4

An affirmative answer to your question would follow from a famous conjecture about envy-free allocations. It is also known that if you replace the '2' in $b$-goodness with '$\frac 12$', then it is true.
A good paper to read (first) on the topic is Almost Envy-Freeness with General Valuations.
An allocation of some items among some players is envy-free up to ...

36

Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community,
an asymptotic variant of the crossing lemma, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, is true even for the pair crossing number on a fixed surface, such as a torus.
With Radoslav Fulek [...

3

The answer is no.
Let $G$ be the Hoffman-Singleton graph (hence n=50, k=42). Let $C_k$ be the disjoint union of 5 $K_8$s and a $K_{10}-C$ ($K_{10}$ with a 10-cycle removed). Any proper induced subgraph of $C_k$ with maximum degree at least 4 will contain a $C_3$ or $C_4$, which $G$ does not contain.

3

I corrected my computation and it turns out the assumptions required by Theorem 1.1 in the paper are not satisfied. Many thanks to everyone, who spent time reading my long writing. Cheers.

4

I do not know of a direct connection to Roth or SzemerÃ©di over the integers. However, the paper
N. Alon, A. Shpilka and C. Umans, On Sunflowers and Matrix Multiplication, 2012 IEEE 27th Conference on Computational Complexity, Porto, 2012, pp. 214-223, doi:10.1109/CCC.2012.26 (author pdf)
shows that a proof of the Sunflower Conjecture would imply a bound ...

4

In Addition to Geck-Pfeiffer: Small values of the a-function are also contained in Geck, Jacon - Representations of Hecke algebras at roots of unity. In particular, for $G_2$ it's in Table 1.3.; for $F_4$ it's table 1.2.; other values are available through combinatorially formulas (for example type $A$ is completely covered in section 2.8) and Remark 1.3.11 ...

135

$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known whether it also holds on the torus.
The best and most current reference for you could be the survey article from Schaefer, updated in February 2020: â€œThe Graph ...

4

I assume you mean "there always exist $\tau_i$ such that $s_i^{t_i}(\tau_i) = 1$ and $s_j^{t_j}(\tau_i) = 0$ for $i \neq j$", i.e. you want that no matter how the sequences are shifted, each sequence has at least one bit which is zero in the other shifted sequences, and that's the slot when it manages to send its packet in your application.
(What ...

2

The notion of $\mathcal{C}_j(G)$ is natural in terms of hypergraphs where is has been studied. If you rephrase in terms of a hypergraphs, then $\mathcal{C}_j(G)$ becomes the independence complex of the hypergraph. These have been studied a lot in (combinatorial) commutative algebra.
An independent set in a hypergraph is any subset of vertices which does not ...

5

We can get a lower bound on the order of $n \log n$.
I'll describe how to arrange $4^n$ points in general position to get $n 4^{n-1}$ squares.
The arrangement is described recursively. For the base case $n=1$, we have $4^1 = 4$ points, and you can probably guess how we should arrange them to get $1 \cdot 4^{1-1} = 1$ squares. Now suppose we have an ...

1

To add to my previous answer, a paper of SzabÃ³ and Tardos from 2006 ("Extremal problems for transversals in graphs with bounded degree") has a result related to the complex you defined in 2.

4

The closest thing to an official account of why JCT split into JCTA and JCTB may be found in Edwin F. Beschler's article Gian-Carlo Rota and the Founding of the Journal of Combinatorial Theory, J. Combin. Theory Ser. A 91 (2000), 2â€“4.
However, no single journal or set of editors, prestigious and hard-working as they might be, could overcome the tremendous ...

7

The Electronic Journal of Combinatorics has many Dynamic Surveys one of which is The Graph Crossing Number and its Variants: A Survey by Schaefer which first appeared in 2013 and has been updated as recently as Feb 14, 2020. From the bottom of page 40 onto page 41 you will find this conjecture for complete bipartite graphs discussed (with many references). ...

4

It is a fascinating conjecture. The following might be a good reference for you: In 1997, Richter & Thomassen showed that
$$\lim_{n\to\infty}cr(K_{n,n})\left(\begin{array}{c} n \\ 2 \end{array}\right)^{-2}$$
exists and is at most $1/4$. If the conjecture is true, the value of this limit is exactly $1/4$.
(R.B. Richter, C. Thomassen, "Relations ...

4

I think the following graph works for $k = 1$:
It clearly has crossing number at most $2$ and local crossing number $1$.
In any drawing with $2$ or fewer crossings, the green cycles cannot cross (the spokes from the red vertices would create at least one additional crossing). Once we have embedded the green cycles and the black matching edges between them, ...

4

A recent paper of mine on permutation enumeration that uses cyclotomic polynomials is I. M. Gessel, Reciprocals of exponential polynomials and permutation enumeration, Australasian J. Combin. 74 (2) (2019), 364â€“370.

6

A Markov chain on the symmetric group with this transition graph (but with directed edges and weights) was investigated by Lam and Williams. This has since received considerable attention, and has been connected to "TASEP on a ring" if you are looking for search words (it doesn't appear that the graph itself has a name in this context).
I should ...

2

I figured out the details, and wrote it up here. I did not manage to find a good reference. There are a few nice surveys on RSK and on crystals, but a survey covering how different tableau operators interact would be nice to see someone type up.
For the interested, these properties above were needed for this project, where we look at a type of skew q-...

answered Jul 25 at 11:05

Per Alexandersson

12.5k88 gold badges5353 silver badges104104 bronze badges

3

I was recently thinking about this question again and I came up with another way to explain the result $$\mathcal H_{\lambda}=\left\{ h(i,j)\right\}_{(i,j)\in \lambda}\succcurlyeq \left\{ h^{*}(i,j)\right\}_{(i,j)\in \lambda}=\mathcal H^{*}_{\lambda} \tag{1}$$
in a way that (i) combinatorially describes the sequence of Robin Hood moves to get from $\mathcal ...

1

Assuming that you mean to precolour $k$ subdiagonals and have no further constraints on the precolouring, the answer to both of your questions is no.
For every $n$ there is a precolouring which cannot be extended: choose colours $1, \dots n/2$ in the first row and colours $n/2+1, \dots, n-1$ in the second row (and thus the second column). Then there is no ...

1

For the case $n=8$, with the precoloring you describe the completion you give is indeed unique. I checked by writing the corresponding boolean program and let a solver enumerate all solutions: there is only one.
For the case $n=10$, consider the pre-colored $K_{10}$
$$\left(\begin{array}{rrrrrrrrrr}
X & & & & & 1 & 8 & 4 &...

0

I do not think there is a standard name for this, but I may prefer to call it $p$-random chromatic number....

8

There are no such graphs when $n$ is odd, by the handshaking lemma.
Conversely, for all even $n \geq 224$, we claim such a graph exists.
In particular, given two planar 5-regular graphs $G$, $H$ each drawn on the surface of a sphere, we can define the 'connected sum' of the graphs as follows:
remove a small disk (containing one vertex) from the sphere on ...

8

There is a 3-connected 5-regular simple $n$-vertex planar graph if and only if $n=12$ or $n \ge 16$ is even. See Recursive generation of 5-regular graphs by Mahdieh Hasheminezhad, Brendan D. McKay, Tristan Reeves in WALCOM: Algorithms and Computation, eds. Das and Uehara, Lecture Notes in Computer Science, vol 5431, Springer 2009. The number of such graphs ...

0

Dmitri's answer is definitely correct. I just want to add my geometric intuition, and a generalization, which, in hindsight, is quite obvious.
All in all, we can have the following:
If $P\subset\Bbb R^d$ is a polytope with $n$ facets, each of which is combinatorially (or projectively) equivalent to $Q\subset\smash{\Bbb R^{d-1}}\!$, then for each $k\ge 1$ ...

2

You might want to read up on the principal specialization.
It specializes a symmetric function into a formal power series.
For example, the symmetric function $s_1(x) = x_1+x_2+ \dotsb$
has principal specialization $s_1(1,q,q^2,\dotsc) = 1+q+q^2+\dotsb = \frac{1}{1-q}$, so it does not make sense to let $q\to 1$. The expression only exist as a formal power ...

answered Jul 20 at 20:09

Per Alexandersson

12.5k88 gold badges5353 silver badges104104 bronze badges

4

This is a conjectural answer.
Let $w = 0\dots01$ be a binary word of length $n$. Then $\phi(w)$ is the Dyck path $U^{(n+1)/2} (UD)^{(n-1)/2} D^{(n+1)/2}$ if $n$ is odd and $U^{n/2} (UD)^{n/2} D^{n/2}$ if $n$ is even.
Let $w = 0^{n_1} 1 0^{n_2} 1 \dots 0^{n_k} 1$ be any binary word ending with a $1$. Then $\phi(w) = \phi(0^{n_1} 1) \phi(0^{n_2} 1)\dots \phi(...

2

I think Timothy Chow's comment is right that there is no result about planar graphs with your lemma as an explicit corollary.
I believe the following 2007 research paper by Guido Helden might be of use to you: http://publications.rwth-aachen.de/record/62349/ It is about hamiltonicity of maximal planar graphs and planar triangulations, and starts with a very ...

2

Your irregular $(3,2)$-nice graph is almost a De Bruijn graph.
Label the vertices ($0$ to $8$) with $12,21,11,22,10,02,20,01,00.$ Then the deviations are that your edges $$1\rightarrow 6 \ \&\ 3\rightarrow 4 \mbox{ should be switched to edges } 1\rightarrow 4\ \& \ 3\rightarrow 6.$$ i.e. $$21\rightarrow 20\ \&\ 22\rightarrow 10 \mbox{ should ...

2

Equation (1) from the above answer can also be viewed as the case in which $n=1$ for $w(n,l).$ This is simply because the number of closed walks of length $2l$ on a one-dimensional cube is always 1 regardless of $n$.

4

This is a kind of inclusion-exclusion related to the identity
$$
\sum_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1)
$$
for all $m=1,2,\ldots$.
For a route on the $n$-cube with first step being vertical we label other $2k-1$ vertical steps, take a weight $(-1)^{k+1}A(2k-1)$ for such a configuration and sum up. For given $k$, you may choose $2k-...

2

This is a non-3-connected 1-planar example...

3

For an answer, see discussion of the degree of the Sperner boundary labelling in the Musin (2014) article https://arxiv.org/pdf/1405.7513.pdf
If the pdf link does not work try https://arxiv.org/abs/1405.7513
Effectively, a valid Sperner boundary labelling is a piecewise linear automorphism on the boundary with odd degree.

2

Under the assumption that $F(2i,n) = 0$ when $i<4$ or $2i>n$, the first and second cases in the recurrence become partial cases of the third one. Hence, the recurrence reduces to
$$F(2i,n) =
\begin{cases}
1, & \text{if } i=2,\ n=4;\\
0, & \text{if } i<2\text{ or } 2i>n;\\
\frac{2i+n-4}{2n-5}F(2i,n-1)+\frac{n-2i+1}{2n-5}F(2i-2,n-1) & \...

15

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics" (see p.481) with the main ingredients being singularity analysis and the relation
$$I(z)=H(z)-\frac{1}{2}\left(H(z)^2-H(z^2)\right)$$
where $I$ is the ...

Top 50 recent answers are included

#### Related Tags

co.combinatorics × 7894graph-theory × 1650

nt.number-theory × 816

reference-request × 671

pr.probability × 618

discrete-geometry × 399

rt.representation-theory × 362

gr.group-theory × 355

linear-algebra × 341

graph-colorings × 248

algorithms × 233

permutations × 228

ag.algebraic-geometry × 214

additive-combinatorics × 209

enumerative-combinatorics × 203

computational-complexity × 189

convex-polytopes × 184

partitions × 180

matrices × 178

binomial-coefficients × 176

mg.metric-geometry × 172

polynomials × 168

sequences-and-series × 158

finite-groups × 150

set-theory × 129