alphaFeedback

WorksMathematics

Critical edges in labelled complete graphs

AI contributions
  • OpenAI ChatGPT GPT-6 Astra
View details

Abstract

In a complete graph whose edges have labels 1,...,ell, an edge is critical for a matching if its label is smaller than that of a matching edge sharing an endpoint. The parameter gamma(ell) is the asymptotic worst-case, over labelings, of the smallest critical-edge count obtainable by choosing the matching, normalized by the number of pairs of covered vertices; gamma'(ell) is its perfect-matching version. These parameters arise in bounds for finding cliques in random graphs by edge queries in a prescribed number of rounds. We prove 0.419772820486... <= gamma'(4) <= gamma(4) <= 0.4334035. For every ell >= 2 we give an explicit construction proving gamma'(ell) >= 1/2-1/[4(ell-1)]. We also improve the state-of-the-art upper bounds for general ell, obtaining gamma(ell) <= 1/2-4/(52^ell) +O(2^(-3ell/2)) as ell tends to infinity, together with explicit finite bounds. The proofs of upper bounds compare matchings obtained by local exchanges. The proofs of lower bounds use labelings that are constant on pairs of vertex parts; the stronger four-label construction has six parts and an algebraic value of degree six. Exact-arithmetic verification programs and their data are included for the computer-assisted parts of the proofs.

Introduction

A matching in an edge-labelled complete graph assigns a label to each vertex it covers: the label of its matching edge. We ask how to choose a matching so that few graph edges have a smaller label than at least one of the matching edges incident to them, that is, smaller than at least one of its endpoints. This extremal problem was introduced by Csókа and Pongrácz [1] in their study of algorithms that find cliques and dense subgraphs by querying edges of a random graph. We improve both upper bounds for arbitrary labelings and lower bounds obtained from explicit constructions.

The extremal parameters

Let KNK_N be a complete graph on NN vertices. Let λ:E(KN)→{1,…,ℓ}\lambda:E(K_N)\to\{1,\ldots,\ell\} be an edge labeling and let M\mathcal{M} be a matching of size MM. For a covered vertex vv, define bM(v)b_{\mathcal{M}}(v) to be the label of the unique matching edge incident to vv, and put bM(v)=0b_{\mathcal{M}}(v)=0 for an uncovered vertex. We call this number the birth label of vv. An edge uvuv is critical for M\mathcal{M} when

λ(uv)<max⁡{bM(u),bM(v)}.\lambda(uv)<\max\{b_{\mathcal{M}}(u),b_{\mathcal{M}}(v)\}.

For example, if uu is matched by an edge of label 3, then every edge of label 1 or 2 incident to uu is critical. A matching edge itself is never critical. An edge from a covered vertex to an uncovered vertex can be critical; such an edge is called outward critical.

Write Cλ(M)C_\lambda(\mathcal{M}) for the total number of critical edges, including outward critical edges. Following [1], define

γ(ℓ)=lim sup⁡M→∞sup⁡N≥2Mmax⁡λmin⁡∣M∣=MCλ(M)(2M2).(1)\gamma(\ell)=\limsup_{M\to\infty}\sup_{N\ge2M}\max_{\lambda}\min_{|\mathcal{M}|=M}\frac{C_\lambda(\mathcal{M})}{\binom{2M}{2}}. \tag*{(1)}

Thus the labeling is chosen first and the matching second. The normalizing denominator counts pairs among the 2M2M covered vertices, even though the numerator also counts outward critical edges. The perfect-matching version is

γ′(ℓ)=lim sup⁡M→∞max⁡λ:E(K2M)→[ℓ]min⁡M perfectCλ(M)(2M2),[ℓ]={1,…,ℓ}.\gamma'(\ell)=\limsup_{M\to\infty}\max_{\lambda:E(K_{2M})\to[\ell]}\min_{\mathcal{M}\ \mathrm{perfect}}\frac{C_\lambda(\mathcal{M})}{\binom{2M}{2}},\qquad[\ell]=\{1,\ldots,\ell\}.

