Pith. sign in

REVIEW 3 major objections 5 minor 27 references

The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the scaled Hall condition known as the normalized matching property turns on sharply at p = (log n)/k in random bipartite graphs, and that pseudorandom graphs gain it after deleting a negligible fraction of vertices.

desk verdict Genuinely new results and a mostly sound random-graph argument, but the proof of the sharp threshold has a load-bearing sign error in Case Y that as printed invalidates the bounded n/k regime. read the letter →

arxiv 1908.02628 v3 pith:7K5UM62G submitted 2019-08-07 math.CO cs.DMmath.PR

Niranjan Balachandran , Deepanshu Kush This is my paper · ORCID
classification math.COcs.DMmath.PR MSC 05C8005C70
keywords normalizedmatchingpropertysharpthresholdrandombipartitegraphspseudorandomexpander-mixinglemmaEuclideantreeHall'sconditionvertexdecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a sharp density threshold for the normalized matching property (NMP) in random bipartite graphs, and shows that pseudorandom bipartite graphs almost have the property. For $G(k,n,p)$ with $k\le n\le \exp(o(k))$, the critical probability is $p=(\log n)/k$: above it every subset of the $k$-side has proportionally enough neighbors with probability arbitrarily close to 1, and below it an isolated vertex on the $n$-side destroys the property. For pseudorandom graphs with $p\gg 1/k$, the paper proves that deleting a negligible fraction of vertices leaves a subgraph with NMP, and the proof does this by decomposing almost all vertices into disjoint copies of a Euclidean tree built from the Euclidean algorithm. These results matter because they turn the motivating balance problems—equal row and column sums in star-arrays and equal-frequency labelling in finite fields—into quantitative density statements.

What carries the argument

The load-bearing object is the Euclidean $(\ell,L)$-tree $T_{\ell,L}$, a left-right tree with $\ell$ left and $L$ right vertices defined recursively: subtract the smaller count from the larger, add a matching of size $\min(\ell,L)$ between the two sides, and repeat until only a star remains. These trees have NMP, and so do vertex-disjoint unions of copies of one Euclidean tree. Lemma 4.1 is the engine that produces them in pseudorandom graphs: using the expander-mixing estimate it shows that any large enough equal-ratio pair of vertex sets can be spanned by a $q$-thrill—a vertex-disjoint union of $q$-fans, each a star with one center and $q$ leaves—up to $O(\varepsilon n)$ leftover vertices. Running this extraction at each step of the Euclidean algorithm gives an almost-factorization of the pseudorandom graph into Euclidean trees, and the leftover vertices are exactly the deleted sets $\mathrm{Del}_X$ and $\mathrm{Del}_Y$.

What would settle it

A counterexample to that transfer would settle the question: build any bipartite graph with $|X|=k$, $|Y|=n\gg k$ where each $x$ has degree at least $pn$ and each pair of $X$-vertices has at most $(1+\varepsilon)p^2n$ common neighbors, but some $A\subseteq X$ of size about $1/p$ and $B\subseteq Y$ violate $|e(A,B)-p|A||B||\le \sqrt{pn|A||B|(1+\varepsilon p|A|)}$. If such a graph exists, the bound on leftover vertices in the $q$-thrill lemma fails and the deletion-size conclusion of the pseudorandom theorem does not follow.

Watch

Extended reading notes

Core claim

The central claim is that the normalized matching property has a sharp threshold in random bipartite graphs: for $G(k,n,p)$ with $k\le n\le \exp(o(k))$, the critical probability is $p=(\log n)/k$. Above $(1+\varepsilon)$ times this value the graph has NMP with probability at least $1-\delta$; below $(1-\varepsilon)$ times it, NMP fails with probability at most $\delta$, the failure witnessed by an isolated vertex in $Y$. For pseudorandom graphs, the central claim is that if every $x\in X$ has degree at least $pn$ and every pair of vertices in $X$ has at most $(1+\varepsilon)p^2n$ common neighbors, and $p\gg 1/k$, then there are tiny sets $\mathrm{Del}_X$ and $\mathrm{Del}_Y$ whose removal leaves a subgraph with NMP; the deletion bounds are $O(\varepsilon)$ from $X$ and $O(\sqrt{\varepsilon})$ from $Y$ when $n\gg k$, and $O(\varepsilon^{1/4}\log(1/\varepsilon))$ from each side in general. The pseudorandom proof is constructive: it partitions almost all vertices into Euclidean trees, small left-right trees defined recursively by the Euclidean algorithm, and Euclidean trees have NMP by construction.

