Pith. sign in

REVIEW 2 major objections 8 minor 2 cited by

Restricted subgraphs of edge-colored graphs and applications

T0 review · 2 major / 8 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read This survey argues that rainbow subgraphs in edge-colored graphs are a powerful transferable tool, and demonstrates it with a counting lemma that yields applications to coding theory, additive combinatorics, graph decomposition, and Latin…

desk verdict A solid, clearly labeled survey that delivers a usable map of rainbow subgraph methods and their applications; the gaps are minor and fixable, and it deserves a serious referee. read the letter →

arxiv 2412.13945 v1 pith:3ISH6BL4 submitted 2024-12-18 math.CO cs.DM

Benny Sudakov This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C3805C7005B1594B65
keywords rainbowsubgraphsedge-coloredgraphsproperlycyclesmatchingsLatinsquaretransversalsgraphdecompositionslocallydecodablecodes
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 survey argues that looking for rainbow subgraphs and related restricted structures in edge-colored graphs is a powerful method for attacking problems elsewhere in mathematics and computer science. It demonstrates this with a small, partly self-contained toolkit: a simple counting lemma about rainbow paths, a reduction from hypergraph even covers to cycles in edge-colored Kikuchi graphs, and recent theorems about rainbow cycles, rainbow matchings, and rainbow trees. The payoff is that several well-known conjectures, about hypergraph refutation witnesses, 3-query locally decodable codes, transversals in Latin squares, tree decompositions of complete graphs, and harmonious labelings, are either proved asymptotically or reduced to cleaner combinatorial arguments. A sympathetic reader should come away believing that the restricted-subgraph viewpoint is a dependable source of proofs, not merely a collection of isolated results.

What carries the argument

The load-bearing object is Lemma 2.2, a counting lemma for rainbow paths in properly edge-colored graphs. The argument counts rainbow paths of length $\ell = \log_2 n$: by the minimum-degree assumption $r = 2\log_2 n$, the number of rainbow paths starting from a fixed vertex is at least $n\prod_{j=0}^{\ell-1}(r-j) \ge n\ell^{\ell}$, while the assumption that no short unique-color cycle exists is used to cap the number of rainbow paths between any fixed pair of vertices at $\ell!$; the contradiction $n^2\ell! < n\ell^{\ell}$ forces the desired short cycle. The same lemma is applied through the Kikuchi graph, an auxiliary graph whose vertices are $\ell$-subsets of a hypergraph's vertex set and whose edges are colored by hyperedges, so that a unique-color cycle in the Kikuchi graph becomes an even cover in the original hypergraph. Later sections rely on more recent machinery, including an essentially tight rainbow-cycle theorem and a rainbow tree embedding theorem for locally $k$-bounded colorings, each of which carries a different family of applications.

What would settle it

Run an exhaustive search for the smallest $n$ where a properly edge-colored graph with at least $2n\log_2 n$ edges has no cycle of length at most $2\log_2 n$ with an edge of unique color; the Cayley sum graph on $\mathbb{F}_2^k$ with the standard basis shows the density threshold cannot be below $\frac12 n\log_2 n$, so the constant $2$ is exactly what must break. Alternatively, in any graph satisfying the lemma's hypotheses, exhibit two rainbow paths of length $\ell$ with the same endpoints but different color sets, since the lemma's upper bound of $\ell!$ rainbow paths per pair falls with that example.

Watch

Extended reading notes

Core claim

The paper's central claim is that the question "which rainbow or edge-constrained subgraphs must every properly edge-colored graph contain?" is not an isolated corner of graph theory but a transferable tool. It demonstrates the claim by presenting Lemma 2.2, which states that every properly edge-colored $n$-vertex graph with at least $2n\log_2 n$ edges contains a cycle of length at most $2\log_2 n$ with an edge whose color appears once on the cycle, and then using that lemma, together with more recent rainbow-cycle and rainbow-tree theorems, to recover or improve results about even covers in hypergraphs, 3-query locally decodable codes, the additive dimension of small-doubling sets, transversals in Latin squares, and decompositions of complete graphs into trees. The survey also reports several headline external results, including the confirmation of the Ryser-Brualdi-Stein conjecture for large even $n$ and a full proof of Ringel's conjecture for large $n$, as further evidence of the same thesis.

Load-bearing premise

The load-bearing premise is an unproved observation inside the proof of Lemma 2.2: two rainbow paths of length $\ell$ with the same endpoints must have the same set of colors, because otherwise their symmetric difference would be a short rainbow cycle. If that observation fails, the bound of at most $\ell!$ rainbow paths per vertex pair collapses, and with it the lemma and its applications to even covers and locally decodable codes.

Editorial extensions