In particular γ′(ℓ)≤γ(ℓ)\gamma'(\ell) \le\gamma(\ell). An upper bound for γ(ℓ)\gamma(\ell) must work for arbitrarily many uncovered vertices; a lower construction on 2M2M vertices already bounds both parameters from below.

Csóka and Pongrácz [1] proved γ′(2)=γ(2)=1/4\gamma'(2) = \gamma(2) = 1/4 and γ′(3)=γ(3)=3/8\gamma'(3) = \gamma(3) = 3/8. For four labels their estimates were

512≤γ′(4)≤γ(4)≤716.\frac{5}{12} \le\gamma'(4) \le\gamma(4) \le\frac{7}{16}.

For every ℓ≥4\ell\ge4 they established

γ(ℓ)≤12−13⋅2ℓ−1−4ℓ+8.(2)\gamma(\ell) \le\frac{1}{2} - \frac{1}{3 \cdot2^{\ell-1} - 4\ell+ 8}. \tag*{(2)}

They also showed that the corresponding parameter with arbitrarily many labels equals 1/21/2.

Results

Theorem 1.1. Let αL\alpha_L be the algebraic number specified in § 17. Then

0.41977282048624007772…=αL≤γ′(4)≤γ(4)≤8668072000000=0.4334035.0.41977282048624007772\ldots= \alpha_L \le\gamma'(4) \le\gamma(4) \le\frac{866807}{2000000} = 0.4334035.

The lower bound is realized by a labeling on six vertex parts whose proportions belong to a number field of degree six.

The lower bound extends the search for explicit extremal labelings, whereas the upper bound asserts that every four-label instance has an appropriate matching. The two estimates leave a gap; no equality between γ′(4)\gamma'(4) and γ(4)\gamma(4) is assumed.

Theorem 1.2. For every integer ℓ≥2\ell\ge2,

γ′(ℓ)≥12−14(ℓ−1).\gamma'(\ell) \ge\frac{1}{2} - \frac{1}{4(\ell-1)}.

For ℓ≥5\ell\ge5, put k=2ℓ−2k = 2^{\ell-2} and S=3k−2ℓ+4S = 3k - 2\ell+ 4. Then

γ(ℓ)≤12−12S−1648k.\gamma(\ell) \le\frac{1}{2} - \frac{1}{2S} - \frac{1}{648k}.

In addition,

γ(ℓ)≤12−15k+2225k3/2+O(log⁡kk2)(ℓ→∞).\gamma(\ell) \le\frac{1}{2} - \frac{1}{5k} + \frac{2\sqrt{2}}{25k^{3/2}} + O\left(\frac{\log k}{k^2}\right) \qquad(\ell\to\infty).

The general lower construction has ℓ\ell vertex parts. Its exact finite matching minimum and the optimality of its part proportions are proved in § 2. The optimality is within the specified labeling family, with one part of mass at least 1/21/2. For ℓ=4\ell= 4 it recovers 5/125/12; the six-part construction of Theorem 1.1 gives the stronger value above.

The finite general upper bound improves (2) by 1/(162⋅2ℓ)1/(162 \cdot2^\ell). The asymptotic upper bound increases the leading gap below 1/21/2 from 1/(6k)1/(6k) to 1/(5k)1/(5k), a factor of 6/56/5. The error term in that statement is necessary. For finite ℓ\ell, Theorem 16.1 gives a rational two-variable quadratic formula; it is this finite formula, and the bound in Section 15, that produce the following certified estimates.

ℓ\ellLower boundUpper bound
40.4197728204860.4334035
57/167/160.471876610486
69/209/200.487382111461
711/2411/240.494116218018
813/2813/280.497175259512
915/3215/320.498622167790
1017/3617/360.499299501525
1119/4019/400.499630626700
1221/4421/440.499810572146

Table 1.

The lower bounds apply to γ′\gamma' and hence to γ\gamma. The upper bounds apply to γ\gamma and hence to γ′\gamma'. Displayed decimal lower bounds are rounded downward, and upper bounds upward. The general-label upper entries are verified rational choices of the parameters in the finite formulas; they are not claims of optimality over all possible matching arguments.

Proof strategy and organization