Load-bearing premise

The pseudorandom result rests on assuming that the edge-counting estimate at its core remains valid when the two sides of the bipartite graph have different sizes and only one side's pair overlaps are controlled; the paper says the original proof carries over but does not show it.

Editorial extensions

If this is right

  • For any $k\le n\le \exp(o(k))$, the random bipartite graph $G(k,n,p)$ has NMP with probability at least $1-\delta$ when $p\ge (1+\varepsilon)\log n/k$, and fails NMP with probability at most $\delta$ when $p\le (1-\varepsilon)\log n/k$.
  • Below the threshold the obstruction is concrete: some vertex of $Y$ is isolated, so the normalized Hall condition cannot hold.
  • Every sufficiently large pseudorandom bipartite graph satisfying the paper's degree and codegree bounds, with $p\gg 1/k$, is NMP-approximable: deleting $O(\varepsilon)|X|$ and $O(\sqrt{\varepsilon})|Y|$ vertices when $n\gg k$, or $O(\varepsilon^{1/4}\log(1/\varepsilon))$ from each side in general, leaves a subgraph with NMP.
  • The surviving subgraph comes with an explicit decomposition into vertex-disjoint Euclidean trees, each of which has NMP, so the decomposition certifies the property.
  • Approximate versions of the motivating problems—filling a star-array with equal row and column sums, and labelling most elements of a finite field so that labelled pairs land in a prescribed multiplicative subgroup—have affirmative answers for random-like or pseudorandom inputs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the threshold proof indicates that above $(1+\varepsilon)\log n/k$ the only possible NMP violations come from tiny subsets of $X$ or isolated vertices of $Y$, while medium-sized violations are exponentially rare; this suggests a simpler certificate for NMP in dense-enough random graphs than checking all subsets.
  • Editorial extension: because Lemma 4.1 is used as a black box, any pseudorandomness notion that supplies a similar discrepancy bound should yield an analogous NMP-approximability theorem; one test is to run the Euclidean-tree process on eigenvalue-based pseudorandom bipartite graphs and compare the required deletion fraction with the paper's bounds.
  • Editorial question: the asymmetric deletion rates in the $n\gg k$ case—$O(\varepsilon)$ from $X$ but $O(\sqrt{\varepsilon})$ from $Y$—raise the question of whether that asymmetry is forced; a construction built from isolated vertices shows some asymmetry is natural, but the exact tradeoff is not settled by the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the Normalized Matching Property (NMP) in bipartite graphs, where a graph G(X,Y) satisfies NMP if every S⊆X has |N(S)|/|Y| ≥ |S|/|X|. The first main result, Theorem 1.2, establishes that p = log(n)/k is a sharp threshold for NMP in the unbalanced random bipartite graph G(k,n,p) under the assumption k ≤ n ≤ exp(o(k)). The second main result, Theorem 1.4, shows that any sufficiently dense Thomason-pseudorandom bipartite graph is NMP-approximable: after deleting a vanishingly small fraction of vertices, the remaining graph has NMP. The proof of Theorem 1.4 is built around a decomposition of the graph into Euclidean trees, which are recursively defined trees that individually have NMP. The paper also includes an appendix proving robustness of the Thomason pseudorandomness condition under deletion of vertices.

Significance. If the results hold, the paper gives a natural generalization of the Erdős–Rényi perfect-matching threshold to the unbalanced setting, and it provides a new sufficient condition for approximate NMP under a weak, easily checkable pseudorandomness assumption. The Euclidean-tree decomposition is an attractive and apparently new structural tool, and the proof strategy of Theorem 1.4 is modular, with Lemma 4.1 as a black-box that could be adapted to other pseudorandomness notions. The paper does not rely on fitted parameters or circular reasoning; the main arguments use standard external ingredients such as Kleitman's equivalence, Chernoff bounds, and the expander-mixing principle. The central claims are significant, but the written proof of Theorem 1.2 contains a concrete algebraic error, and a key pseudorandomness estimate is asserted without proof; these issues need to be fixed before the results can be considered established.

