co.combinatorics – A query on Galvin’s theorem for bipartite graphs

The Galvin’s theorem is the generalized version of Dinitz conjecture that states that if the maximum degree of any bipartite graph is $Delta$, then its edges are colorable properly if each of its edges is given a list of $Delta$ colors to choose from.

The proof, as I have seen, is by using the fact that there exists a kernel perfect orientation of the line graph of bipartite graph. But, I have a method as follows: We know that even cycles are chromatic edge-choosable. The bipartite graphs consist of even cycles and possible chords (matchings). As each of the even cycle can be list edge colored with a list of exactly two colors, and the chords (matchings) can be list edge colored using a list having just one color, I think a suitable greedy list edge coloring ( by assigning a list of $Delta$ colors to each edge) would solve the problem.

What is the defect in the method above? Thanks beforehand.

co.combinatorics – Tree-width of graphs in which any two induced cycles touch

Let $G$ be a graph s.t. any two cycles $C_1, C_2 subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph obtained from $G$ by deleting $C$ and all neighbors of $C$ is acyclic. Let’s denote the class of all such graphs by $mathcal{G}$.

The cycle $C_n$, the complete graph $K_n$ and the complete bipartite graph $K_{s,t}$ are rather trivial examples of such graphs.

Are there constants $g, t$ such that all $G in mathcal{G}$ of girth at least $g$ (that is, all cycles of $G$ have length $> g$) have tree-width at most $t$?

co.combinatorics – Injective choice function for finite Fano planes

Let $H=(V,E)$ be a hypergraph that is a finite Fano plane, that is, $V$ is a finite set and $E$ has the following properties:

  1. for $e_1neq e_2in E$ we have $|e_1|=|e_2|$, as well as $|e_1cap e_2|=1$, and
  2. for $vneq win V$ there is a (unique) $ein E$ with ${v,w}in e$.

Is there always an injective map $f:E to V$ with $f(e)in e$ for all $ein E$?

co.combinatorics – Discrete Math – Modular Equations

I’m not sure how to go about doing this. There exists an ‘x’ value between 0 and 21 that satisfies both equations:

x mod 3 = 2
x mod 7 = 4

How do I solve these equations for x? (not by just testing x values, but how to actually solve this)

EDIT: I keep trying to change the tag to discrete-mathematics but it doesn’t work and is stuck as co.combinatorics. Not sure why.

co.combinatorics – Number of cells in array covered by a random permutation

Consider a set $A subseteq (n) times (n)$ with $|A| = a = alpha n$ for some $alpha in (0,1)$.

Suppose we select a permutation $pi in S_n$ uniformly at random. This permutation $pi$ can also be viewed as a subset of $(n) times (n)$. Then the random variable $|pi cap A|$ is the number of cells of $A$ meeting $pi$, i.e. the number of pairs $(x,y) in A$ with $pi(x) = y$.

My question is this: for some fixed value $r geq 1$ and fixed value of $alpha$, and letting $n rightarrow infty$, what is the maximum value of
q_{A} = Pr( | pi cap A| geq r)

asymptotically in $n$ ?

It seems reasonable that $q_{A}$ should be maximized when $A = { (1,1), (2,2), dots, (a,a) }$, since this maximizes the expected value of $binom{ |pi cap A|}{ r }$. (It is important here that $alpha leq 1$.) In this case, $pi cap A$ roughly has a Poisson distribution with rate $lambda = alpha$ (bearing in mind that $alpha$ and $r$ are constant), and so we would expect
q_{A} leq (1+o(1)) sum_{j geq r} e^{-alpha} alpha^j / j!

Is this intuition correct? Is it true that $q_{A}$ satisfies such bound for any fixed $r$ and $alpha$ ?

co.combinatorics – Optimal Testing Strategy

In order to speed up Covid testing, some centers are testing multiple people at once. This means that they are combining their biological material and testing for the presence of Covid in the resulting mixture (so far as I understand it). This proposes the following puzzle:

Let us assume that we have a single Covid detection machine. Given a biological sample, it takes the machine one unit of time to test for the presence of Covid. Assume further that the machine gives no false positives or negatives, and that we can collect as much biological material as we want from each person. Lastly, let us assume that the probability that one of our $N$ citizens has Covid is a fixed value $p$, independent of any information about their peers.

The challenge is: what is an optimal testing strategy, as a function of $p$, when we are allowed to test multiple people at once? By “optimal” I mean a strategy that, on average, conclusively determines everyone’s Covid status in the fewest units of time.