The general lower construction in § 2 provides an elementary example of the problem. Its proof counts critical edges for an arbitrary perfect matching, without a computer calculation.

For the upper bounds, we start with a matching chosen by the order of [1]. This order prevents several small exchanges that would reduce its weight. Those restrictions bound the number of critical edges inside and between the sets of vertices covered by matching edges of each label. The original estimate is sharp only if several of these counts are simultaneously large. We show that such a configuration permits other matchings with smaller critical-edge counts.

The four-label argument begins in § 3. We describe the exchanges explicitly and keep track of the edges that prevent each exchange. This leads to a finite family of quadratic inequalities. § 13 combines these inequalities to prove the numerical bound. Each combination has rational coefficients, and its validity is checked by an exact matrix factorization. The combinatorial derivations are given in the text; the supplied programs check the resulting identities, signs, and coverage of the parameter ranges.

For general ℓ\ell, alternating paths provide a systematic family of exchanges. Sections 14–§ 16 derive the corresponding finite and asymptotic upper bounds. The estimates account for outward critical edges, so the number of uncovered vertices does not enter the error terms.

§ 17 proves the six-part lower bound. For a labeling constant on pairs of vertex parts, a matching is described by the amount it matches between each pair of parts. These amounts satisfy linear constraints, and the noncritical-edge count is a quadratic function of them. We bound this function over the entire feasible set using exact algebraic arithmetic. The algebraic number and the part proportions are specified explicitly. Appendix § 19 examine small perturbations of this construction. § 18 gives the verification commands and identifies the data needed for each computational claim.

Two normalizations occur in the proofs. Upper-bound counts are divided by M2M^2, so their conversion to γ\gamma includes a factor of 1/21/2, since (2M2)=2M2−M\binom{2M}{2}=2M^2-M. Lower constructions use vertex masses summing to one and the density of ordered critical pairs; this is already on the γ′\gamma' scale. The convention is stated again at the start of each argument.

Application to clique queries

Consider an Erdős–Rényi graph G(n,1/2)G(n,1/2) whose edges are initially unknown. An algorithm may query at most nδn^\delta pairs in ℓ\ell rounds, choosing all queries of a round before receiving the answers to that round. Let α∗(δ,ℓ)\alpha_*(\delta,\ell) be the supremum of the constants α\alpha for which such an algorithm finds a clique of size (α+o(1))log⁡2n(\alpha+o(1))\log_2 n with probability tending to one. Computational time is unrestricted.

Feige, Gamarnik, Neeman, Rácz, and Tetali [2] obtained upper bounds in this query model, and Feige and Ferster [3] sharpened the analysis for two and three rounds. The clique-query theorem of Csóka and Pongrácz [1] gives, for 1≤δ≤21\le\delta\le2 and ℓ≥3\ell\ge3,

α∗(δ,ℓ)≤1+1−(2−δ)24γ(ℓ).\alpha_*(\delta,\ell) \le1+\sqrt{1-\frac{(2-\delta)^2}{4\gamma(\ell)}}.

Consequently any upper bound GℓG_\ell for γ(ℓ)\gamma(\ell) proved here can replace γ(ℓ)\gamma(\ell) on the right. In particular one may use G4=0.4334035G_4=0.4334035. Our lower constructions bound the combinatorial parameters; they do not assert the existence of clique-query algorithms attaining the corresponding expression.

A lower bound for every number of labels

The following construction extends the four-part labeling of Csókа and Pongrácz [1], which gives the lower bound 5/125/12 for four labels. Its advantage is that the minimum over all perfect matchings can be calculated exactly for every number of labels.

Theorem 2.1. For every integer ℓ≥2\ell\ge2,

γ(ℓ)≥γ′(ℓ)≥12−14(ℓ−1).\gamma(\ell) \ge\gamma'(\ell) \ge\frac{1}{2} - \frac{1}{4(\ell-1)}.

In particular these lower bounds tend to 1/21/2 as ℓ→∞\ell\to\infty.

Put m=ℓ−1m=\ell-1. The construction has parts A1,…,Am,RA_1,\ldots,A_m,R with vertex proportions

