[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Submodular Functions and Rooted Trees

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

A Correction to this article was published on 28 November 2022

This article has been updated

Abstract

For any positive number k and for any hypergraph H with vertex set V(H) and edge set \(\mathrm {E}(H)\subseteq 2^{\mathrm {V}(H)}\), we call \(U\subseteq \mathrm {V}(H)\) a k-antimatching of H if for every matching \(F\subseteq \mathrm {E}(H)\) it holds rankA[U,F] ≤ k, where A is the V(H) ×E(H) (0,1) matrix whose (v,e)-entry is 1 if and only if v ∈ e. Consider a finite poset P with a unique maximal element and having a rooted tree as its Hasse diagram. Let H be the hypergraph with V(H) = P and with E(H) being the set of all down-sets of P. Let μ be a submodular function defined on 2V(H) such that μ(V(H)) ≥ d + (ℓ − 1)c for a positive integer ℓ and two nonnegative reals d and c. For any nonnegative reals d1,…,dℓ with \({\sum }_{i=1}^{\ell } d_{i}=d\), we show that either there is a matching {D1,…,Dℓ} of H with μ(Di) ≥ di for all i, or there is a 1-antimatching C of H such that μ(C) ≥ c. We establish a countable version of this result by assuming further that μ satisfies the weak Fatou property and reverse Fatou property. We propose a conjecture on a possible extension of our result from 1-antimatching to general k-antimatchings.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Change history

References

  1. Dellacherie, C., Meyer, P.-A.: Probabilités Et Potentiel, p. 291. Hermann. Chapitres I à IV, Édition entièrement refondue, Publications de l’Institut de Mathématique de l’Université de Strasbourg, No. XV, Actualités Scientifiques et Industrielles, No. 1372 (1975)

  2. Wu, Y., Zhu, Y.: Weighted rooted trees: fat or tall? In: Fernau, H. (ed.) Computer Science—Theory and Applications. https://doi.org/10.1007/978-3-030-50026-9_30, pp 406–418. Springer (2020)

  3. Albin, N., Clemens, J., Fernando, N., Poggi-Corradini, P.: Blocking duality for p-modulus on networks and applications. Ann. Mat. Pura Appl. (4) 198(3), 973–999 (2019). https://doi.org/10.1007/s10231-018-0806-0https://doi.org/10.1007/s10231-018-0806-0

    Article  MathSciNet  MATH  Google Scholar 

  4. Artstein-Avidan, S., Milman, V.: The concept of duality in convex analysis, and the characterization of the Legendre transform. Ann. Math. (2) 169(2), 661–674 (2009). https://doi.org/10.4007/annals.2009.169.661https://doi.org/10.4007/annals.2009.169.661

    Article  MathSciNet  MATH  Google Scholar 

  5. Luenberger, D. G.: A double look at duality. IEEE Trans. Autom. Control 37(10), 1474–1482 (1992). https://doi.org/10.1109/9.256366

    Article  MathSciNet  MATH  Google Scholar 

  6. Tao, T.: Higher Order Fourier Analysis. Graduate Studies in Mathematics, vol. 142, p. 187 American Mathematical Society. https://doi.org/10.1090/gsm/142 (2012)

  7. Gascuel, O., Steel, M.: A Darwinian uncertainty principle. Syst. Biol. 69(3), 521–529 (2020). https://doi.org/10.1093/sysbio/syz054

    Article  Google Scholar 

  8. Meerkoetter, K.: Uncertainty relation for multidimensional discrete signals. Multidimens. Syst. Signal Process. 28(2), 389–406 (2017). https://doi.org/10.1007/s11045-015-0346-3

    Article  MathSciNet  MATH  Google Scholar 

  9. Ram Murty, M.: Some remarks on the discrete uncertainty principle. In: Highly Composite: Papers in Number Theory. Ramanujan Mathematical Society Lecture Notes Series. https://mast.queensu.ca/~murty/BaluConference.pdf, vol. 23, pp 77–85. Ramanujan Mathematical Society (2016)

  10. Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935). https://doi.org/10.1007/978-0-8176-4842-8_3

    Article  MathSciNet  MATH  Google Scholar 

  11. Dilworth, R. P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161–166 (1950). https://doi.org/10.2307/1969503

    Article  MathSciNet  MATH  Google Scholar 

  12. Mirsky, L.: A dual of Dilworth’s decomposition theorem. Amer. Math. Mon. 78, 876–877 (1971). https://doi.org/10.2307/2316481

    Article  MathSciNet  MATH  Google Scholar 

  13. Gallai, T., Milgram, A. N.: Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sci. Math. (Szeged) 21, 181–186 (1960)

    MathSciNet  MATH  Google Scholar 

  14. Gallai, T.: On Directed Paths and Circuits. In: Theory of Graphs (Proc. Colloq., Tihany, 1966), pp 115–118. Academic Press (1968)

  15. Roy, B.: Nombre chromatique et plus longs chemins d’un graphe. Rev. Franç. Inform. Rech. Opér. 1(5), 129–132 (1967)

    MathSciNet  MATH  Google Scholar 

  16. Lovász, L.: A characterization of perfect graphs. J. Combin. Theory Ser. B 13, 95–98 (1972). https://doi.org/10.1016/0095-8956(72)90045-7

    Article  MathSciNet  MATH  Google Scholar 

  17. Davey, B. A., Priestley, H. A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511809088 (2002)

  18. Malvestuto, F.M.: A new notion of convexity in digraphs with an application to Bayesian networks. Discrete Math. Algorithms Appl. 9 (2), 1750016–22 (2017). https://doi.org/10.1142/S1793830917500161https://doi.org/10.1142/S1793830917500161

    Article  MathSciNet  MATH  Google Scholar 

  19. Akin, E.: Recurrence in Topological Dynamics: Furstenberg Families and Ellis Actions. The University Series in Mathematics, p. 265. Plenum Press. https://doi.org/10.1007/978-1-4757-2668-8 (1997)

  20. Berghammer, R., Winter, M.: Order- and graph-theoretic investigation of dimensions of finite topological spaces and Alexandroff spaces. Monatsh. Math. 190(1), 33–78 (2019). https://doi.org/10.1007/s00605-019-01261-1https://doi.org/10.1007/s00605-019-01261-1

    Article  MathSciNet  MATH  Google Scholar 

  21. Wu, Y., Zhao, D.: Three conjectures of Ostrander on digraph Laplacian eigenvectors. Art Discrete Appl. Math. 4(2), 1–21 (2021). https://doi.org/10.26493/2590-9770.1420.b57. Paper No. 2.08

    MathSciNet  Google Scholar 

  22. Edelman, P. H., Saks, M. E.: Combinatorial representation and convex dimension of convex geometries. Order 5(1), 23–32 (1988). https://doi.org/10.1007/BF00143895

    Article  MathSciNet  MATH  Google Scholar 

  23. Korte, B., Lovász, L.: Homomorphisms and Ramsey properties of antimatroids. Discrete Appl. Math. 15(2–3), 283–290 (1986). https://doi.org/10.1016/0166-218X(86)90049-1

    Article  MathSciNet  MATH  Google Scholar 

  24. Habib, M., Nourine, L.: Representation of lattices via set-colored posets. Discrete Appl. Math. 249, 64–73 (2018). https://doi.org/10.1016/j.dam.2018.03.068

    Article  MathSciNet  MATH  Google Scholar 

  25. Rota, G. -C.: The many lives of lattice theory. Notices Am. Math. Soc. 44(11), 1440–1445 (1997)

    MathSciNet  MATH  Google Scholar 

  26. Libkin, L., Gurvich, V.: Trees as semilattices. Discrete Math. 145(1–3), 321–327 (1995). https://doi.org/10.1016/0012-365X(94)00046-Lhttps://doi.org/10.1016/0012-365X(94)00046-L

    Article  MathSciNet  MATH  Google Scholar 

  27. Luccio, F.: Arithmetic for rooted trees. Theory Comput. Syst. 60(1), 33–52 (2017). https://doi.org/10.1007/s00224-016-9731-zhttps://doi.org/10.1007/s00224-016-9731-z

    Article  MathSciNet  MATH  Google Scholar 

  28. Talagrand, M.: The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer Monographs in Mathematics, p. 222. Springer. https://doi.org/10.1007/3-540-27499-5 (2005)

  29. Frankl, P., Tokushige, N.: Extremal Problems for Finite Sets. Student Mathematical Library, vol. 86, p. 224 American Mathematical Society. https://doi.org/10.1090/stml/086 (2018)

  30. Klain, D. A., Rota, G. -C.: Introduction to Geometric Probability. Lezioni Lincee. [Lincei Lectures], p. 178. Cambridge University Press (1997)

  31. Lovász, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Grötschel, M. (eds.) Mathematical Programming: The State of the Art (Bonn, 1982). https://doi.org/10.1007/978-3-642-68874-4_10, pp 235–257. Springer (1983)

  32. Bonamy, M., Bousquet, N., Thomassé, S.: The Erdös-Hajnal conjecture for long holes and antiholes. SIAM J. Discrete Math. 30(2), 1159–1164 (2016). https://doi.org/10.1137/140981745

    Article  MathSciNet  MATH  Google Scholar 

  33. Song, Z. -X., Ward, T., York, A.: A note on weighted rooted trees. Discrete Math. 338(12), 2492–2494 (2015). https://doi.org/10.1016/j.disc.2015.06.014

    Article  MathSciNet  MATH  Google Scholar 

  34. Grabisch, M.: Set Functions, Games and Capacities in Decision Making. Theory and Decision Library C. Game Theory, Social Choice, Decision Theory, and Optimization, vol. 46, p. 473. Springer (2016)

  35. Fujishige, S.: Polymatroidal dependence structure of a set of random variables. Inform. Control 39(1), 55–72 (1978). https://doi.org/10.1016/S0019-9958(78)91063-X

    Article  MathSciNet  MATH  Google Scholar 

  36. Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra. In: Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alta. 1969), pp 69–87. Gordon and Breach (1970)

  37. Jowett, S., Mo, S., Whittle, G.: Connectivity functions and polymatroids. Adv. Appl. Math. 81, 1–12 (2016). https://doi.org/10.1016/j.aam.2016.06.004

    Article  MathSciNet  MATH  Google Scholar 

  38. Huber, K. T., Moulton, V., Steel, M.: Phylogenetic flexibility via Hall-type inequalities and submodularity. Bull. Math. Biol. 81(2), 598–617 (2019). https://doi.org/10.1007/s11538-018-0419-1

    Article  MathSciNet  MATH  Google Scholar 

  39. Tao, T.: An Introduction to Measure Theory. Graduate Studies in Mathematics, vol. 126, p. 206 American Mathematical Society. https://doi.org/10.1090/gsm/126(2011)

  40. Talagrand, M.: Maharam’s problem. Ann. Math. (2) 168 (3), 981–1009 (2008). https://doi.org/10.4007/annals.2008.168.981https://doi.org/10.4007/annals.2008.168.981

    Article  MathSciNet  MATH  Google Scholar 

  41. Yosida, K., Hewitt, E.: Finitely additive measures. Trans. Am. Math. Soc. 72, 46–66 (1952). https://doi.org/10.2307/1990654https://doi.org/10.2307/1990654

    Article  MathSciNet  MATH  Google Scholar 

  42. König, H.: Measure and Integration: An Advanced Course in Basic Procedures and Applications, p. 260. Springer. Corrected, 2nd printing (2009)

  43. Pietsch, A.: History of Banach Spaces and Linear Operators, p 855. Birkhäuser, Boston (2007). https://doi.org/10.1007/978-0-8176-4596-0

    MATH  Google Scholar 

  44. Ben-Eliezer, I., Krivelevich, M., Sudakov, B.: The size Ramsey number of a directed path. J. Combin. Theory Ser. B 102(3), 743–755 (2012). https://doi.org/10.1016/j.jctb.2011.10.10.002

    Article  MathSciNet  MATH  Google Scholar 

  45. Wu, Y., Zhu, Y.: BBT tree orders of countable connected graphs (2020)

  46. Gelfand, I. M., Goresky, R. M., MacPherson, R. D., Serganova, V. V.: Combinatorial geometries, convex polyhedra, and Schubert cells. Adv. Math. 63(3), 301–316 (1987). https://doi.org/10.1016/0001-8708(87)90059-4https://doi.org/10.1016/0001-8708(87)90059-4

    Article  MathSciNet  MATH  Google Scholar 

  47. Murota, K.: Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications, p. 389. Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9780898718508https://doi.org/10.1137/1.9780898718508 (2003)

  48. Shapley, L.S.: Cores of convex games. Int. J. Game Theory 1, 11–261197172199 (1971/72). https://doi.org/10.1007/BF01753431

  49. Kannai, Y.: The Core and balancedness. In: Aumann, R., Hart, S (eds.) Handbook of Game Theory with Economic Applications, Chap. 12. https://doi.org/10.1016/S1574-0005(05)80015-3, vol. 1, pp 355–395, North-Holland (1992)

  50. Abe, T.: Decomposing a balanced game: a necessary and sufficient condition for the nonemptiness of the core. Econ. Lett. 176, 9–13 (2019). https://doi.org/10.1016/j.econlet.2018.12.009

    Article  MathSciNet  MATH  Google Scholar 

  51. Forand, J. G., Uyanik, M.: Fixed-point approaches to the proof of the Bondareva-Shapley Theorem. Econ. Theory Bull. 7(1), 117–124 (2019). https://doi.org/10.1007/s40505-018-0146-7

    Article  MathSciNet  Google Scholar 

  52. Kannai, Y.: Countably additive measures in cores of games. J. Math. Anal. Appl. 27, 227–240 (1969). https://doi.org/10.1016/0022-247X(69)90044-4

    Article  MathSciNet  MATH  Google Scholar 

  53. Pintér, M.: Algebraic duality theorems for infinite LP problems. Linear Algebra Appl. 434(3), 688–693 (2011). https://doi.org/10.1016/j.laa.2010.10.09.007

    Article  MathSciNet  MATH  Google Scholar 

  54. Schmeidler, D.: On balanced games with infinitely many players. Technical report, The Hebrew University of Jerusalem, Jerusalem, Israel. Research program in game theory and mathematical economics (1967)

  55. Fragnelli, V., Llorca, N., Sánchez-Soriano, J., Tijs, S., Branzei, R.: Convex games with an infinite number of players and sequencing situations. J. Math. Anal. Appl. 362(1), 200–209 (2010). https://doi.org/10.1016/j.jmaa.2009.07.057

    Article  MathSciNet  MATH  Google Scholar 

  56. Chateauneuf, A., Ventura, C.: Partial probabilistic information. J. Math. Econ. 47(1), 22–28 (2011). https://doi.org/10.1016/j.jmateco.2010.10.09.007

    Article  MathSciNet  MATH  Google Scholar 

  57. Kindler, J.: The sigma-core of convex games and the problem of measure extension. Manuscr. Math. 66(1), 97–108 (1989). https://doi.org/10.1007/BF02568484

    Article  MathSciNet  MATH  Google Scholar 

  58. Parker, J. M.: The sigma-core of a cooperative game. Manuscr. Math. 70(3), 247–253 (1991). https://doi.org/10.1007/BF02568374

    Article  MathSciNet  MATH  Google Scholar 

  59. Parker, J. M.: Extreme points of a set of contents majorized by a submodular set function. Arch. Math. (Basel) 59(6), 572–580 (1992). https://doi.org/10.1007/BF01194850

    Article  MathSciNet  MATH  Google Scholar 

  60. Sagara, N., Vlach, M.: A new class of convex games on σ-algebras and the optimal partitioning of measurable spaces. Int. J. Game Theory 40 (3), 617–630 (2011). https://doi.org/10.1007/s00182-010-0258-2https://doi.org/10.1007/s00182-010-0258-2

    Article  MathSciNet  MATH  Google Scholar 

  61. Schmeidler, D.: Cores of exact games. I. J. Math. Anal. Appl. 40, 214–225 (1972). https://doi.org/10.1016/0022-247X(72)90045-5https://doi.org/10.1016/0022-247X(72)90045-5

    Article  MathSciNet  MATH  Google Scholar 

  62. Choquet, G.: Theory of capacities. Ann. Inst. Fourier (Grenoble) 5, 131–295 (1954). https://doi.org/10.5802/aif.53https://doi.org/10.5802/aif.53

    Article  MathSciNet  MATH  Google Scholar 

  63. Alfonsi, A.: A simple proof for the convexity of the Choquet integral. Statist. Probab. Lett. 104, 22–25 (2015). https://doi.org/10.1016/j.spl.2015.04.022

    Article  MathSciNet  MATH  Google Scholar 

  64. Wang, F., Wu, X. -Y., Zhu, R.: Last passage percolation on the complete graph. Stat. Probab. Lett. 164, 108798–10 (2020). https://doi.org/10.1016/j.spl.2020.108798

    Article  MathSciNet  MATH  Google Scholar 

  65. Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms, p 470. Addison-Wesley Publishing Co., Reading (1975). Second printing, Addison-Wesley Series in Computer Science and Information Processing

    Google Scholar 

  66. Joó, A.: Gomory-Hu trees of infinite graphs with finite total weight. J. Graph Theory 88(1), 222–231 (2018). https://doi.org/10.1002/jgt.22207

    Article  MathSciNet  MATH  Google Scholar 

  67. Jung, H. A.: Wurzelbäume und unendliche Wege in Graphen. Math. Nachr. 41, 1–22 (1969). https://doi.org/10.1002/mana.19690410102

    Article  MathSciNet  MATH  Google Scholar 

  68. Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173, p. 411. Springer (2005)

Download references

Acknowledgments

This work was supported by National Natural Science Foundation of China (11971305,11671258).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences and MOE-LSC, Shanghai Jiao Tong University, Dongchuan Rd. 800, Shanghai, 200240, China

    Yaokun Wu & Yinfeng Zhu

Authors
  1. Yaokun Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yinfeng Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yaokun Wu.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The original online version of this article was revised due to half of the sentence was lost in the beginning of section 3.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wu, Y., Zhu, Y. Submodular Functions and Rooted Trees. Theory Comput Syst 66, 1047–1073 (2022). https://doi.org/10.1007/s00224-022-10092-x

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-022-10092-x

Keywords

Search

Navigation