One simple strategy is to group people into pairs, first testing both at once, and then testing each individually if the first test comes up positive. Provided that $p< 1 – sqrt{frac{1}{2}}$, the probability that a given person doesn’t have Covid is more than $sqrt{frac{1}{2}}$, so the probability that a given pair doesn’t have Covid is more than $1/2$. Then, the expected units of time needed to determine the pair’s Covid status is strictly less than $(1)(1/2) + (3)(1/2) = 2$, which beats out the strategy of testing them individually. When $p$ gets lower, one can group people into triples or more, and this becomes more and more efficient. However, this is a super naive analysis, and one can likely cook up all manner of more sophisticated procedures.

So: Is there a better way to analyze this problem? Is it equivalent/similar to well-studied problems in probability/combinatorics? What happens when the possibility of false positives or negatives emerges, and we want to establish everyone’s Covid status with high probability?

co.combinatorics – Is being simply connected very rare?

Essentially, my question is how strong a restriction it is to be simply connected.

Here is a way of making this precise: Let’s say we want to count simplicial complexes (of dimension 2, though that does not matter much, any fixed dimension is fine) on N simplices that are subject to the following restrictions:

A: every vertex is contained only in a bounded number of simplices (say, 10000).

B: the complex is simply connected.

So properly: How many distinct complexes like this are there? In fact, I only want a rough answer: is it exponential in N, or is it superexponential. Note that if I remove either restriction, the answer is superexponential.

co.combinatorics – Is there general theory of this type of problem?

Suppose we have a function $f(x_1 ,x_2 ,x_3 ,x_4).$ We know that we can factor it int two ways as $f(x_1 ,x_2 ,x_3 ,x_4)=phi_1 (x_1 ,x_2 )phi_2(x_3 ,x_4 )=psi_1 (x_1,x_3)psi_2(x_2,x_4)$

Show that we can completely factor the function as: $f(x_1 ,x_2 ,x_3 ,x_4)=varphi_1(x_1)varphi_2(x_2)varphi_3(x_3)varphi_4(x_4).$

I stumbled a little bit on this elementary problem as the proof is not as immediate as I think. But eventually I can prove this.

Here the overlap of partition {{1,2} {3,4}} and {{1,3},{2,4}} is {{1},{2},{3},{4}} and indeed satisfying the first two partition implies that we can factor by the overlap of both partitions.

I wonder if there is a general statement/theory of this.

co.combinatorics – Is matroid realizability computable?

Contra my suspicions, the Internet is telling me that Vámos proved in “A necessary and sufficient condition for a matroid to be linear” (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of Solving Rota’s Conjecture which says “The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos (28).”

Vamos, P., A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). ZBL0374.05017.

co.combinatorics – Is there a short (conceptual) way to prove that this combinatorial map is invariant by cyclic permutation?

Consider a positive integer $n$ and integers $c_i$, $i=1,2,3,4$, such that $1 le c_i le n$. For all $c_4$, consider the map:

$$m_{c_4}: (c_1,c_2,c_3) mapsto delta_{c_1,c_2}delta_{c_3,c_4} – # { |2n+1-2|x||, x in {c_1+c_2, c_3+c_4, c_1-c_2, c_3-c_4} },$$

where the notation $#$ means cardinal. The problem is to show that this map is invariant by cyclic permutation, i.e.
$$ m_{c_4}(c_1,c_2,c_3) = m_{c_4}(c_2,c_3,c_1). $$

I see a straightforward way to prove that by cases, but it should be quite long.

Question: Is there a short (conceptual) way to prove that?

Context: this problem poped up to prove that some rings (parametrized by $q$) are associative.

Just for the conveniance of the reader, here is the checking for $n<20$:

sage: def map(c1,c2,c3,c4,n):
....:     return kronecker_delta(c1,c2)*kronecker_delta(c3,c4)-len(set((abs(2*n+1-2*abs(x)) for x in (c1+c2,c3+c4,c1-c2,c3-c4))))
sage: for n in range(1,20):
....:     for c1 in range(1,n+1):
....:         for c2 in range(1,n+1):
....:             for c3 in range(1,n+1):
....:                 for c4 in range(1,n+1):
....:                     if map(c1,c2,c3,c4,n)!=map(c2,c3,c1,c4,n):
....:                         print((c1,c2,c3,c4,n))