a1=14m,ai=12m(2≤i≤m),r=2m+14m.(3)a_1=\frac{1}{4m},\qquad a_i=\frac{1}{2m}\quad(2\le i\le m),\qquad r=\frac{2m+1}{4m}. \tag*{(3)}

The part RR provides a reservoir of possible matching partners for the other parts, which we call satellites. Labels are constant on each pair of parts and are given by

λ(Ai,Aj)=max⁡{1,min⁡(i,j)−1},λ(Ai,R)=i,λ(R,R)=m+1.(4)\lambda(A_i,A_j)=\max\{1,\min(i,j)-1\},\qquad\lambda(A_i,R)=i,\qquad\lambda(R,R)=m+1. \tag*{(4)}

The first rule includes i=ji=j and hence specifies all internal labels. When ℓ=4\ell=4, the proportions are (1,2,2,7)/12(1,2,2,7)/12, and the label matrix is exactly the one in [1].

Proof of Theorem 2.1. We prove an exact finite statement. For any positive integer qq, take N=4mqN=4mq vertices and parts of sizes

∣A1∣=q,∣Ai∣=2q (2≤i≤m),∣R∣=(2m+1)q.|A_1|=q,\qquad|A_i|=2q\ (2\le i\le m),\qquad|R|=(2m+1)q.

Write A=⋃i=1mAiA=\bigcup_{i=1}^{m}A_i, s=∣A∣=(2m−1)qs=|A|=(2m-1)q, and rN=∣R∣r_N=|R|. We claim that the minimum number of critical edges over all perfect matchings is

(4m2−2m)q2−(m−1)q.(5)(4m^2-2m)q^2-(m-1)q. \tag*{(5)}

Fix a perfect matching. Let xix_i count its edges between AiA_i and RR, and put

X=∑i=2mxi,pi=∑j<i∣Aj∣.X=\sum_{i=2}^{m}x_i,\qquad p_i=\sum_{j<i}|A_j|.

References

  1. [1]E. Csóka and A. Pongrácz, Finding cliques and dense subgraphs using edge queries, Discrete Mathematics 349(10) (2026), 115226. doi:10.1016/j.disc.2026.115226. Preprint: arXiv:2310.06826.DOI
  2. [2]U. Feige, D. Gamarnik, J. Neeman, M. Z. Rácz, and P. Tetali, Finding cliques using few probes, Random Structures & Algorithms 56(1) (2020), 142–153. doi:10.1002/rsa.20896.DOI
  3. [3]U. Feige and T. Ferster, A tight bound for the clique query problem in two rounds, arXiv:2112.06072 (2021). https://arxiv.org/abs/2112.06072.
  4. [4]D. König, Graphok és matricok, Matematikai és Fizikai Lapok 38 (1931), 116–119. English translation by G. Szárnyas, arXiv:2009.03780 (2020), https://arxiv.org/abs/2009.03780.
  5. [5]P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Mathematica Academiae Scientiarum Hungaricae 10 (1959), 337–356. https://users.renyi.hu/~p_erdos/1959–10.pdf.DOI
  6. [6]W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22(2) (1947), 107–111. doi:10.1112/jlms/s1-22.2.107.DOI
  7. [7]C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences of the USA 43(9) (1957), 842–844. doi:10.1073/pnas.43.9.842.DOI
  8. [8]A. Schrijver, Tutte–Berge ⇒ Gallai ⇒ Mader, seminar notes, https://homepages.cwi.nl/~lex/files/mader_gallai_tutteb.pdf, accessed 9 November 2026.
  9. [9]L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. doi:10.1090/coll/060.DOI
  10. [10]H. Peyrl and P. A. Parrilo, Computing sum of squares decompositions with rational coefficients, Theoretical Computer Science 409(2) (2008), 269–281. doi:10.1016/j.tcs.2008.09.025.DOI

Paper details

vlnc:W_bqccmyzd
v1 · latestHistory (1)

published · Fresh — published within the last 30 days

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

OpenAI ChatGPT GPT-6 Astra · View statement →

Looking for related papers…
Contents