I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...

I’m working on the planted perfect matching problem in random $k$-uniform hypergraphs $k \ge 3$, and I’m stuck on rigorizing the impossibility (lower bound) side of what looks like the information-...

Consider the following streaming algorithm for maximum matching in a weighted graph....

Let $G$ be a graph with no isolated vertices.A set of vertices in $G$ is calledindependent if no two vertices in the set are incident on the same edge;vertex cover if every edge is incident to ...

The following is a collection of combinatorics theorems commonly refereed as "equivalent" due to one being easily derived from another.Theorem (Hall).A finite bipartite graph $G = (A\...

Is it true that a graph has a fractional perfect matching if and only if $i(G\setminus S)\leq |S| $ for all $S\subset V(G)$? And why?Here $i(G\setminus S)$ denotes the number of isolated vertices of ...

I’m studying properties of adjacency matrices of graphs.Suppose $G$ is a simple undirected graph with adjacency matrix $A$. If we have$$A^2 = I,$$where $I$ is the identity matrix, then it seems ...

Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithmhas $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−1}$. We ...

I’m trying to prove the following statement:Let $G$ be a countably infinite, $d$‑regular, connected, vertex‑transitive bipartite graph. Show that $G$ admits a perfect matching.Problem$G$ is a ...

Definition. Let $I$ be a squarefree monomial ideal (that is, an ideal in $K[x_1,\dots,x_n]$ generated by squarefree monomials). The $k$-th squarefree power $I^{[k]}$ of $I$ is the ideal generated by ...

Let $G$ be a connected 3-regular (cubic) graph on $n$ vertices. A balloon in $G$ is defined as a maximal subgraph of $G$ that has no cut-edges (i.e., is 2-edge-connected) and is connected to the rest ...

I've recently been reading Paul Zeitz's "The Art and Craft of Problem Solving" Third Edition, and I've come across a problem whos solution I was confused on. The problem reads,"In a ...

The following is taken from Design of Approximation Algorithms by Williamson and Shmoys available at https://www.designofapproxalgs.com/book.pdfExercise 4.6 Let $G = (A, B, E)$ be a bipartite graph; ...

Suppose, my input is a graph $G$, and $k$ sets $A_1, A_2,\ldots, A_k\subseteq E(G)$. I wish to find a perfect matching $M$ such that $M\cap A_i\neq \emptyset$, for all $i \in 1,2,\ldots, k$. Can such ...

[Crossposted from mathoverflow]Let $\mathcal F$ be a family of subsets of $[n]=\{1,2,\dots,n\}$. For $k \in [n]$ let $\mathcal F_k = \{A \in \mathcal F : k \in A \}$ and $\mathcal F_{\overline{k}} = \...