If this is right

  • Lemma 2.2 turns the hypergraph even-cover problem for even uniformity into a short argument: a $k$-uniform hypergraph with at least $Cn(n/\ell)^{k/2-1}\log n$ hyperedges has an even cover of size $O(\ell\log n)$, recovering and slightly improving spectral proofs.
  • The same lemma gives a purely combinatorial proof of a cubic lower bound for 3-query binary locally decodable codes, with a slightly better logarithmic factor than the previous spectral argument.
  • The essentially tight rainbow-cycle theorem, stating that average degree $C\log n\log\log n$ forces a rainbow cycle, implies that a subset of any group with $|A\cdot A| \le K|A|$ has additive dimension at most $O_K(\log^{1+o(1)}|A|)$.
  • The rainbow tree embedding theorem yields asymptotic solutions to Ringel's conjecture, the harmonious-labeling conjecture, and the orthogonal-double-cover conjecture for trees; its refinements give a full proof of Ringel's conjecture for large $n$.
  • In Latin squares, rainbow matchings in properly edge-colored $K_{n,n}$ correspond to transversals, and the survey reports that every such coloring has a rainbow matching of size $n-1$ for large even $n$, confirming the Ryser-Brualdi-Stein conjecture in that range.

Reading between the lines

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

  • If the restricted-subgraph viewpoint is as productive as the survey argues, the same style of question, applied to rainbow subdivisions, rainbow embeddings with prescribed color sets, or matroid analogues where "proper" means independent, could be turned on open problems in incidence geometry and approximate groups.
  • The unproved observation inside Lemma 2.2, that same-endpoint rainbow paths of equal length must share their color set, is stated without proof; a reader who wants the survey's simplest applications on a firm footing would first supply a full proof of that observation.
  • The Kikuchi-graph reduction suggests a testable extension: hypergraphs of odd uniformity might be handled by the same lemma after a parity-twisting construction, and the survey's even-$k$ theorem is evidence that the constant $C$ can be made explicit and small.
  • The contrast between the simple Lemma 2.2 proof and the spectral proofs it replaces suggests that other Kikuchi-graph arguments in coding theory could be re-derived combinatorially, potentially improving hidden constants such as the $10^7/\delta^2$ in the locally decodable code bound.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 8 minor

Summary. This survey argues that rainbow and other edge-constrained subgraphs of properly edge-colored graphs constitute a powerful method for attacking problems in graph decomposition, additive combinatorics, theoretical computer science, and coding theory. After introducing proper edge colorings and the rainbow-subgraph formalism, the paper presents Lemma 2.2 (2n log n edges force a short cycle with a unique color), uses it to derive even-cover bounds and a cubic lower bound for 3-query locally decodable codes via Kikuchi graphs, discusses the rainbow cycle problem and its application to dissociated subsets, surveys Latin-square transversals from Euler through Montgomery's recent Ryser-Brualdi-Stein breakthrough, and treats rainbow tree embeddings with applications to asymptotic Ringel decompositions, harmonious labelings, and orthogonal double covers. The paper is explicitly a survey: most proofs are sketches and several central results are cited from the literature rather than proved.

Significance. The survey is timely and well structured. Its main value is synthetic: it connects the Kikuchi-graph method, the near-tight rainbow-cycle bound of Alon, Bucić, Sauermann, Zakharov and Zamir, the rainbow-tree route to Ringel's conjecture, and recent transversal results under a single conceptual umbrella, and it correctly identifies the simple Lemma 2.2 as an engine driving several applications. The included proofs are short and checkable, and the survey is candid about which results are stated without proof. The central thesis, that restricted-subgraph questions in edge-colored graphs are a versatile transfer tool, is credible and well supported by the applications to decomposition, additive combinatorics, coding theory, and complexity theory. Because the surveyed results are published and independently checkable, the issues identified below are repairable and do not cast doubt on the body of results surveyed.

major comments (2)
  1. [Section 4.1 (Theorem 4.7)] The proof applies Theorem 4.1 to embed a tree T with n−o(n) vertices into the Cayley-sum-colored K_n. Theorem 4.1 guarantees only a rainbow copy of trees with at most (1−ε)n/k vertices for a fixed ε>0, and for every fixed ε>0 the inequality n−o(n) ≤ (1−ε)n fails for all sufficiently large n. The application is therefore invalid as written, and since this step supplies the rainbow copy S whose translations form the approximate orthogonal double cover, the proof of Theorem 4.7 is incomplete. The author should either weaken the statement to trees with at most (1−ε)n vertices for a fixed ε>0, or provide a different argument establishing the existence of a rainbow copy of a nearly-spanning tree in this specific coloring.
  2. [Section 2 (Lemma 2.2)] The upper-bound part of the proof relies on the assertion that two rainbow paths of length ℓ with the same endpoints must use the same set of colors, with no justification. The assertion is true: if two such paths had different color sets, a color appearing on exactly one of them would appear exactly once in the symmetric difference, which decomposes into cycles of total length at most 2ℓ, yielding a cycle of length at most 2ℓ with an edge of unique color and contradicting the standing assumption. However, because this observation alone yields the ℓ! bound per vertex pair that drives Lemma 2.2 and, through it, Theorems 2.6 and 2.7, it is load-bearing and should be stated and proved in the text rather than left as an unproved 'observe that'.