major comments (3)
  1. [Section 3, Case Y, Eqs. (9)-(14)] The displayed estimate of M1 is not valid as written because of a sign error. From (1-p)^{s k(1-s/n)} ≤ exp(-p s k(1-s/n)), the factor entering the bracket in (10) must be exp(-p k(1-s/n)), with a negative sign, not exp(p k(1-s/n)). The subsequent inequalities (11)-(13) use the positive exponent, so the claimed bound M1 = o(1) does not follow from the displayed chain. This is load-bearing because Case Y is one of the two cases needed for the sharp threshold in Theorem 1.2. The error appears repairable: with the corrected negative exponent one obtains exp(-(1+ε) log n + (1+ε)k/(2n)) in the bounded n/k regime, and the factor exp((1+ε)k/(2n)) is O(1) when k = O(n), so the sum over s ≥ s_min can still be made o(1) with a sufficient polynomial decay in n. The authors should rewrite this chain carefully and state explicitly how the bounded n/k regime is handled.
  2. [Section 4, after Theorem 1.3] Theorem 1.3 states an asymmetric version of Thomason's expander-mixing lemma for |X|=k ≤ n=|Y| with the error term sqrt(p n a b (1+ε p a)), but the proof is not given and no precise reference for this exact asymmetric statement is supplied. The sentence 'a glance at the proof there immediately tells us that the same proof works in our general setup' is not sufficient, because Lemma 4.1 and hence Theorem 1.4 depend on this estimate in an essential way. The authors should either include a full proof of the asymmetric expander-mixing inequality under the stated codegree hypothesis, or provide a reference that proves exactly this statement with the same hypotheses and error term.
  3. [Section 3, Case X, minimal-witness argument] In the paragraph bounding the probability of a small minimal witness S⊆X, the claim that every U⊆N(S) of size ceil(n/k) has at least two neighbors in S is supported by the displayed inequality 'n/k |S| - ceil(n/k) > |N(S')|'. This inequality has the wrong direction. From |N(S)| < n|S|/k and U⊆N(S) with |U|=ceil(n/k), one gets |N(S')| ≤ |N(S)| - |U| < n|S|/k - ceil(n/k) ≤ n/k (|S|-1), which is the needed contradiction with minimality. The displayed inequality should be corrected, and the argument phrased as a strict inequality in the last step. This is a local but necessary fix in the proof of the main random-graph theorem.
minor comments (5)
  1. [Section 2, Lemma 2.1] The proof of Lemma 2.1 is correct but terse; it would help to explicitly state that the second characterization in Theorem 1.1 is symmetric in X and Y when passing to witnesses in G(Y,X).
  2. [Section 2, Euclidean tree process] The definitions of 'spanned by an X q-thrill' and 'admits a T_{l,L}-factor' are used before being formally defined; a sentence clarifying that these mean a spanning subgraph consisting of vertex-disjoint copies would improve readability.
  3. [Section 3, Lemma 3.2] In the small and large cases of Lemma 3.2, the bounds involving binomial coefficients are stated with the convention (N,K) ≤ (eN/K)^K, but the intermediate case uses a different bound; a uniform notational remark would help the reader follow the estimates.
  4. [Section 4, Proof of Theorem 1.4 part (b)] When choosing K and N as multiples of floor(α n), the argument should explicitly note that all inequalities are asymptotic and require k large enough relative to ε; as written, the interval endpoints depend on quantities that may not be integers.
  5. [Appendix] The appendix proves robustness of Thomason pseudorandomness under vertex deletion, but it does not address the asymmetric expander-mixing estimate. Adding a cross-reference to the missing proof of Theorem 1.3 would clarify the logical dependencies.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proofs are grounded in external theorems and direct probabilistic estimates, with no self-citation loops or fitted-parameter predictions.

full rationale