minor comments (8)
  1. [Section 4.1 (Theorem 4.3)] The shifts of the rainbow tree S0 should be indexed by all residues modulo 2ℓ+1, not by i∈[ℓ]; as written only ℓ+1 copies are constructed, too few to give the claimed 2n+1 copies. Additionally, the application of Theorem 4.1 silently reuses the symbol ε for two different roles; the proof should specify a smaller parameter (e.g., ε/6) so that n+1 ≤ (1−ε')(2ℓ+1)/2.
  2. [Section 4.1 (Theorem 4.5)] The same reuse of the symbol ε occurs here: to apply Theorem 4.1 to a tree with n vertices in K_ℓ with ℓ=(1+ε)n, one must choose a parameter ε' with (1−ε')(1+ε) ≥ 1; the text should name such an ε' explicitly.
  3. [Section 2 (Theorem 2.6)] The inequality e(G) ≥ 2N log₂ N is dismissed as a 'simple but tedious computation'. Since this inequality is the quantitative heart of the even-cover bound, a brief outline of the estimate (for example, that C(n−k,ℓ−k/2)/C(n,ℓ) is of order (ℓ/n)^{k/2}) would let readers verify the claim without redoing the computation.
  4. [Title] The title on the first page reads 'applicati ons', with a space inside the word 'applications'; the title should be corrected.
  5. [Section 1] The introduction places Euler at Catherine the Great's court in St. Petersburg 'at the end of 17th century'; the thirty-six officers problem dates to the end of the 18th century (c. 1779), so the century is misstated.
  6. [Section 4.1] The text attributes the near-distance coloring and the cyclic-decomposition conjecture to 'Kotzig [90]', but reference [90] is a 1966 paper by Rosa; the citations for these two attributions appear to point to the wrong reference.
  7. [Sections 2 and 4.1] 'Caley' should be 'Cayley' in the occurrences 'Caley sum graph' and 'Caley sum coloring'.
  8. [Section 3] Minor wording: 'two alternative proof' should be 'two alternative proofs', and 'Hall-Page conjecture' should be 'Hall-Paige conjecture'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified: the central lemma is proved in the text and the applications are reductions to published, independently checkable theorems.

full rationale

This is a survey paper, and none of its derived claims are equivalent by construction to its inputs. The load-bearing Lemma 2.2 is proved in the text via double-counting rainbow paths; the unproved 'observe that...' step is a standard short argument (if two rainbow paths between the same endpoints used different color sets, their symmetric difference would contain a cycle of length at most 2ℓ in which some color appears exactly once). The applications in Theorems 2.6, 2.7, 2.13, 4.3, 4.5, and 4.7 are concrete reductions to stated external theorems such as Theorem 2.10 and Theorem 4.1, with the relevant constructions fully specified; no fitted parameter is renamed as a prediction. Although the author is an author of many cited results, each cited result is published and independently checkable, and the survey also relies substantially on independent work of Alon, Bucić, Sauermann, Zakharov, and Zamir, Montgomery, Pokrovskiy, Hsieh, Kothari, Mohanty, and others. Self-citation is therefore pervasive but not load-bearing in a circular sense. Minor issues such as the omitted proof of a claim inside Lemma 2.2 and small parameter typos are exposition gaps, not circularity.

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

The survey's central claims rest on a body of prior results, several of which are black-boxed. We list the most load-bearing external theorems and the unproved internal observation. No free parameters are fitted and no new entities are introduced.

assumptions (5)
  • standard math Two rainbow paths of length ℓ between the same endpoints in a properly edge-colored graph, under the assumption that no short unique-color cycle exists, must have the same color set.
    Stated without proof in Lemma 2.2's proof ('observe that...'); if false, the ℓ! upper bound fails.
  • domain assumption Theorem 2.10 (Alon, Bucić, Sauermann, Zakharov, Zamir): average degree at least C log n log log n in a properly edge-colored n-vertex graph forces a rainbow cycle.
    Used as a black box in the proof of Theorem 2.13 part 2; the survey does not reproduce the proof.
  • domain assumption Theorem 4.1 (Montgomery, Pokrovskiy, Sudakov): locally k-bounded edge-colorings of K_n contain rainbow copies of every tree with at most (1-ε)n/k vertices.
    Used as a black box in the proofs of Theorems 4.3, 4.5, and 4.7.
  • standard math The ND-coloring of K_{2n+1} is locally 2-bounded and each color class is a single translation orbit of 2n+1 edges.
    Invoked in the proof of Theorem 4.3; follows from the definition but not proved in the text.
  • standard math Standard estimates for binomial coefficients imply e(G) ≥ 2N log_2 N in Theorem 2.6's proof.
    The 'simple but tedious computation' is omitted.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Restricted subgraphs of edge-colored graphs and applications." pith.science (2026). https://pith.science/paper/3ISH6BL4

@misc{pith2026241213945,
  author       = {Pith},
  title        = {Pith review of: Restricted subgraphs of edge-colored graphs and applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3ISH6BL4}},
  note         = {Machine review of arXiv:2412.13945}
}
read the original abstract

A properly edge-colored graph is a graph with a coloring of its edges such that no vertex is incident to two or more edges of the same color. A subgraph is called rainbow if all its edges have different colors. The problem of finding rainbow subgraphs or other restricted structures in edge-colored graphs has a long history, dating back to Euler's work on Latin squares. It has also proven to be a powerful method for studying several well-known questions in other areas. In this survey, we will provide a brief introduction to this topic, discuss several results in this area, and demonstrate their applications to problems in graph decomposition, additive combinatorics, theoretical computer science, and coding theory.

Figures

Figures reproduced from arXiv: 2412.13945 by the authors.

Figure 1
Figure 1. Correspondence between a Latin square and a proper [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Cayley sum graph of the group F 3 2 with respect to the standard basis and its canonical edge coloring. The above bound has the right order of magnitude. This was shown in [62], using an argument which counts the number of rainbow paths in the edge-colored graph. Moreover the proof produces a cycle with an edge of unique color that has at most logarithmic length. Lemma 2.2. Any properly edge-colored n-vertex graph w… view at source ↗
Figure 3
Figure 3. An illustration of the Kikuchi graph defined above w [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The addition table of the cyclic group Z4, for which the corresponding Latin square does not contain a full transversal. One central problem on Latin squares is to determine which of them have transversals. This question is very difficult even in the case of multiplica…
Figure 5
Figure 5. Figure 5: The ND-coloring of K9 and a rainbow copy of a tree T with four edges. The color of each edge corresponds to its Euclidean length. By taking cyclic shifts of this tree around the centre of the picture we obtain 9 disjoint copies of the tree decomposing K9 (and thus a pr…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A proof of Andersen's rainbow path conjecture for large $n$

    math.CO 2026-08 conditional novelty 8.0 of 10

    For all sufficiently large n, every properly edge-coloured n-vertex complete graph has a rainbow path on n-1 vertices, resolving Andersen's conjecture and its Latin-square analogue for large n.

  2. Recent progress in graph theory using expansion

    math.CO 2026-07 accept novelty 3.0 of 10

    Sublinear expansion—weak neighbourhood growth in sparse graphs—has resolved many long-standing extremal graph theory conjectures, and this survey organizes that progress.

Reference graph

Works this paper leans on

111 extracted references · 73 canonical work pages · cited by 2 Pith papers

  1. [1]

    Adamaszek, P

    A. Adamaszek, P. Allen, C. Grosu and J. Hladk´ y. Almost al l trees are almost graceful. Random Struct. Alg. 56 (2020), 948–987

    2020

  2. [2]

    Aharoni and E

    R. Aharoni and E. Berger. Rainbow matchings in r-partite r-graphs. Electron. J. Combin. , R119, (2009)

    2009

  3. [3]

    Aharoni, E

    R. Aharoni, E. Berger, D. Kotlar and R. Ziv. On a conjectur e of Stein. In Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg , volume 87, pages 203–211. Springer, 2017

    2017

  4. [4]

    Akbari, O

    S. Akbari, O. Etesami, H. Mahini and M. Mahmoody. On rainb ow cycles in edge colored com- plete graphs. Australas. J. Comb. 37 (2007), 33 pages

    2007

  5. [5]

    N. Alon, M. Buci´ c, L. Sauermann, D. Zakharov and O. Zamir . Essentially tight bounds for rainbow cycles in proper edge-colorings. arXiv preprint:2309.04460, 2023

    arXiv 2023

  6. [6]

    N. Alon, U. Feige. On the power of two, three and four probe s. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 , 346–354, 2009. 17

    2009

  7. [7]

    N. Alon, S. Hoory and N. Linial. The Moore Bound for Irregu lar Graphs. Graphs Comb. , 18(1):53–57, 2002

    2002

  8. [8]

    Pokrovskiy and B

    N Alon, A. Pokrovskiy and B. Sudakov. Random subgraphs of properly edge-colored complete graphs and long rainbow cycles. Isr. J. Math. 222 (2017), 317–331

    2017

Show all 111 references
  1. [9]

    Alrabiah and V

    O. Alrabiah and V. Guruswami. Near-Tight Bounds for 3-Qu ery Locally Correctable Binary Linear Codes via Rainbow Cycles. arXiv preprint: 2404.05864 , 2024

    2024 arXiv

  2. [10]

    Alrabiah, V

    O. Alrabiah, V. Guruswami, P. Kothari and P. Manohar. A N ear-Cubic Lower Bound for 3- Query Locally Decodable Codes from Semirandom CSP Refutati on. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20- 23, 2023 , ACM, 1438...

    2023

  3. [11]

    Anastos and P

    M. Anastos and P. Morris. A note on finding large transver sals efficiently. arXiv preprint: 2412.05891, 2024

    2024 arXiv

  4. [12]

    Andersen

    L. Andersen. Hamilton circuits with many colors in prop erly edge-colored complete graphs. Mathematica Scandinavica (1989), 5–14

    1989

  5. [13]

    Balogh and T

    J. Balogh and T. Molla. Long rainbow cycles and Hamilton ian cycles using many colors in properly edge-colored complete graphs. Europ. J. Combin. 79 (2019), 140–151

    2019

  6. [14]

    Bateman and N

    M. Bateman and N. H. Katz. New bounds on cap sets. J. Amer. Math. Soc. 25 (2012), no. 2, 585–613

    2012

  7. [15]

    Benzing, A

    F. Benzing, A. Pokrovskiy and B. Sudakov. Long directed rainbow cycles and rainbow spanning trees. Europ. J. Combin. 88 (2020), Article 103102

    2020

  8. [16]

    R. C. Bose, S. S. Shrikhande and E. T. Parker. Further res ults on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conject ure. Can. J. Math. 12 (1960), 189–203

    1960

  9. [17]

    B¨ ottcher, J

    J. B¨ ottcher, J. Hladk´ y, D. Piguet and A. Taraz. An appr oximate version of the tree packing conjecture. Isr. J. Math. 211 (2016), 391–446

    2016

  10. [18]

    Bourgain

    J. Bourgain. On triples in arithmetic progression. Geom. Funct. Anal. 9 (1999), no. 5, 968–984

    1999

  11. [19]

    A. E. Brouwer, A. de Vries and R. Wieringa. A lower bound f or the length of partial transversals in a Latin square. Nieuw Archief Voor Wiskunde 26 (1978), 330–332

    1978

  12. [20]

    R. A. Brualdi and H. J. Ryser, et al., Comb. matrix theory , volume 39, Springer, 1991

    1991

  13. [21]

    Chakraborti, M

    D. Chakraborti, M. Christoph, Z. Hunter, R. Montgomery and T. Petrov. Almost-full transver- sals in equi- n-squares. arXiv preprint: 2412.07733 , 2024

    2024 arXiv

  14. [22]

    M.-C. Chang. A polynomial bound in Freiman’s theorem. Duke Math. J. 113 (2002), no. 3, 399–419

    2002

  15. [23]

    Chen and X

    H. Chen and X. Li. Long rainbow path in properly edge-col ored complete graphs. arXiv preprint: 1503.04516, 2015

    2015 arXiv

  16. [24]

    Munh´ a Correia, A

    D. Munh´ a Correia, A. Pokrovskiy and B. Sudakov. Short p roofs of rainbow matching results. Int. Math. Res. Not. , 2023(14):12441–12476, 2023. 18

    2023

  17. [25]

    S. Das, C. Lee and B. Sudakov. Rainbow Tur´ an problem for even cycles. Europ. J. Combin. , 34(5):905–915, 2013

    2013

  18. [26]

    J. H. Dinitz and D. R. Stinson. Contemporary design theory: A collection of surveys , volume 26, John Wiley & Sons, 1992

    1992

  19. [27]

    D. A. Drake. Maximal sets of Latin squares and partial tr ansversals. J. Stat. Plan. Inference 1 (1977), 143–149

    1977

  20. [28]

    Z. Dvir. Incidence Theorems and Their Applications. arXiv preprint: 1208.5073 , 2012

    2012 arXiv

  21. [29]

    Eberhard, F

    S. Eberhard, F. Manners and R. Mrazovi´ c. An asymptotic for the Hall–Paige conjecture. Adv. Math. 404 (2022), 108423

    2022

  22. [30]

    Efremenko

    K. Efremenko. 3-query locally decodable codes of subex ponential length. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda , MD, USA, May 31 - June 2, 2009 , ACM, 39–44, 2009

    2009

  23. [31]

    Erd˝ os, A

    P. Erd˝ os, A. Gy´ arf´ as and L. Pyber. Vertex Coverings by Monochromatic Cycles and Trees. J. Comb. Theory Ser. B 51 (1991), 90–95

    1991

  24. [32]

    Erd˝ os and R

    P. Erd˝ os and R. Rado. A combinatorial theorem. J. London Math. Soc. 25 (1950), 249–255

    1950

  25. [33]

    L. Euler. Recherches sur un nouvelle esp´ ece de quarr´ e s magiques. Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissin gen 9 (1782), 85–239

  26. [34]

    U. Feige. Small linear dependencies for binary vectors of low weight. Building Bridges: Between Mathematics and Computer Science , Springer, 283–307, 2008

    2008

  27. [35]

    Feige, J

    U. Feige, J. H. Kim and E. Ofek. Witnesses for non-satisfi ability of dense random 3CNF formulas. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings , IEEE Computer Society, 497–508, 2006

    2006

  28. [36]

    Feige and T

    U. Feige and T. Wagner. Generalized girth problems in gr aphs and hypergraphs. preprint

  29. [37]

    Ferber, C

    A. Ferber, C. Lee and F. Mousset. Packing spanning graph s from separable families. Isr. J. Math. 219 (2017), 959–982

    2017

  30. [38]

    Ferber and W

    A. Ferber and W. Samotij. Packing trees of unbounded deg rees in random graphs. J. Lond. Math. Soc. 99 (2019), 653–677

    2019

  31. [39]

    G. A. Fre ˘ ıman. On the addition of finite sets. Dokl. Akad. Nauk SSSR (1964), 1038–1041

    1964

  32. [40]

    J. A. Gallian. A dynamic survey of graph labeling. The Electron. J. Combin. 16 (2009), 1–219

    2009

  33. [41]

    Gebauer and F

    H. Gebauer and F. Mousset. On rainbow cycles and paths. a rXiv preprint: 1207.0840, 2012

    2012 arXiv

  34. [42]

    Glock, D

    S. Glock, D. K¨ uhn, A. Lo and D. Osthus. The existence of d esigns via iterative absorption. Mem. Am. Math. Soc. 284 (2023), 131 pp

    2023

  35. [43]

    Goldreich, H

    O. Goldreich, H. Karloff, L. Schulman and L. Trevisan. Low er bounds for linear locally decodable codes and private information retrieval. Comput. Complex. , 15(3):263–296, 2006. 19

    2006

  36. [44]

    Graham and N

    R. Graham and N. Sloane. On additive bases and harmoniou s graphs. SIAM J. Alg. Disc. Meth. 1 (1980), 382–404

    1980

  37. [45]

    Green and I

    B. Green and I. Z. Ruzsa, Freiman’s theorem in an arbitra ry abelian group. J. Lond. Math. Soc. (2) 75 (2007), no. 1, 163–175

    2007

  38. [46]

    Gronau, R

    H.D. Gronau, R. C. Mullin and A. Rosa. Orthogonal double covers of complete graphs by trees. Graphs Comb. 13 (1997), 251–262

    1997

  39. [47]

    Guruswami, P

    V. Guruswami, P. Kothari and P. Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , ACM, 678–689, 2022

    2022

  40. [48]

    Gy´ arf´ as and M

    A. Gy´ arf´ as and M. Mhalla. Rainbow and orthogonal path s in factorizations of Kn. J. Comb. Des. 18(2010), 167–176

    2010

  41. [49]

    Gy´ arf´ as, M

    A. Gy´ arf´ as, M. Ruszink´ o, G. S´ ark¨ ozy and R. Schelp.Long rainbow cycles in proper edge- colorings of complete graphs. Australas. J. Comb. 50 (2011), 45–53

    2011

  42. [50]

    G. Hahn. Un jeu de coloration. Regards sur la theorie des graphes , Actes du Colloque de Cerisy, volume 12, page 18, 1980

    1980

  43. [51]

    Hall and L

    M. Hall and L. Paige. Complete mappings of finite groups. Pac. J. Math. 5 (1955), 541–549

    1955

  44. [52]

    Hatami and P

    P. Hatami and P. W. Shor. A lower bound for the length of a p artial transversal in a Latin square. J. Comb. Theory Ser. A 115 (2008), 1103–1113

    2008

  45. [53]

    Hoory, N

    S. Hoory, N. Linial and A. Wigderson. Expander graphs an d their applications. Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561

    2006

  46. [54]

    Hsieh, P

    T. Hsieh, P. Kothari and S. Mohanty. A simple and sharper proof of the hypergraph Moore bound. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algori thms, SODA 2023, Florence, Italy, January 22-25, 2023 , 2324–2344, 2023

    2023

  47. [55]

    Hsieh, P

    T. Hsieh, P. Kothari, S. Mohanty, D. Munh´ a Correia and B . Sudakov. Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-C olored Kikuchi Graphs. arXiv preprint: 2401.11590 , 2024

    2024 arXiv

  48. [56]

    D. Hughes. Biplanes and semi-biplanes. Comb. Math. , Proc. International Conference on Com- binatorial Theory, Canberra, 55–58, 1978

    1978

  49. [57]

    O. Janzer. Rainbow Tur´ an number of even cycles, repeat ed patterns and blow-ups of cycles. Isr. J. Math. , 253(2):813–840, 2023

    2023

  50. [58]

    Janzer and B

    O. Janzer and B. Sudakov. On the Tur´ an number of the hype rcube. Forum Math., Sigma 12 (2024), e38, 1–19

    2024

  51. [59]

    F. Joos, J. Kim, D. K¨ uhn and D. Osthus. Optimal packings of bounded degree trees. J. Eur. Math. Soc. 21 (2019), 3573–3647

    2019

  52. [60]

    J. Kim, J. Lee, H. Liu and T. Tran. Rainbow cycles in prope rly edge-colored graphs. Combina- torica 44 (2024), 909—919. 20

    2024

  53. [61]

    P. Keevash. The existence of designs. arXiv preprint: 1401.3665 , 2014

    2014 arXiv

  54. [62]

    Keevash, D

    P. Keevash, D. Mubayi, B. Sudakov and J. Verstra¨ ete. Ra inbow Turan Problems. Combin. Probab. Comput. 16 (2007), 109–126

    2007

  55. [63]

    Keevash, A

    P. Keevash, A. Pokrovskiy, B. Sudakov and L. Yepremyan. New bounds for Ryser’s conjecture and related problems. Trans. Amer. Math. Soc. Ser B 9 (2022), 288—321

    2022

  56. [64]

    Keevash and K

    P. Keevash and K. Staden. Ringel’s tree packing conject ure in quasirandom graphs. arXiv preprint: 2004.09947 , 2020

    2004 arXiv

  57. [65]

    Kerenidis and R

    I. Kerenidis and R. Wolf. Exponential lower bound for 2- query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. , 69(3):395–420, 2004

    2004

  58. [66]

    J. Kim, D. K¨ uhn, D. Osthus and M. Tyomkyn. A blow-up lemm a for approximate decomposi- tions. Trans. Amer. Math. Soc. 371 (2019), 4655–4742

    2019

  59. [67]

    K. K. Koksma. A lower bound for the order of a partial tran sversal in a Latin square. J. Comb. Theory 7 (1969), 94—95

    1969

  60. [68]

    S. V. Konyagin and I. D. Shkredov. A quantitative versio n of the Beurling-Helson theorem. Funct. Anal. Appl. 49 (2015), no. 2, 110–121, Translation of Funktsional. Anal. i Prilozhen. 49 (2015), no. 2, 39–53

    2015

  61. [69]

    S. V. Konyagin and I. D. Shkredov. On subgraphs of random Cayley sum graphs. Europ. J. Combin. 70 (2018), 61–74

    2018

  62. [70]

    Krivelevich

    M. Krivelevich. Triangle factors in random graphs. Combin. Probab. Comput. 6 (1997), 337–347

    1997

  63. [71]

    Lazebnik, V

    F. Lazebnik, V. Ustimenko and A. Woldar. A new series of d ense graphs of high girth. Bull. Amer. Math. Soc. , 32:73–79, 1995

    1995

  64. [72]

    Leck and V

    U. Leck and V. Leck. On orthogonal double covers by trees . J. Comb. Des. 5 (1997), 433–441

    1997

  65. [73]

    V. F. Lev and R. Yuster. On the size of dissociated bases. Electron. J. Combin. 18 (2011), no. 1, Paper 117, 5pp

    2011

  66. [74]

    Maamoun and H

    M. Maamoun and H. Meyniel. On a problem of G. Hahn about co lored Hamiltonian paths in K2t. Discrete Math. 51 (1984), 213–214

    1984

  67. [75]

    Messuti, V

    S. Messuti, V. R¨ odl and M. Schacht. Packing minor-clos ed families of graphs into complete graphs. J. Comb. Theory Ser. B 119 (2016), 245–265

    2016

  68. [76]

    Montgomery

    R. Montgomery. Spanning trees in random graphs. Adv. Math. 356 (2019), 106793

    2019

  69. [77]

    Montgomery

    R. Montgomery. Transversals in Latin Squares. Surveys in Combinatorics 2024 Cambridge University Press, 131–158

    2024

  70. [78]

    Montgomery

    R. Montgomery. A proof of the Ryser-Brualdi-Stein conj ecture for large even n. arXiv preprint: 2310.19779, 2023

    2023 arXiv

  71. [79]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy and B. Sudakov. Decomposi tions into spanning rainbow struc- tures. Proc. London Math. Soc. 119 (2019), 899–959. 21

    2019

  72. [80]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy and B. Sudakov. Embedding rainbow trees with applications to graph labelling and decomposition. J. European Math. Soc. 22 (2020), 3101–3132

    2020

  73. [81]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy and B. Sudakov. A proof of R ingel’s Conjecture. Geom. Funct. Anal. 31 (2021), 663–720

    2021

  74. [82]

    M¨ uyesser and A

    A. M¨ uyesser and A. Pokrovskiy. A random Hall-Paige con jecture. arXiv preprint:2204.09666 , 2022

    2022 arXiv

  75. [83]

    Naor and J

    A. Naor and J. Verstra¨ ete. Parity check matrices and pr oduct representations of squares. Com- binatorica, 28(2):163–185, 2008

    2008

  76. [84]

    Pokrovskiy

    A. Pokrovskiy. An approximate version of a conjecture o f Aharoni and Berger. Adv. Math. , 333:1197–1241, 2018

    2018

  77. [85]

    Pokrovskiy

    A. Pokrovskiy. Rainbow Subgraphs and their Applicatio ns. Surv. Comb. 2022 Cambridge University Press, page 191–214

    2022

  78. [86]

    Pokrovskiy and B

    A. Pokrovskiy and B. Sudakov. A counterexample to Stein ’s equi-n-square conjecture. Proc. Amer. Math. Soc. , 147(6):2281–2287, 2019

    2019

  79. [87]

    G. Ringel. Theory of graphs and its applications. Proceedings of the Symposium Smolenice, 1963

    1963

  80. [88]

    V. R¨ odl. On a packing and covering problem. Europ. J. Comb. 6 (1985), 69–78

    1985

  81. [89]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski and E. Szemer´ edi. A Dirac-type theorem for 3-uniform hypergraphs. Com- bin. Probab. Comput. 15 (2006), 229–251

    2006

  82. [90]

    A. Rosa. On certain valuations of the vertices of a graph . Theory of Graphs (Internat. Sympo- sium, Rome, 349–355, 1966

    1966

  83. [91]

    H. J. Ryser. Neuere probleme der kombinatorik. Vortr¨ age ¨ uber Kombinatorik, Oberwolfach69:91, 1967

    1967

  84. [92]

    W. Rudin. Fourier analysis on groups . Wiley Classics Library, John Wiley & Sons, Inc., New York, 1990

    1990

  85. [93]

    T. Sanders. On a theorem of Shkredov. Online J. Anal. Comb. (2010), no. 5, 4 pp

    2010

  86. [94]

    T. Sanders. On Roth’s theorem on progressions. Ann. of Math. (2) 174 (2011), no. 1, 619–636

    2011

  87. [95]

    T. Sanders. The structure theory of set addition revisi ted. Bull. Amer. Math. Soc. (N.S.) 50 (2013), no. 1, 93–127

    2013

  88. [96]

    Schoen and I

    T. Schoen and I. D. Shkredov. Additive dimension and a th eorem of Sanders. J. Aust. Math. Soc. 100 (2016), no. 1, 124–144

    2016

  89. [97]

    P. W. Shor. A lower bound for the length of a partial trans versal in a Latin square. J. Comb. Theory Ser. A 33 (1982), 1–8

    1982

  90. [98]

    S. K. Stein. Transversals of Latin squares and their gen eralizations. Pac. J. Math. 59 (1975), 567–575. 22

    1975

  91. [99]

    T. Tao. Product set estimates for non-commutative grou ps. Combinatorica 28 (2008), no. 5, 547–594

    2008

  92. [100]

    G. Tarry. Le probl` eme des 36 officiers. Secr´ etariat de l’Association fran¸ caise pour l’avancement des sciences , 1900

    1900

  93. [101]

    I. Tomon. Robust (rainbow) subdivisions and simplici al cycles. Adv. Comb. , 2024

    2024

  94. [102]

    I.M. Wanless. Transversals in Latin squares: a survey . Surv. Comb. 392, Cambridge University Press, 403–437, 2011

    2011

  95. [103]

    S. Wilcox. Reduction of the Hall–Paige conjecture to s poradic simple groups. J. Algebra 321 (2009), 1407–1428

    2009

  96. [104]

    R. M. Wilson. Decompositions of complete graphs into s ubgraphs isomorphic to a given graph. Proc. 5th British Combinatorial Conf. , 1975

    1975

  97. [105]

    D. E. Woolbright. An n×n Latin square has a transversal with at least n−√n distinct symbols. J. Comb. Theory Ser. A 24 (1978), 235–237

    1978

  98. [106]

    W´ ozniak

    M. W´ ozniak. Packing of graphs and permutations—a sur vey. Discrete Math. 276 (2004), 379– 391

    2004

  99. [107]

    H. Yap. Packing of graphs — a survey. Ann. Discrete Math. 38 (1988), 395–404

    1988

  100. [108]

    Yekhanin

    S. Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM , 55(1):1–16, 2008

    2008

  101. [109]

    Yekhanin

    S. Yekhanin. Locally Decodable Codes and Private Info rmation Retrieval Schemes. Inf. Secur. Cryptogr., Springer, 2010

    2010

  102. [110]

    Yekhanin

    S. Yekhanin. Locally Decodable Codes. Found. Trends Theor. Comput. Sci. , Now Publishers, Inc., 6(3):139–255, 2012

    2012

  103. [111]

    A. ˙Zak. Harmonious order of graphs. Discrete Math. 309 (2009), 6055–6064. 23

    2009

Pith tools

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