The paper's derivation chain is self-contained with respect to its stated external inputs. Theorem 1.2 is proved by a union bound over independent-set witnesses using Kleitman's equivalence (Theorem 1.1) and Chernoff-type estimates; the lower-threshold direction uses isolated vertices in Y. No parameter is fitted to the target conclusion: the claimed threshold log n/k appears in the hypotheses, and the proof bounds probabilities as functions of it rather than using the NMP event to define the threshold. Theorem 1.4 is built from Thomason's expander-mixing estimate (Theorem 1.3, external to this paper), the Euclidean-tree construction whose NMP property is proved directly in Lemma 2.2, and the deletion bounds from Lemma 4.1. The Euclidean trees are not renamed known NMP objects; the paper explicitly notes a prior definition in a graphic-matroid context and proves the NMP property here. The only notable rigor issue — the asymmetric k ≤ n extension of Thomason's theorem is asserted by 'a glance at the proof there' rather than reproduced — is an unproved importation of an external result and therefore a correctness/verification concern, not a circularity; likewise, the algebraic gap in Case Y of Theorem 1.2's proof, if real, would invalidate that proof but would not make the claim reduce to its own inputs. There are no self-citation loops and no fitted-input-called-prediction steps.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard probabilistic and combinatorial tools plus the stated model assumptions. No free parameters are fitted to data; the constants ε, δ, ω(k) are arbitrary accuracy parameters. The only non-standard step is the asserted generalization of Thomason's expander-mixing lemma, which should be checked.

assumptions (6)
  • standard math Chernoff bounds for binomial and hypergeometric tails
    Invoked in Theorem 2.1 and in the Appendix to control degree and codegree deviations.
  • standard math Kleitman's equivalence of NMP with the independent set condition and with a multiplicity function
    Theorem 1.1 is the starting point for the random threshold proof and for showing Euclidean trees have NMP.
  • domain assumption Thomason's expander-mixing lemma for pseudorandom bipartite graphs extends to asymmetric parts with k≤n and relaxed parameters
    Section 2 relies on Theorem 1.3 for all subsets A,B; the paper asserts the known equal-size proof carries over but does not supply it.
  • standard math Degree and minimum-degree facts for G(k,n,p) derived from known random graph results
    Facts 2.2 and 2.3 are quoted from standard references and Chernoff estimates.
  • standard math The Euclidean algorithm complexity bound m ≤ 2.078 log L + 0.6723
    Fact 2.4, taken from Knuth, controls deletion sizes in Lemma 4.2 and Theorem 1.4(b).
  • domain assumption The parameter range k ≤ n ≤ exp(o(k)) in Theorem 1.2
    The threshold statement is proved only in this range, and the authors argue it is essentially the widest possible for a sharp threshold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs." pith.science (2026). https://pith.science/paper/7K5UM62G

@misc{pith2026190802628,
  author       = {Pith},
  title        = {Pith review of: The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7K5UM62G}},
  note         = {Machine review of arXiv:1908.02628}
}
abstract

A simple generalization of the Hall's condition in bipartite graphs, the Normalized Matching Property (NMP) in a graph $G(X,Y,E)$ with vertex partition $(X,Y)$ states that for any subset $S\subseteq X$, we have $\frac{|N(S)|}{|Y|}\ge\frac{|S|}{|X|}$. In this paper, we show the following results about having the Normalized Matching Property in random and pseudorandom graphs. 1. We establish $p=\frac{\log n}{k}$ as a sharp threshold for having NMP in $\mathbb{G}(k,n,p)$, which is the graph with $|X|=k,|Y|=n$ (assuming $k\le n\leq \exp(o(k))$), and in which each pair $(x,y)\in X\times Y$ is an edge independently with probability $p$. This generalizes a classic result of Erd\H{o}s-R\'enyi on the $\frac{\log n}{n}$ threshold for having a perfect matching in $\mathbb{G}(n,n,p)$. 2. We also show that a pseudorandom bipartite graph - upon deletion of a vanishingly small fraction of vertices - admits NMP, provided it is not too sparse. More precisely, a bipartite graph $G(X,Y)$, with $k=|X|\le |Y|=n$, is said to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989)) with parameters $(p,\varepsilon)$ if each $x\in X$ has degree at least $pn$ and each pair of distinct $x, x'\in X$ has at most $(1+\varepsilon)p^2n$ common neighbors. We show that for any large enough $(p,\varepsilon)$-Thomason pseudorandom graph $G(X,Y)$, there are "tiny" subsets $\mathrm{Del}_X\subset X, \ \mathrm{Del}_Y\subset Y$ such that the subgraph $G(X\setminus \mathrm{Del}_X,Y\setminus \mathrm{Del}_Y)$ has NMP, provided $p \gg\tfrac{1}{k}$. En route, we prove an "almost" vertex decomposition theorem: Every such Thomason pseudorandom graph admits - excluding a negligible portion of its vertex set - a partition of its vertex set into graphs that we call Euclidean trees. These are trees that have NMP, and which arise organically through the Euclidean GCD algorithm.

Figures

Figures reproduced from arXiv: 1908.02628 by the authors.

Figure 1
Figure 1. Construction of the Euclidean (3, 7)-tree. Each successive matching is shown in a different color. build here will be relevant in Section 4 in the proof of Theorem 1.4. This description also justifies why we call them Euclidean trees. Suppose ` < L. Consider the Euclidean algorithm on the pair (`, L) as follows. L = qm` + rm−1, 0 < rm−1 < rm = `, ` = qm−1rm−1 + rm−2, 0 < rm−2 < rm−1, · · · = · · · r3 = q2r2 + r1, 0 … view at source ↗
Figure 2
Figure 2. The Euclidean (5, 8)-tree process. In this case m = 4, (r2, r3, r4, r5) = (2, 3, 5, 8), (q1, q2, q3, q4) = (2, 1, 1, 1). T5,8 evolves as T2,1 ⇒ T2,3 ⇒ T5,3 ⇒ T5,8 in the process. 3 Threshold for NMP for G(k, n, p) In this section we prove Theorem 1.2, restated below for convenience. Throughout this section, we shall write G to denote G(k, n, p). Unless stated otherwise, we shall assume k ≤ n ≤ exp(o(k)). Theorem 1.2… view at source ↗
Figure 3
Figure 3. An illustration of the induction step in the proof of Theorem 1.4. The picture on the left depicts the copies of Ti−1 that span Gi−1 and are colored blue. The picture on the right depicts what happens to each of these copies in the induction step: those which have a vertex in Ai (the topmost box in X (i) ) “corrupt” all the vertices that they contain (colored pink) and those which do not have a vertex in Ai “evolve”… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

  1. [1]

    Bourgain, Additive Patterns in Multiplicative Subgroups, Geom

    N Alon, J. Bourgain, Additive Patterns in Multiplicative Subgroups, Geom. Funct. Anal., 24 (2014), No. 3, 721-739

    work page 2014

  2. [2]

    N. Alon, J. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016

    work page 2016

  3. [3]

    Anderson, Some problems in combinatorial number theory, PhD thesis, University of Not- tingham, United Kingdom, (1967)

    I. Anderson, Some problems in combinatorial number theory, PhD thesis, University of Not- tingham, United Kingdom, (1967)

    work page 1967

  4. [4]

    Anderson, Combinatorics of Finite Sets , Dover Publications, Mineola, NY (2002)

    I. Anderson, Combinatorics of Finite Sets , Dover Publications, Mineola, NY (2002)

    work page 2002

  5. [5]

    Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press (2001)

    B. Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press (2001)

    work page 2001

  6. [6]

    Bollob´ as, A

    B. Bollob´ as, A. Thomason, Threshold functions,Combinatorica, 7 (1986), 35-38. 25

    work page 1986

  7. [7]

    Engel, Sperner theory in Encyclopedia of Mathematics, Cambridge University Press (1997)

    K. Engel, Sperner theory in Encyclopedia of Mathematics, Cambridge University Press (1997)

    work page 1997

  8. [8]

    A. Eden, U. Feige, M. Feldman, Max-min greedy matching, NetEcon’ 19, Proc. 14th Workshop on the Economics of Networks, Systems and Computation, Article 10, (2019)

    work page 2019

Show all 27 references
  1. [9]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi, On the evolution of random graphs,Publ. Math. Inst. Hungar. Acad. Sci. , 5 (1960), 17-61

    1960

  2. [10]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi, On random matrices,Publ. Math. Inst. Hungar. Acad. Sci. , 8 (1964), 455-461

    1964

  3. [11]

    R. L. Graham, L. H. Harper, Some results on matchings in bipartite graphs, SIAM J. Appl. math., 17 (1969), 1017-1022

    1969

  4. [12]

    J. R. Griggs, Sufficient conditions for a symmetric chain order, SIAM J. Appl. Math. , 32 (1977), 807-809

    1977

  5. [13]

    J. Guo, K. Wang, F. Li, Normalized matching property of subspace posets in finite classical polar spaces, Finite Fields Appl. , 19 (2013), 67-72

    2013

  6. [14]

    T. Hsu, M. Logan, S. Shahriari, Methods for nesting rank 3 normalized matching rank- unimodal posets. Discrete Math. 309(3), 521-531 (2009)

    2009

  7. [15]

    Janson, T

    S. Janson, T. Luczak, A. Rucinski. Random Graphs, Wiley (2000)

    2000

  8. [16]

    Kleitman, On an extremal property of antichains in partial orders, Combinatorics (eds

    D. Kleitman, On an extremal property of antichains in partial orders, Combinatorics (eds. M. Hall & J. H. van Lint), Math. Centre Tracts 55 (1974), 77-90

    1974

  9. [17]

    Knuth, The Art of Computer Programming, Vol II: Seminumerical Algorithms , 3rd ed., Addison-Wesley (1998)

    D. Knuth, The Art of Computer Programming, Vol II: Seminumerical Algorithms , 3rd ed., Addison-Wesley (1998)

    1998

  10. [18]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, Pseudo-random graphs, More Sets, Graphs and Numbers , Bolyai Soc. Math. Studies 15, Springer, (2006), 199-262

    2006

  11. [19]

    Skala, Hypergeometric tail inequalities: ending the insanity, arXiv:1311.5939, 2013

    M. Skala, Hypergeometric tail inequalities: ending the insanity, arXiv:1311.5939, 2013

    2013 arXiv

  12. [20]

    Thomason, Pseudo-random graphs, Annals of Discrete Math

    A. Thomason, Pseudo-random graphs, Annals of Discrete Math. , 33 (1985), 307-331

    1985

  13. [21]

    Thomason, Dense Expanders and Pseudo-Random Bipartite graphs, Discrete Math

    A. Thomason, Dense Expanders and Pseudo-Random Bipartite graphs, Discrete Math. 75 (1989), 381-386

    1989

  14. [22]

    Wang, Normalized matching property of the subgroup lattice of an abelianp-group, Discrete Math., 257 (2002), 559-574

    J. Wang, Normalized matching property of the subgroup lattice of an abelianp-group, Discrete Math., 257 (2002), 559-574

    2002

  15. [23]

    J. Wang, H. Zhang, Normalized Matching property of a class of subspace lattices, Taiwanese J. Math., 11 (2007), No. 1, 43-50

    2007

  16. [24]

    D. B. West, L. H. Harper, D. E. Daykin, Some remarks on Normalized Matching, J. Combin. Theory Ser. A 35 (1983), 301-308

    1983

  17. [25]

    Chang, W

    Y. Chang, W. Li, Some Remarks on Nestings in the Normalized Matching Posets of Rank 3. Order 36 (2019), 501–505

    2019

  18. [26]

    A. Sali, G. Simonyi, Intersecting set systems and graphic matroids, Discrete Math. 185 (1998), 279-285. 26 Appendix: Robustness of Thomason pseudorandomness Lemma. Let 0 < ε < 1 2, and k ≤ n be positive integers. Suppose G(X,Y ) is a Thomason pseudorandom bipartite graph with ...

    1998

  19. [27]

    Thus, 2t2D≥ 2ε2p2 0 ( 1 α− 1 )2(αn 2 ) ≥ (ε2 α ) (1−α)2(p2 0k)≥ 49 64ε = log (1 η ) where we may take the constant C = 49 64 = 0.765625 in the definition of η. 27 One interesting consequence of the proof of the lemma is that if we seek η = poly(ε) then one has a randomized algo...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.